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 the xᵗʰ item to v.
• 2 v: Change any price that is less than v to v (apply a floor of v to 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 res

class 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 res

class 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 -1

class 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;
}

Implement a prototype of a friend recommendation system for a social media application. There are n users indexed from 0 to n-1, and m friendships are represented as a 2-d array friendships.

A user x is suggested as a friend to user y if:

1. x and y are not friends.
2. x and y have the maximum number of common friends.
3. If multiple users satisfy conditions 1 and 2, the user with the minimum index is recommended.

For each of the n users, find the index of the friend that should be recommended to them. If there is no recommendation available, report -1.

Constraints: 1 ≤ n ≤ 10⁵, max 15 friends per user.

Determine if a bot can reach a specified destination point on a grid. The bot starts at coordinates (x, y) and must reach a target location. It can make unlimited moves but is restricted to only two types of movements:

1. Move from (x, y) to (x + y, y)
2. Move from (x, y) to (x, x + y)

Both starting and target coordinates have 1 ≤ x1, y1, x2, y2 ≤ 1000. Return "Yes" if reachable, else "No".

Given a tree with g_nodes nodes and g_edges undirected edges. Each edge has an integer value from 1 to 26, mapping to 'a' to 'z'.

For each shortest path between two nodes, determine whether the sequence of characters of the edges encountered can be rearranged into a palindrome. If so, the pair of vertices is a nice pair. Determine the number of distinct nice pairs.

A ride hailing company sometimes travels between cities. To avoid delays, a driver first checks for the shortest routes. There is a map of the cities and their bidirectional roads represented by a graph of nodes and edges. Determine the paths from the first node to the last node and choose the shortest length. Now select all paths that are that length. These are the shortest paths. Return an array of strings, one for each road in order, where the value is YES if the road is along any shortest path or NO if it is not. The roads or edges are named using their 1-based index within the input arrays. Function Description Complete the function classifyEdges in the editor. classifyEdges has the following parameter(s): int g_nodes: an integer, the num of nodes

• int g_from[g_edges]: an array of integers, the start g_nodes for each road
• int g_to[g_edges]: an array of integers, the end g_nodes for each road
• int g_weight[g_edges]: an array of integers, the lengths of each road

Constraints

An unknown urban legend

Example 1

Input:

g_nodes = 5
g_from = [1, 2, 3, 4, 5, 1, 5]
g_to = [2, 3, 4, 5, 1, 3, 3]
g_weight = [1, 1, 1, 1, 3, 2, 1]

Output:

["YES", "YES", "NO", "NO", "YES", "YES", "YES"]

Explanation: Given a map of g_nodes = 5 nodes, the starting nodes, ending nodes and road lengths are:

• The traveller must travel from city 1 to city g_nodes, so from node 1 to node S in thsi case
• The shortest path is 3 units long and there are three paths of that length: 1->5, 1->2->3->5, and 1->3->5
• Return an array of strings, one for each road in order, where the values is YES if a road is along a shortes path or NO if it is not. In this case the resulting array is ["YES", "YES", "NO", "NO", "YES", "YES", "YES"]. The third and fourth raods connect nodes (3, 4) and (4, 5) respectively. They are not on a shorest path, i.e. one with a len of 3 in this case

You are organizing an event where there will be a number of presenters. The event starts at time 0 and time be allocated for networking at any time during the event when there is not a presentation being made. The presentations may not overlap as they are in the same room, but this allows them to run consecutively, without breaks. While the order of speeches cannot be changed, there is a maximum number given that indicates how many speeches may be rescheduled. Your goal is to maximize the length of the longest networking period you can arrange. Function Description Complete the function maxNetworkingTime in the editor. maxNetworkingTime has the following parameters:

1. int[] start: an array of integers indicating the start times of the presentations

• 2. int[] finish: an array of integers indicating the end times of the presentations
• 3. k: the maximum number of presentations that can be rescheduled Returns int: the maximum length of the longest networking period that can be arranged

Constraints

Unkown for now. Will be sure to add once find them

Example 1

Input:

start = [4, 6, 7, 10]
finish = [5, 7, 8, 11]
k = 2

Output:

6

Explanation: there are n = 4 presenters scheduled for the course of the event which begins at time 0 and ends at time t = 15. The meetings start at times start = [4, 6, 7, 10] and end at times finish = [5, 7, 8, 11]. You can rearrange up to k = 2 meetings. Green cells are free, marked with the hour number, and blue cells have a presentation scheduled, marked with presentation number. (Shown in the first line of colors in the image) In this case, we have 4 periods without speakers scheduled: [0-3], [5-6], [8-9], [11-14]. The meeting ends after hour 14. If the first meeting is shifted to an hour later, a break is created from 0 to 5 hours. If the last speech is moved up to 8, it will end at 9 leaving a break from 9 to 15. There is no point to moving the middle two speeches in this case. The longest break that can be achieved is 15 - 9 = 6 hours by moving the last speech to two hours earlier. The two options are illustrated in the option1 and option2 lines in the image above.

A start-up owner is looking to meet new investors to get some funds for his company. Each investor has a tight schedule that the owner has to respect. Given the schedules of the days investors are available, determine how many meetings the owner can schedule. Note that the owner can only have one meeting per day. The schedules consists of two integer arrays, firstDay and lastDay. Each element in the array firstDay represents the first day an investor is available, and each element in lastDay represents the last day an investor is available, both inclusive. Function Description Complete the function maxMeetings in the editor. maxMeetings has the following parameters:

• int[] firstDay: an array of integers representing the first day investors are available
• int[] lastDay: an array of integers representing the last day investors are available Returns int: the maximum number of meetings that can be scheduled

Constraints

Unkown for now. Will be sure to add once find them