A general store at hackerland sells n items with the price of the ith item represented by price[i]. The store adjusts the price of the items based on inflation as queries of two types:

• 1. 1 x v: change the price of the xth item to v.
• 2. 2 v v: change any price that is less than v to v. 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. Function Description: Complete the func adjustPrices in the editor adjustPrices has the following parameter(s): int price[n]: an arr of integers int queries[q][3]: A 2-d arr of ints

Constraints

• 1 ≤ n, q ≤ 10⁵
• 1 ≤ price[i], v ≤ 10⁹
• 1 ≤ x ≤ n

解法

直接模拟。对每个 query：type 1 修改单点；type 2 对整个数组每个 < v 的位置改为 v。复杂度 O(q · n)。

from typing import List

def adjust_prices(price: List[int], queries: List[List[int]]) -> List[int]:
    arr = list(price)
    for q in queries:
        if q[0] == 1:
            x, v = q[1], q[2]
            arr[x - 1] = v
        else:
            v = q[1]
            for i in range(len(arr)):
                if arr[i] < v:
                    arr[i] = v
    return arr

class Solution {
    int[] adjustPrices(int[] price, int[][] queries) {
        int[] arr = price.clone();
        for (int[] q : queries) {
            if (q[0] == 1) arr[q[1] - 1] = q[2];
            else for (int i = 0; i < arr.length; i++) if (arr[i] < q[1]) arr[i] = q[1];
        }
        return arr;
    }
}

class Solution {
public:
    vector<int> adjustPrices(vector<int>& price, vector<vector<int>>& queries) {
        vector<int> arr = price;
        for (auto& q : queries) {
            if (q[0] == 1) arr[q[1] - 1] = q[2];
            else for (int& x : arr) if (x < q[1]) x = q[1];
        }
        return arr;
    }
};

A DashMart is a warehouse run by DoorDash that houses items found in convenience stores, grocery stores, and restaurants. We have a city with open roads, blocked-off roads, and DashMarts. City planners want you to identify how far a location is from its closest DashMart. You can only travel over open roads (up, down, left, right). Locations are given in [row, col] format. Provided:

• city: char[][] - A 2D array representing the city where ' ' represents an open road, 'X' represents a blocked road, and 'D' represents a DashMart.
• locations: int[][2] - A list of pairs [row, col] representing the locations to check. Return: answer: int[] - Return a list of the distances from a given point to its closest DashMart. If a DashMart cannot be reached from a location, return -1 for that location.

Example 1

Input:

city = [
['X', ' ', ' ', 'D', ' ', ' ', 'X', ' ', 'X'],
['X', ' ', 'X', 'X', ' ', ' ', ' ', ' ', 'X'],
[' ', ' ', ' ', 'D', 'X', 'X', ' ', 'X', ' '],
[' ', ' ', ' ', 'D', ' ', 'X', ' ', ' ', ' '],
[' ', ' ', ' ', ' ', ' ', 'X', ' ', ' ', 'X'],
[' ', ' ', ' ', ' ', 'X', ' ', ' ', 'X', 'X']
]
locations = [[200, 200], [1, 4], [0, 3], [5, 8], [1, 8], [5, 5]]

Output:

[-1, 2, 0, -1, 6, 9]

Explanation:

解法

多源 BFS：从所有 D 同时入队，按 4 邻接扩展，跳过 X；每格记录距离 dist[i][j]。查询每个 location，越界或 dist == INF 返回 -1。复杂度 O(R · C + Q)。

from typing import List
from collections import deque

def closest_dashmart(city: List[List[str]], locations: List[List[int]]) -> List[int]:
    if not city:
        return [-1] * len(locations)
    R, C = len(city), len(city[0])
    INF = float("inf")
    dist = [[INF] * C for _ in range(R)]
    q = deque()
    for i in range(R):
        for j in range(C):
            if city[i][j] == 'D':
                dist[i][j] = 0
                q.append((i, j))
    while q:
        r, c = q.popleft()
        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and city[nr][nc] != 'X' and dist[nr][nc] > dist[r][c] + 1:
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    res = []
    for r, c in locations:
        if not (0 <= r < R and 0 <= c < C) or dist[r][c] == INF:
            res.append(-1)
        else:
            res.append(int(dist[r][c]))
    return res

import java.util.*;

