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 x v: change the price of thexth item tov.
-
2 v v: change any price that is less thanvtov. Given an arraypriceofnintegers and the price adjustment queries are in the form of a 2-d array wherequery[i]consists of 3 integers, find the final prices of all the items. Function Description: Complete the funcadjustPricesin the editoradjustPriceshas the following parameter(s):int price[n]: an arr of integersint 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 arrclass 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-1for 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 resimport 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⁵firstStringandsecondStringconsist of uppercase English letters
Example 1
Input:
firstString = "HACKERRANK"
secondString = "HACKERMAN"Output:
1Explanation:
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 bestclass 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;
}
};