OAmaster
— / 5已做

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 out
import 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;
    }
};

02Calculate Change

Given 2 non-negative double numbers first representing price of product

Example 1

Input:

pp = 230.0
cash = 500.0

Output:

"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:

55

Explanation: 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;
    }
};

SDE I An array is called palindromic if it remains the same after reversing the order of its elements. You have an array of strings arr. For each i, arr[i] consists of at least two characters. For each pair of consecutive elements arr[i] and arr[i + 1], you can: Move the rightmost character of arr[i] to the leftmost position in arr[i + 1]. For instance, "abc" and "def" will become "ab" and "cdef". This operation can be applied only once to any pair of consecutive elements. Move the leftmost character of arr[i + 1] to the rightmost position in arr[i]. For instance, "abc" and "def" will become "abcd" and "ef". Again, this operation can be applied only once to any pair of consecutive elements. Do nothing to the pair of consecutive elements. Is it possible to obtain a palindromic array from arr by performing these operations? return 1 --> True return 0 --> False Return 1 if the given array can be turned into a palindromic array, otherwise return 0.

Constraints

  • 1 ≤ arr.length ≤ 10⁵
  • 2 ≤ arr[i].length ≤ 10

Example 1

Input:

arr = ["aa", "bab", "cde", "aba", "ab"]

Output:

1

Explanation: Apply the second operation to "aa" and "bab". Apply the first operation to "aba" and "ab". This gives us the following array: ["aab", "ab", "cde", "ab", "aab"], which is palindromic.

Example 2

Input:

arr = ["palindrome"]

Output:

1

Explanation: The given array is already palindromic, so no operations are needed.

Example 3

Input:

arr = ["aaaaaa", "aa"]

Output:

0

Explanation: If moving two characters between two consecutive array elements was allowed, the array could have been made palindromic, but this is impossible given the actual rules.

Pro解法 · 三语代码 · 复杂度分析
边界讨论 + 面试官追问 · $98 / 一年解锁

Given a string of digits, repeatedly sum any consecutive identical digits until there are no more consecutive duplicates. For example: Input: 99823

  • 99 becomes 18 → 18823
  • 88 becomes 16 → 11623
  • 11 becomes 2 → 2623 Now there are no more consecutive identical digits, so output the final result: 2623. Function Description Complete the function sumConsecutiveIdenticalDigits in the editor. sumConsecutiveIdenticalDigits has the following parameter:
  • String digits: a string of digits Returns String: the final string after summing all consecutive identical digits

Example 1

Input:

digits = "99823"

Output:

"2623"

Explanation:

  • 99 becomes 18 → 18823
  • 88 becomes 16 → 11623
  • 11 becomes 2 → 2623 Now there are no more consecutive identical digits, so output the final result: 2623.
Pro解法 · 三语代码 · 复杂度分析
边界讨论 + 面试官追问 · $98 / 一年解锁
Pro 会员

解锁全部 2 道题的解法

题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.

Pro 解锁全部
  • 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
  • 📊个人 dashboard + 进度可视化 + 14 天活跃图
  • 📝题目笔记跨设备同步 + 个人复盘库
  • 🔓随时取消下次续费, Stripe Customer Portal 自助管理
$12/月($98/年, 一次付清省 32%)

≈ 北美 SWE 工资 10 分钟 · LeetCode Premium $35/月 的 23%

立即解锁 $98/年已是会员, 去登录

Agoda

Agoda OA 真题，三语题解(Python / Java / C++)。

Money Forward

Money Forward OA 真题，三语题解(Python / Java / C++)。