class Solution {
    int[] closestDashmart(char[][] city, int[][] locations) {
        int R = city.length, C = R == 0 ? 0 : city[0].length;
        int[][] dist = new int[R][C];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        Deque<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                if (city[i][j] == 'D') { dist[i][j] = 0; q.add(new int[]{i, j}); }
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] d : dirs) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr >= 0 && nr < R && nc >= 0 && nc < C && city[nr][nc] != 'X' && dist[nr][nc] > dist[cur[0]][cur[1]] + 1) {
                    dist[nr][nc] = dist[cur[0]][cur[1]] + 1;
                    q.add(new int[]{nr, nc});
                }
            }
        }
        int[] res = new int[locations.length];
        for (int i = 0; i < locations.length; i++) {
            int r = locations[i][0], c = locations[i][1];
            res[i] = (r < 0 || r >= R || c < 0 || c >= C || dist[r][c] == Integer.MAX_VALUE) ? -1 : dist[r][c];
        }
        return res;
    }
}

class Solution {
public:
    vector<int> closestDashmart(vector<vector<char>>& city, vector<vector<int>>& locations) {
        int R = city.size(), C = R == 0 ? 0 : city[0].size();
        vector<vector<int>> dist(R, vector<int>(C, INT_MAX));
        queue<pair<int, int>> q;
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                if (city[i][j] == 'D') { dist[i][j] = 0; q.push({i, j}); }
        int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < R && nc >= 0 && nc < C && city[nr][nc] != 'X' && dist[nr][nc] > dist[r][c] + 1) {
                    dist[nr][nc] = dist[r][c] + 1;
                    q.push({nr, nc});
                }
            }
        }
        vector<int> res;
        for (auto& loc : locations) {
            int r = loc[0], c = loc[1];
            if (r < 0 || r >= R || c < 0 || c >= C || dist[r][c] == INT_MAX) res.push_back(-1);
            else res.push_back(dist[r][c]);
        }
        return res;
    }
};

As an assignment, students at HackerLand High School are to find a subsequence using two strings by performing the below-mentioned operation. Given two strings firstString of length n and secondString of length m, the goal is to make secondString a subsequence of firstString by applying the operation any number of times. In one operation, any single character can be removed from the secondString. The goal is to find the minimum possible difference value which is calculated as: | maximum index of all the characters removed from the string secondString | - | minimum index of all the characters removed from the string secondString | + 1. Removing a character from secondString does not affect the indices of the other characters and an empty string is always a subsequence of firstString. Note: A subsequence of a string is a new string formed deleting some (can be none) of the characters from a string without changing the relative positions of the remaining characters. "ace" is a subsequence of "abcde" but "aec" is not. Function Description Complete the function findDifferenceValue in the editor.

Constraints

• 1 ≤ n, m ≤ 10⁵
• firstString and secondString consist of uppercase English letters

Example 1

Input:

firstString = "HACKERRANK"
secondString = "HACKERMAN"

Output:

1

Explanation: Remove the character at index 7 to change secondString to "HACKERAN", a subsequence of firstString. The difference value is 7 - 7 + 1 = 1. Return 1.

解法

用双指针求 secondString 在 firstString 中匹配的前缀和后缀：prefix[i] = 让 secondString[0..i] 是 firstString 子序列时 firstString 的最早匹配位置；suffix[j] = 让 secondString[j..] 是 firstString 子序列时 firstString 的最晚起始位置。然后枚举要删除的连续区间 [l, r]：要求 prefix[l-1] < suffix[r+1]。最小化 r - l + 1。复杂度 O(n + m)。

def find_difference_value(firstString: str, secondString: str) -> int:
    n, m = len(firstString), len(secondString)
    prefix = [-1] * (m + 2)
    j = 0
    for i in range(m):
        while j < n and firstString[j] != secondString[i]:
            j += 1
        if j == n:
            prefix[i] = n + 1
            for k in range(i, m):
                prefix[k] = n + 1
            break
        prefix[i] = j
        j += 1
    suffix = [n + 1] * (m + 2)
    j = n - 1
    for i in range(m - 1, -1, -1):
        while j >= 0 and firstString[j] != secondString[i]:
            j -= 1
        if j < 0:
            for k in range(i, -1, -1):
                suffix[k] = -1
            break
        suffix[i] = j
        j -= 1
    best = m
    for l in range(m):
        for r in range(l, m):
            left_ok = l == 0 or (prefix[l - 1] >= 0 and prefix[l - 1] < n)
            right_ok = r == m - 1 or (suffix[r + 1] >= 0 and suffix[r + 1] <= n - 1)
            mid_ok = (l == 0 or r == m - 1) or (prefix[l - 1] < suffix[r + 1])
            if left_ok and right_ok and mid_ok:
                if r - l + 1 < best:
                    best = r - l + 1
    if best == m:
        return 0
    return best

