登录
OAmaster

You are given an integer length representing the length of a balloon queue (indexed from 0 to length - 1) and an array queries. Initially, the balloon queue is empty (all positions are uncolored or considered empty). Each query[i] = (index, color) means you color the balloon at position index with the given color. After processing each query, you need to count the number of adjacent pairs of balloons that have the same color and record that number. At the end, you should return an array containing the count after each query — the length of the result array is the same as the number of queries.

Example 1

Input:

length = 5
queries = [[0, 1], [1, 1], [2, 1], [1, 3]]

Output:

[0, 1, 2, 0]

Explanation: Initial state: _ _ _ _ _ (empty) Process each query:

  • (0, 1): 1 _ _ _ _ → 0 adjacent same-color pairs
  • (1, 1): 1 1 _ _ _ → 1 pair (positions 0 and 1)
  • (2, 1): 1 1 1 _ _ → 2 pairs (0-1 and 1-2)
  • (1, 3): 1 3 1 _ _ → 0 pairs Final Output: [0, 1, 2, 0]

解法

维护数组和当前相邻同色对计数 pairs。每次涂色前先看 (idx, idx-1) 和 (idx, idx+1) 之前的"是否同色"贡献，撤销旧贡献后涂上新色再加新贡献。时间复杂度 O(Q)。

from typing import List

def balloonColorPairs(length: int, queries: List[List[int]]) -> List[int]:
    arr = [0] * length
    pairs = 0
    res = []
    for idx, color in queries:
        # remove old contributions
        if arr[idx] != 0:
            if idx - 1 >= 0 and arr[idx - 1] == arr[idx]: pairs -= 1
            if idx + 1 < length and arr[idx + 1] == arr[idx]: pairs -= 1
        arr[idx] = color
        if idx - 1 >= 0 and arr[idx - 1] == color and arr[idx - 1] != 0: pairs += 1
        if idx + 1 < length and arr[idx + 1] == color and arr[idx + 1] != 0: pairs += 1
        res.append(pairs)
    return res
class Solution {
    int[] balloonColorPairs(int length, int[][] queries) {
        int[] arr = new int[length];
        int pairs = 0;
        int[] res = new int[queries.length];
        for (int q = 0; q < queries.length; q++) {
            int idx = queries[q][0], color = queries[q][1];
            if (arr[idx] != 0) {
                if (idx - 1 >= 0 && arr[idx - 1] == arr[idx]) pairs--;
                if (idx + 1 < length && arr[idx + 1] == arr[idx]) pairs--;
            }
            arr[idx] = color;
            if (idx - 1 >= 0 && arr[idx - 1] == color && arr[idx - 1] != 0) pairs++;
            if (idx + 1 < length && arr[idx + 1] == color && arr[idx + 1] != 0) pairs++;
            res[q] = pairs;
        }
        return res;
    }
}
class Solution {
public:
    vector<int> balloonColorPairs(int length, vector<vector<int>>& queries) {
        vector<int> arr(length, 0);
        int pairs = 0;
        vector<int> res;
        for (auto& q : queries) {
            int idx = q[0], color = q[1];
            if (arr[idx] != 0) {
                if (idx - 1 >= 0 && arr[idx - 1] == arr[idx]) pairs--;
                if (idx + 1 < length && arr[idx + 1] == arr[idx]) pairs--;
            }
            arr[idx] = color;
            if (idx - 1 >= 0 && arr[idx - 1] == color && arr[idx - 1] != 0) pairs++;
            if (idx + 1 < length && arr[idx + 1] == color && arr[idx + 1] != 0) pairs++;
            res.push_back(pairs);
        }
        return res;
    }
};

You are given an array forest and the bird's starting position bird. forest[i] represents the length of the stick at position i. If forest[i] == 0, it means there is no stick at position i. The bird's starting position bird will always be an index where there is no stick (forest[bird] == 0). The bird follows this process: Starting from the initial position, the bird flies right until it finds the first stick. It picks up the stick and brings it back to the starting position. Next, the bird flies left until it finds the next stick. It picks up that stick and brings it back to the starting position. The bird repeats this process: alternating right and left until it collects sticks with a total length of at least 100. You need to output the indices of the sticks that the bird picks up, in the order they are collected. Note: There will always be a stick available in the current flying direction. No edge cases like "flying right and finding no sticks" will occur.

Example 1

Input:

forest = [0, 50, 0, 30, 0, 25]
bird = 2

Output:

[3, 1, 5]

Explanation: Pls ignore the explanation in the source image.

解法

交替方向扫描：从 bird 位置开始，先右后左反复；每次找到第一个 forest[i] > 0 的位置，记录索引并把该位置置 0、累加 totalLength；当 totalLength ≥ 100 时停止。时间复杂度 O(n²) 最坏，n 为数组长度。

from typing import List

def collectSticks(forest: List[int], bird: int) -> List[int]:
    res = []
    total = 0
    direction = 1  # 1: right, -1: left
    while total < 100:
        i = bird + direction
        while 0 <= i < len(forest) and forest[i] == 0:
            i += direction
        if not (0 <= i < len(forest)):
            break
        res.append(i)
        total += forest[i]
        forest[i] = 0
        direction = -direction
    return res
