A general store at Hackerland sells n items with the price of the iᵗʰ item represented by price[i]. The store adjusts the price of the items based on inflation as queries of two types:
1 x v: Change the price of thexᵗʰitem tov.2 v: Change any price that is less thanvtov(apply a floor ofvto all items).
Given an array price of n integers and the price adjustment queries are in the form of a 2-d array where query[i] consists of 3 integers, find the final prices of all the items.
Constraints: 1 ≤ n ≤ 2·10⁵, 1 ≤ q ≤ 2·10⁵.
解法
倒着扫查询，维护 suffix_floor(右侧所有 type-2 设底操作的最大 v)。首次遇到下标 x 的 type-1 [1, x, v] 时，x 的最终值固定为 max(v, suffix_floor)(visited[x] = true)。扫完后未触动的下标取 max(price[i], suffix_floor)。复杂度 O(n + q)。
def getFinalPrice(price, queries):
n = len(price); res = list(price); visited = [False] * n; suf = 0
for q in reversed(queries):
if q[0] == 1:
idx = q[1] - 1
if not visited[idx]: res[idx] = max(q[2], suf); visited[idx] = True
else: suf = max(suf, q[1])
for i in range(n):
if not visited[i]: res[i] = max(price[i], suf)
return resclass Solution {
public int[] getFinalPrice(int[] price, int[][] queries) {
int n = price.length;
int[] res = price.clone();
boolean[] visited = new boolean[n];
int suffixFloor = 0;
for (int i = queries.length - 1; i >= 0; i--) {
int[] q = queries[i];
if (q[0] == 1) {
int idx = q[1] - 1;
if (!visited[idx]) { res[idx] = Math.max(q[2], suffixFloor); visited[idx] = true; }
} else suffixFloor = Math.max(suffixFloor, q[1]);
}
for (int i = 0; i < n; i++) if (!visited[i]) res[i] = Math.max(price[i], suffixFloor);
return res;
}
}vector<int> getFinalPrice(vector<int>& price, vector<vector<int>>& queries) {
int n = price.size();
vector<int> res(price);
vector<bool> visited(n, false);
int suffixFloor = 0;
for (int i = queries.size() - 1; i >= 0; --i) {
auto& q = queries[i];
if (q[0] == 1) {
int idx = q[1] - 1;
if (!visited[idx]) { res[idx] = max(q[2], suffixFloor); visited[idx] = true; }
} else suffixFloor = max(suffixFloor, q[1]);
}
for (int i = 0; i < n; ++i) if (!visited[i]) res[i] = max(price[i], suffixFloor);
return res;
}For each element in a given array, calculate the absolute value of index differences between it and all other elements of the same value. Return the resulting values in an array. For example, if the array elements at indices 2 and 3 are equal, the distance metric for element 2 is |2-3| = 1. For element 3 it is |3-2| = 1.
解法
按值分组下标。对每组 [i₀ < i₁ < ... < i_{k-1}]，i_j 的距离度量 = Σ_{t≠j} |i_j - i_t|。按序遍历用前缀和：j · i_j - (i_0 + ... + i_{j-1}) + (i_{j+1} + ... + i_{k-1}) - (k - 1 - j) · i_j。复杂度 O(n)。
def getDistanceMetric(arr):
from collections import defaultdict
groups = defaultdict(list)
for i, v in enumerate(arr): groups[v].append(i)
res = [0] * len(arr)
for idxs in groups.values():
m = len(idxs)
if m <= 1: continue
pre = [0] * (m + 1)
for i, x in enumerate(idxs): pre[i + 1] = pre[i] + x
total = pre[m]
for k, x in enumerate(idxs):
res[x] = k * x - pre[k] + (total - pre[k + 1]) - (m - 1 - k) * x
return resclass Solution {
public long[] getDistanceMetric(int[] arr) {
int n = arr.length;
Map<Integer, List<Integer>> groups = new HashMap<>();
for (int i = 0; i < n; i++) groups.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
long[] res = new long[n];
for (List<Integer> idxs : groups.values()) {
int m = idxs.size();
if (m <= 1) continue;
long[] pre = new long[m + 1];
for (int i = 0; i < m; i++) pre[i + 1] = pre[i] + idxs.get(i);
long total = pre[m];
for (int k = 0; k < m; k++) {
long x = idxs.get(k);
long left = (long) k * x - pre[k];
long right = (total - pre[k + 1]) - (long) (m - 1 - k) * x;
res[(int) x] = left + right;
}
}
return res;
}
}vector<long long> getDistanceMetric(vector<int>& arr) {
int n = arr.size();
unordered_map<int, vector<int>> groups;
for (int i = 0; i < n; ++i) groups[arr[i]].push_back(i);
vector<long long> res(n, 0);
for (auto& [v, idxs] : groups) {
int m = idxs.size();
if (m <= 1) continue;
vector<long long> pre(m + 1, 0);
for (int i = 0; i < m; ++i) pre[i + 1] = pre[i] + idxs[i];
long long total = pre[m];
for (int k = 0; k < m; ++k) {
long long x = idxs[k];
long long left = (long long)k * x - pre[k];
long long right = (total - pre[k + 1]) - (long long)(m - 1 - k) * x;
res[x] = left + right;
}
}
return res;
}Bob and Alice have teamed up on a game where, after winning the first round, they now have access to a maze with hidden gold. If Bob can collect all the gold coins and deliver them to Alice, they can split the gold. Bob can move horizontally or vertically as long as he stays in the maze, and the cell is not blocked.
The maze is represented by an n × m array. Each cell has a value, where 0 is open, 1 is blocked, and 2 is open and contains a gold coin. Bob starts at the top left position (0, 0), and Alice's position is given by (x, y). Determine the shortest path Bob can take to collect all gold coins and deliver them to Alice. If Bob can't collect and give all the gold coins, return -1.
解法
在 (r, c, collected_mask) 上做位掩码 BFS。给金币编号 0..k-1(一般 k ≤ 20)。状态空间 n × m × 2^k；每状态扩展 4 邻居，邻居是金币就 OR 上对应位，首次到 (x, y) 且 mask == (1 << k) - 1 时停。复杂度 O(n · m · 2^k)。
from collections import deque
def minMoves(maze, x, y):
n, m = len(maze), len(maze[0])
coin_idx = {(i, j): k for k, (i, j) in enumerate(
(i, j) for i in range(n) for j in range(m) if maze[i][j] == 2)}
full = (1 << len(coin_idx)) - 1
if maze[0][0] == 1: return -1
dq = deque([(0, 0, 0, 0)])
seen = {(0, 0, 0)}
while dq:
r, c, mask, d = dq.popleft()
if (r, c) == (x, y) and mask == full: return d
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r + dr, c + dc
if not (0 <= nr < n and 0 <= nc < m) or maze[nr][nc] == 1: continue
nm = mask | (1 << coin_idx[(nr, nc)]) if (nr, nc) in coin_idx else mask
if (nr, nc, nm) in seen: continue
seen.add((nr, nc, nm)); dq.append((nr, nc, nm, d + 1))
return -1class Solution {
public int minMoves(int[][] maze, int x, int y) {
int n = maze.length, m = maze[0].length;
Map<Long, Integer> coinIdx = new HashMap<>();
int k = 0;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
if (maze[i][j] == 2) coinIdx.put((long) i * m + j, k++);
int full = (1 << k) - 1;
if (maze[0][0] == 1) return -1;
Deque<int[]> dq = new ArrayDeque<>();
Set<Long> seen = new HashSet<>();
dq.add(new int[]{0, 0, 0, 0});
seen.add(0L);
int[] dr = {-1,1,0,0}, dc = {0,0,-1,1};
while (!dq.isEmpty()) {
int[] s = dq.poll();
if (s[0] == x && s[1] == y && s[2] == full) return s[3];
for (int i = 0; i < 4; i++) {
int nr = s[0] + dr[i], nc = s[1] + dc[i];
if (nr < 0 || nr >= n || nc < 0 || nc >= m || maze[nr][nc] == 1) continue;
int nm = s[2];
Long key = (long) nr * m + nc;
if (coinIdx.containsKey(key)) nm |= (1 << coinIdx.get(key));
long st = ((long) nr * m + nc) * 128 + nm;
if (seen.add(st)) dq.add(new int[]{nr, nc, nm, s[3] + 1});
}
}
return -1;
}
}int minMoves(vector<vector<int>>& maze, int x, int y) {
int n = maze.size(), m = maze[0].size();
map<pair<int,int>, int> coinIdx;
int k = 0;
for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j)
if (maze[i][j] == 2) coinIdx[{i, j}] = k++;
int full = (1 << k) - 1;
if (maze[0][0] == 1) return -1;
queue<tuple<int,int,int,int>> dq;
set<tuple<int,int,int>> seen;
dq.push({0, 0, 0, 0}); seen.insert({0, 0, 0});
int dr[] = {-1,1,0,0}, dc[] = {0,0,-1,1};
while (!dq.empty()) {
auto [r, c, mask, d] = dq.front(); dq.pop();
if (r == x && c == y && mask == full) return d;
for (int i = 0; i < 4; ++i) {
int nr = r + dr[i], nc = c + dc[i];
if (nr < 0 || nr >= n || nc < 0 || nc >= m || maze[nr][nc] == 1) continue;
int nm = mask;
if (coinIdx.count({nr, nc})) nm |= (1 << coinIdx[{nr, nc}]);
if (seen.insert({nr, nc, nm}).second) dq.push({nr, nc, nm, d + 1});
}
}
return -1;
}