class Solution {
    int findDifferenceValue(String firstString, String secondString) {
        int n = firstString.length(), m = secondString.length();
        int[] prefix = new int[m + 2];
        Arrays.fill(prefix, -1);
        int j = 0;
        for (int i = 0; i < m; i++) {
            while (j < n && firstString.charAt(j) != secondString.charAt(i)) j++;
            if (j == n) { for (int k = i; k < m; k++) prefix[k] = n + 1; break; }
            prefix[i] = j;
            j++;
        }
        int[] suffix = new int[m + 2];
        Arrays.fill(suffix, n + 1);
        j = n - 1;
        for (int i = m - 1; i >= 0; i--) {
            while (j >= 0 && firstString.charAt(j) != secondString.charAt(i)) j--;
            if (j < 0) { for (int k = i; k >= 0; k--) suffix[k] = -1; break; }
            suffix[i] = j;
            j--;
        }
        int best = m;
        for (int l = 0; l < m; l++)
            for (int r = l; r < m; r++) {
                boolean leftOk = l == 0 || (prefix[l - 1] >= 0 && prefix[l - 1] < n);
                boolean rightOk = r == m - 1 || (suffix[r + 1] >= 0 && suffix[r + 1] <= n - 1);
                boolean midOk = (l == 0 || r == m - 1) || (prefix[l - 1] < suffix[r + 1]);
                if (leftOk && rightOk && midOk) best = Math.min(best, r - l + 1);
            }
        return best == m ? 0 : best;
    }
}

class Solution {
public:
    int findDifferenceValue(string firstString, string secondString) {
        int n = firstString.size(), m = secondString.size();
        vector<int> prefix(m + 2, -1), suffix(m + 2, n + 1);
        int j = 0;
        for (int i = 0; i < m; i++) {
            while (j < n && firstString[j] != secondString[i]) j++;
            if (j == n) { for (int k = i; k < m; k++) prefix[k] = n + 1; break; }
            prefix[i] = j++;
        }
        j = n - 1;
        for (int i = m - 1; i >= 0; i--) {
            while (j >= 0 && firstString[j] != secondString[i]) j--;
            if (j < 0) { for (int k = i; k >= 0; k--) suffix[k] = -1; break; }
            suffix[i] = j--;
        }
        int best = m;
        for (int l = 0; l < m; l++)
            for (int r = l; r < m; r++) {
                bool leftOk = l == 0 || (prefix[l - 1] >= 0 && prefix[l - 1] < n);
                bool rightOk = r == m - 1 || (suffix[r + 1] >= 0 && suffix[r + 1] <= n - 1);
                bool midOk = (l == 0 || r == m - 1) || (prefix[l - 1] < suffix[r + 1]);
                if (leftOk && rightOk && midOk) best = min(best, r - l + 1);
            }
        return best == m ? 0 : best;
    }
};

A general store at Hackerland sells n items with the price of the ith item represented by price[i]. The store adjusts the price of the items based on inflation as queries of two types:

1. 1 x v: Change the price of the xth item to v.
2. 2 v v: Change any price that is less than v to v. 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. Function Description Complete the function getFinalPrice in the editor. getFinalPrice has the following parameter(s):

• int price[n]: An array of integers
• int queries[q][3]: A 2-d array of integers Returns int[]: the final array after all queries are executed

Example 1

Input:

price = [7, 5, 4]
queries = [[2, 6, 6], [1, 2, 9], [2, 8, 8]]

Output:

[8, 9, 8]

Explanation:

• [2, 6, 6]: Change elements < 6 to 6. Now arr = [7, 6, 6].
• [1, 2, 9]: Change the 2nd element to 9. arr = [7, 9, 6].
• [2, 8, 8]: Change elements < 8 to 8. Finally arr = [8, 9, 8]. Return [8, 9, 8] as the answer.