class Solution {
    int[] collectSticks(int[] forest, int bird) {
        List<Integer> res = new ArrayList<>();
        int total = 0, direction = 1;
        while (total < 100) {
            int i = bird + direction;
            while (i >= 0 && i < forest.length && forest[i] == 0) i += direction;
            if (i < 0 || i >= forest.length) break;
            res.add(i);
            total += forest[i];
            forest[i] = 0;
            direction = -direction;
        }
        int[] out = new int[res.size()];
        for (int k = 0; k < res.size(); k++) out[k] = res.get(k);
        return out;
    }
}
class Solution {
public:
    vector<int> collectSticks(vector<int>& forest, int bird) {
        vector<int> res;
        int total = 0, direction = 1;
        while (total < 100) {
            int i = bird + direction;
            while (i >= 0 && i < (int)forest.size() && forest[i] == 0) i += direction;
            if (i < 0 || i >= (int)forest.size()) break;
            res.push_back(i);
            total += forest[i];
            forest[i] = 0;
            direction = -direction;
        }
        return res;
    }
};

You are given a 2D array grid, where grid[i][j] represents the color of the bubble at position (i, j). You are also given an operations array, which is a sequence of coordinates indicating where to pop bubbles. Rules: If you pop a bubble at a position with value 0 (meaning no bubble), nothing happens. If you pop a bubble, check its top-left, bottom-left, top-right, and bottom-right diagonal neighbors: If the neighbor is within bounds, has a bubble (non-zero), and the color is the same as the popped bubble, that neighbor also pops. After popping, gravity applies: bubbles above empty cells fall down to fill the empty spaces directly below them. Perform all operations in order and return the final grid.

Example 1

Input:

grid = [[1, 2, 3], [6, 1, 2], [1, 2, 5]]
operations = [[1, 1], [1, 2]]

Output:

[[0, 0, 0], [0, 0, 3], [6, 2, 5]]

Explanation: Step 1: Pop bubble at (1, 1)

  • Pops the bubble itself
  • Pops diagonally connected bubble (0, 0) because it has the same color 1 Apply gravity: [ [0, 0, 3], [0, 2, 2], [6, 2, 5] ] Step 2: Pop bubble at (1, 2)
  • Pops the bubble itself
  • Pops diagonal (0, 1) because it's 2
  • Pops diagonal (2, 1) because it's also 2 Apply gravity: [ [0, 0, 0], [0, 0, 3], [6, 2, 5] ] Final Output: [ [0, 0, 0], [0, 0, 3], [6, 2, 5] ]

解法

每次操作：若位置非零，BFS 扩展同色对角邻居全部置 0；之后按列做"重力"：每列从下往上将非零值压到底。时间复杂度 O(K · MN)。

from typing import List
from collections import deque

def popBubbles(grid: List[List[int]], operations: List[List[int]]) -> List[List[int]]:
    m, n = len(grid), len(grid[0])
    diags = [(-1, -1), (-1, 1), (1, -1), (1, 1)]
    for r, c in operations:
        if grid[r][c] == 0:
            continue
        color = grid[r][c]
        q = deque([(r, c)])
        grid[r][c] = 0
        while q:
            i, j = q.popleft()
            for di, dj in diags:
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == color:
                    grid[ni][nj] = 0
                    q.append((ni, nj))
        # gravity
        for c2 in range(n):
            col = [grid[r2][c2] for r2 in range(m) if grid[r2][c2] != 0]
            col = [0] * (m - len(col)) + col
            for r2 in range(m): grid[r2][c2] = col[r2]
    return grid
class Solution {
    int[][] popBubbles(int[][] grid, int[][] operations) {
        int m = grid.length, n = grid[0].length;
        int[][] diags = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
        for (int[] op : operations) {
            int r = op[0], c = op[1];
            if (grid[r][c] == 0) continue;
            int color = grid[r][c];
            Deque<int[]> q = new ArrayDeque<>();
            q.add(new int[]{r, c});
            grid[r][c] = 0;
            while (!q.isEmpty()) {
                int[] p = q.poll();
                for (int[] d : diags) {
                    int ni = p[0] + d[0], nj = p[1] + d[1];
                    if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == color) {
                        grid[ni][nj] = 0;
                        q.add(new int[]{ni, nj});
                    }
                }
            }
            for (int c2 = 0; c2 < n; c2++) {
                List<Integer> col = new ArrayList<>();
                for (int r2 = 0; r2 < m; r2++) if (grid[r2][c2] != 0) col.add(grid[r2][c2]);
                int k = m - col.size();
                for (int r2 = 0; r2 < m; r2++) grid[r2][c2] = r2 < k ? 0 : col.get(r2 - k);
            }
        }
        return grid;
    }
}
class Solution {
public:
    vector<vector<int>> popBubbles(vector<vector<int>>& grid, vector<vector<int>>& operations) {
        int m = grid.size(), n = grid[0].size();
        int diags[4][2] = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
        for (auto& op : operations) {
            int r = op[0], c = op[1];
            if (grid[r][c] == 0) continue;
            int color = grid[r][c];
            queue<pair<int,int>> q;
            q.push({r, c});
            grid[r][c] = 0;
            while (!q.empty()) {
                auto [i, j] = q.front(); q.pop();
                for (auto& d : diags) {
                    int ni = i + d[0], nj = j + d[1];
                    if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == color) {
                        grid[ni][nj] = 0;
                        q.push({ni, nj});
                    }
                }
            }
            for (int c2 = 0; c2 < n; c2++) {
                vector<int> col;
                for (int r2 = 0; r2 < m; r2++) if (grid[r2][c2] != 0) col.push_back(grid[r2][c2]);
                int k = m - col.size();
                for (int r2 = 0; r2 < m; r2++) grid[r2][c2] = r2 < k ? 0 : col[r2 - k];
            }
        }
        return grid;
    }
};

DoorDash

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

Pinterest

Pinterest 真实 OA 题库，三道题(字符串 + ML 经典算法实现)。