登录
OAmaster

In a financial monitoring system, given an array of non-negative integers transactions (each element is the net transaction value for a day) and a positive integer k, find the length of the longest contiguous subarray whose sum is divisible by k. Return 0 if no such subarray exists.

Constraints

  • 1 ≤ transactions.length ≤ 10⁵
  • 0 ≤ transactions[i] ≤ 10⁹
  • 1 ≤ k ≤ 10⁹

解法

前缀和模 k。两个余数相同的前缀和之间的子数组和能被 k 整除。记录每个余数首次出现的下标，对每个 i 更新 ans = max(ans, i - first_idx[prefix_mod])。用 first_idx[0] = -1 初始化，让前缀本身可被算上。复杂度 O(n)。

solution([2, 3, 1, 6, 1, 5], 3) = 6
solution([1], 3) = 0
solution([1, 2, 3, 4, 5], 3) = 5
solution([2, 7, 6, 1, 4, 5], 3) = 4
def solution(transactions: list[int], k: int) -> int:
    # first_idx[r] = first prefix index where residue r appeared
    first_idx = {0: -1}
    prefix_mod = 0
    ans = 0

    for i, x in enumerate(transactions):
        prefix_mod = (prefix_mod + x) % k
        if prefix_mod in first_idx:
            ans = max(ans, i - first_idx[prefix_mod])
        else:
            first_idx[prefix_mod] = i      # only record first occurrence -> longest span
    return ans
import java.util.HashMap;

class Solution {
    int solution(int[] transactions, int k) {
        HashMap<Long, Integer> firstIdx = new HashMap<>();
        firstIdx.put(0L, -1);              // empty prefix has residue 0
        long prefixMod = 0;
        int ans = 0;

        for (int i = 0; i < transactions.length; i++) {
            prefixMod = (prefixMod + transactions[i]) % k;
            if (firstIdx.containsKey(prefixMod)) {
                ans = Math.max(ans, i - firstIdx.get(prefixMod));
            } else {
                firstIdx.put(prefixMod, i);
            }
        }
        return ans;
    }
}
#include <unordered_map>
class Solution {
public:
    int solution(vector<int>& transactions, int k) {
        unordered_map<long long, int> firstIdx;
        firstIdx[0] = -1;                  // empty prefix
        long long prefixMod = 0;
        int ans = 0;

        for (int i = 0; i < (int)transactions.size(); i++) {
            prefixMod = (prefixMod + transactions[i]) % k;
            auto it = firstIdx.find(prefixMod);
            if (it != firstIdx.end()) {
                ans = max(ans, i - it->second);
            } else {
                firstIdx[prefixMod] = i;
            }
        }
        return ans;
    }
};

Process a sequence of operations on a number line. Each operation is one of:

  • [1, x] — place an obstacle at coordinate x.
  • [2, x, size] — attempt to place a block of length size with its right end at x (covering the half-open segment [x - size, x)). Append '1' to the result if the segment contains no obstacle (success), otherwise append '0'.

Return the concatenated result string.

Constraints

  • 1 ≤ operations.length ≤ 10⁵
operations = [[1, 2],
 [1, 5],
 [2, 5, 2],
 [2, 6, 3],
 [2, 2, 1],
 [2, 3, 2]]
solution(operations) = "1010"

解法

用有序集合存障碍坐标。放置查询 [2, x, size] 二分找 ≥ x - size 的最小障碍；若存在且 < x 则与障碍相交输出 '0'，否则输出 '1'。复杂度 O((I + Q) log I)，I 为障碍数。

from sortedcontainers import SortedList

def solution(operations: list[list[int]]) -> str:
    obstacles = SortedList()
    out = []

    for op in operations:
        if op[0] == 1:
            obstacles.add(op[1])           # O(log n) insert
        else:
            x, size = op[1], op[2]
            l, r = x - size, x - 1          # query closed interval [l, r]
            idx = obstacles.bisect_left(l)  # first obstacle index >= l
            if idx < len(obstacles) and obstacles[idx] <= r:
                out.append('0')
            else:
                out.append('1')
    return ''.join(out)
import java.util.TreeSet;

class Solution {
    String solution(int[][] operations) {
        TreeSet<Integer> obstacles = new TreeSet<>();
        StringBuilder sb = new StringBuilder();

        for (int[] op : operations) {
            if (op[0] == 1) {
                obstacles.add(op[1]);
            } else {
                int x = op[1], size = op[2];
                int l = x - size, r = x - 1;
                Integer ceil = obstacles.ceiling(l);
                if (ceil != null && ceil <= r) {
                    sb.append('0');
                } else {
                    sb.append('1');
                }
            }
        }
        return sb.toString();
    }
}
#include <set>
#include <string>
class Solution {
public:
    string solution(vector<vector<int>>& operations) {
        set<int> obstacles;
        string out;

        for (auto& op : operations) {
            if (op[0] == 1) {
                obstacles.insert(op[1]);
            } else {
                int x = op[1], size = op[2];
                int l = x - size, r = x - 1;
                auto it = obstacles.lower_bound(l);
                if (it != obstacles.end() && *it <= r) {
                    out.push_back('0');
                } else {
                    out.push_back('1');
                }
            }
        }
        return out;
    }
};

Given a recording of typed characters, count the number of times the underlying letter changes between consecutive characters (case-insensitive). In other words, lowercase the entire sequence and count adjacent positions where recording[i] differs from recording[i-1].

Constraints

  • 1 ≤ recording.length ≤ 1000
solution(['W', 'w', 'a', 'A', 'b', 'b']) = 2
solution(['w', 'W', 'a', 'W', 'a']) = 3

解法

单次遍历：每字符转小写，与上一个不同就计数加 1。复杂度 O(n)。

def solution(recording: list[str]) -> int:
    if len(recording) <= 1:
        return 0
    count = 0
    prev = recording[0].lower()
    for i in range(1, len(recording)):
        cur = recording[i].lower()
        if cur != prev:
            count += 1
            prev = cur
    return count
class Solution {
    int solution(char[] recording) {
        if (recording.length <= 1) return 0;
        int count = 0;
        char prev = Character.toLowerCase(recording[0]);
        for (int i = 1; i < recording.length; i++) {
            char cur = Character.toLowerCase(recording[i]);
            if (cur != prev) {
                count++;
                prev = cur;
            }
        }
        return count;
    }
}
#include <cctype>
class Solution {
public:
    int solution(vector<char>& recording) {
        if (recording.size() <= 1) return 0;
        int count = 0;
        char prev = tolower(recording[0]);
        for (size_t i = 1; i < recording.size(); i++) {
            char cur = tolower(recording[i]);
            if (cur != prev) {
                count++;
                prev = cur;
            }
        }
        return count;
    }
};
Pro 会员

解锁剩余 66 道 OA 真题

开通后立即解锁完整题面 + Python / Java / C++ 三语题解。 全站 165 家公司 · 1000+ 道 OA · 月度更新。

开通会员已是会员，去登录

LinkedIn

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

Airbnb

Airbnb 真实 OA 题库，三语题解 (Python / Java / C++)。