As new students begin to arrive at college, each receives a unique ID number, 1 to n. Initially, the students do not know one another, and each has a different circle of friends. As the semester progresses, other groups of friends begin to form randomly. There will be three arrays, each aligned by an index. The first array will contain a queryType which will be either Friend or Total. The next two arrays, students1 and students2, will each contain a student ID. If the query type is Friend, the two students become friends. If the query type is Total, report the sum of the sizes of each group of friends for the two students. Function Description Complete the function getSizesOfFriendsGroups in the editor. getSizesOfFriendsGroups has the following parameters:

• 1. String[] queryType: an array of strings representing the type of query
• 2. int[] student1: an array of integers representing the first student IDs
• 3. int[] student2: an array of integers representing the second student IDs
• 4. n: the number of students Returns int: the sum of the sizes of each group of friends for the two students in a Total query

Constraints

• 1 ≤ n ≤ 10⁵
• 1 ≤ queryType.length ≤ 10⁵
• 1 ≤ student1[i], student2[i] ≤ n

Example 1

Input:

queryType = ["Friend", "Friend", "Total"]
student1 = [1, 2, 1]
student2 = [2, 3, 4]
n = 4

Output:

4

Explanation: Students will start as discrete groups {1}, {2}, {3} and {4}. Students 1 and 2 become friends with the first query, as well as students 2 and 3 in the second. The new groups are {1, 2}, {2, 3} and {4} which simplifies to {1, 2, 3} and {4}. In the third query, the number of friends for student 1 = 3 and student 4 = 1 for a Total = 4. Notice that student 3 is indirectly part of the circle of friends of student 1 because of student 2.

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem. You are given three integer arrays: chefSkill: each chef's skill level dishDifficulty: each dish's difficulty dishProfit: the profit earned for completing that dish Rules: Each chef can complete at most one dish. A dish can be completed by multiple chefs (dishes are not exclusive). A chef can only complete dishes with difficulty ≤ their skill. Compute the maximum total profit by assigning each chef the best dish they can do. Example Input: chefSkill = [1,2,3] dishDifficulty = [1,2,3] dishProfit = [1,2,3] Output: 6 Explanation: each chef picks the most profitable dish they can do. Typical constraints (you may state/assume during the interview) 1 ≤ len(chefSkill), len(dishDifficulty), len(dishProfit) ≤ 2e5 values are non-negative integers and arrays may be unsorted. Task Return the maximum total profit as an integer. Example Input 3 1 2 3 3 1 2 3 Output 6 Function Description Complete solveMaximizeChefDishProfit. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.

Constraints

Use the limits and requirements stated in the prompt.

Given a list of ints representing order IDs, return the priority of the order IDs based on the values of their neighbors. An order is considered if it's greater than it's neighbors to the left and right of it. Function Description Complete the function getOrderPriorities in the editor. getOrderPriorities has the following parameter:

• List orderIds: a list of integers representing order IDs Returns List: the priority of the order IDs

Example 1

Input:

orderIds = [3, 5, 1, 4, 2]

Output:

[4, 2, 5, 3, 1]

Explanation: If we iterate over [3, 5, 1, 4, 2], the order IDs that can be considered in this first pass is 5 and 4. In this case, remove 4 because it's the order ID with the smallest value. The result of the removal looks like this: [3, 5, 1, 2] If we iterate over [3, 5, 1, 2], the order IDs that can be considered in this pass is 5 and 2. In this case, remove 2 because it's the order ID with the smallest value. The result of the removal looks like this: [3, 5, 1] Continue on from there until the list is empty

Given a list of employees where each is assigned a numeric evaluation score, use the selection process below to find the sum of scores of selected employees.

• The employee with the highest score among the first k employees or the last k employees in the score list is selected.
• The selected employee is removed from the score list.
• The process continues to select the next employee until the team_size is achieved. Note:
• In case multiple employees have the same highest score, the employee with the lowest index is selected.
• If there are fewer than k employees, the entire list is available for selection. Function Description Complete the function teamFormation in the editor. teamFormation has the following parameter(s):
• score[n]: an array of scores for each employee
• team_size: the number of team members required
• k: the size of the array segments to select from