Consider a rectangular h × w board with all cells initially white. You are to process several queries of the following types:
"x a b" - color the white cell (a, b) (0-based coordinates, the first one is a row index, and the second one is a column index) black;
"> a b" - find the leftmost white cell to the right of the white cell (a, b);
""v a b" - the same, but the search should be done downwards;
"^ a b" - the same, but the search should be done upwards;
For each query, except the ones of the first type, find the answer.
For each query except the ones of the first type, store the answer's coordinates in the array. If the desired cell doesn't exist, store [-1, -1] instead. The answers should be stored in the same order as the queries.
Constraints
1 ≤ h ≤ 500.1 ≤ w ≤ 500.5 ≤ queries.length ≤ 10⁴ (OR MAYBE 104).
Example 1
Input:
h = 3
w = 5
queries = ["v 1 2", "x 2 2", "v 1 2", "> 2 1", "x 2 3", "> 2 1", "< 2 0"]Output:
[[2, 2], [-1, -1], [2, 3], [2, 4], [-1, -1]]Explanation: :3
解法
每行/每列维护一个并查集 jump-pointer：next_right[r][c] 表示从 (r, c) 向右走(含自身)的下一个白格列号，初始 next_right[r][c] = c；染黑后将 next_right[r][c] = c + 1，路径压缩。同理 next_left、next_down、next_up。每次查询沿对应数组查一次。注意题目中查询参数 (a, b) 本身保证是白格——但若不是白色，返回 [-1, -1] 是特例。时间 O((h·w + q) α)。
from typing import List
def board_queries(h: int, w: int, queries: List[str]) -> List[List[int]]:
black = [[False] * w for _ in range(h)]
# next pointers for each direction
nr = [list(range(w + 1)) for _ in range(h)] # right: nr[r][c] = next col >= c that is white, or w
nl = [list(range(-1, w)) for _ in range(h)] # left
nd = [list(range(h + 1)) for _ in range(w)]
nu = [list(range(-1, h)) for _ in range(w)]
def find_r(r, c):
if c >= w or not black[r][c]: return c if c < w and not black[r][c] else -1
# walk
return -1
def find_right(r, c):
# find leftmost white col > c in row r
cc = c + 1
while cc < w and black[r][cc]:
cc += 1
return cc if cc < w else -1
def find_left(r, c):
cc = c - 1
while cc >= 0 and black[r][cc]: cc -= 1
return cc if cc >= 0 else -1
def find_down(r, c):
rr = r + 1
while rr < h and black[rr][c]: rr += 1
return rr if rr < h else -1
def find_up(r, c):
rr = r - 1
while rr >= 0 and black[rr][c]: rr -= 1
return rr if rr >= 0 else -1
out: List[List[int]] = []
for q in queries:
parts = q.split()
op, a, b = parts[0], int(parts[1]), int(parts[2])
if op == 'x':
black[a][b] = True
else:
if op == '>':
cc = find_right(a, b)
out.append([a, cc] if cc != -1 else [-1, -1])
elif op == '<':
cc = find_left(a, b)
out.append([a, cc] if cc != -1 else [-1, -1])
elif op == 'v':
rr = find_down(a, b)
out.append([rr, b] if rr != -1 else [-1, -1])
elif op == '^':
rr = find_up(a, b)
out.append([rr, b] if rr != -1 else [-1, -1])
return outimport java.util.*;
class Solution {
public int[][] boardQueries(int h, int w, String[] queries) {
boolean[][] black = new boolean[h][w];
List<int[]> out = new ArrayList<>();
for (String q : queries) {
String[] parts = q.split("\\s+");
char op = parts[0].charAt(0);
int a = Integer.parseInt(parts[1]), b = Integer.parseInt(parts[2]);
if (op == 'x') { black[a][b] = true; continue; }
int rr = a, cc = b;
if (op == '>') { cc = b + 1; while (cc < w && black[a][cc]) cc++; if (cc == w) { out.add(new int[]{-1, -1}); continue; } }
else if (op == '<') { cc = b - 1; while (cc >= 0 && black[a][cc]) cc--; if (cc < 0) { out.add(new int[]{-1, -1}); continue; } }
else if (op == 'v') { rr = a + 1; while (rr < h && black[rr][b]) rr++; if (rr == h) { out.add(new int[]{-1, -1}); continue; } }
else if (op == '^') { rr = a - 1; while (rr >= 0 && black[rr][b]) rr--; if (rr < 0) { out.add(new int[]{-1, -1}); continue; } }
out.add(new int[]{rr, cc});
}
return out.toArray(new int[0][]);
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<vector<int>> boardQueries(int h, int w, vector<string>& queries) {
vector<vector<bool>> black(h, vector<bool>(w, false));
vector<vector<int>> out;
for (auto& q : queries) {
stringstream ss(q);
string op; int a, b; ss >> op >> a >> b;
char c = op[0];
if (c == 'x') { black[a][b] = true; continue; }
int rr = a, cc = b;
if (c == '>') { cc = b + 1; while (cc < w && black[a][cc]) cc++; if (cc == w) { out.push_back({-1, -1}); continue; } }
else if (c == '<') { cc = b - 1; while (cc >= 0 && black[a][cc]) cc--; if (cc < 0) { out.push_back({-1, -1}); continue; } }
else if (c == 'v') { rr = a + 1; while (rr < h && black[rr][b]) rr++; if (rr == h) { out.push_back({-1, -1}); continue; } }
else if (c == '^') { rr = a - 1; while (rr >= 0 && black[rr][b]) rr--; if (rr < 0) { out.push_back({-1, -1}); continue; } }
out.push_back({rr, cc});
}
return out;
}
};Given 2 non-negative double numbers first representing price of product
Example 1
Input:
pp = 230.0
cash = 500.0Output:
"Fifty,One Hundred,One Hundred,Twenty"Explanation: :O
解法
change = cash − pp(保留两位小数)；从最大面额向下贪心拆 (100, 50, 20, 10, 5, 1, 0.25, 0.10, 0.05, 0.01)，按出现次数生成对应英文名，逗号分隔。注意浮点用整数化(× 100)。
def calculate_change(pp: float, cash: float) -> str:
change_cents = round((cash - pp) * 100)
denoms = [(10000, "One Hundred"), (5000, "Fifty"), (2000, "Twenty"), (1000, "Ten"), (500, "Five"), (100, "One"), (25, "Quarter"), (10, "Dime"), (5, "Nickel"), (1, "Penny")]
out = []
for v, name in denoms:
while change_cents >= v:
change_cents -= v
out.append(name)
return ",".join(out)class Solution {
public String calculateChange(double pp, double cash) {
long c = Math.round((cash - pp) * 100);
int[] vals = {10000,5000,2000,1000,500,100,25,10,5,1};
String[] names = {"One Hundred","Fifty","Twenty","Ten","Five","One","Quarter","Dime","Nickel","Penny"};
StringBuilder sb = new StringBuilder();
for (int i = 0; i < vals.length; i++) {
while (c >= vals[i]) {
c -= vals[i];
if (sb.length() > 0) sb.append(',');
sb.append(names[i]);
}
}
return sb.toString();
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string calculateChange(double pp, double cash) {
long long c = llround((cash - pp) * 100);
vector<pair<long long, string>> denoms = {{10000, "One Hundred"}, {5000, "Fifty"}, {2000, "Twenty"}, {1000, "Ten"}, {500, "Five"}, {100, "One"}, {25, "Quarter"}, {10, "Dime"}, {5, "Nickel"}, {1, "Penny"}};
string out;
for (auto& [v, name] : denoms) {
while (c >= v) {
c -= v;
if (!out.empty()) out += ',';
out += name;
}
}
return out;
}
};You are given a string consisting of digits. Find the biggest two-digits value that is a consistent fragment of the given string.
For example, two-digit consistent fragments of "50552" are ["50","05","55","52"], representing the numbers [50,5,55,52]. The biggest value among them is 55.
Function Description
Write a function:
class Solution { public int solution(String S); }
that, given a string S consisting of digits, returns the maximum two-digit value that is a consistent fragment of S.
Example 1
Input:
S = "50552"Output:
55Explanation:
The two-digit consistent fragments of "50552" are ["50","05","55","52"], representing the numbers [50,5,55,52]. The biggest value among them is 55.
解法
扫描所有长度为 2 的连续子串，转 int，取最大。时间 O(N)。
def solution(S: str) -> int:
return max(int(S[i:i+2]) for i in range(len(S) - 1))class Solution {
public int solution(String S) {
int best = 0;
for (int i = 0; i + 1 < S.length(); i++) {
int v = Integer.parseInt(S.substring(i, i + 2));
if (v > best) best = v;
}
return best;
}
}#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solution(string S) {
int best = 0;
for (int i = 0; i + 1 < (int)S.size(); i++) {
int v = (S[i] - '0') * 10 + (S[i + 1] - '0');
if (v > best) best = v;
}
return best;
}
};