Images are stored as grids of 0/1. A connected region is a set of cells containing 1 that are reachable from each other by moving row or column through adjacent 1-cells. Given two grids of the same size, count the number of regions in the second grid that match (occupy the exact same set of cell positions as) some region in the first grid.

Example

grid1 = [[1,1,1],[1,0,0],[1,0,0]]
grid2 = [[1,1,1],[1,0,0],[1,0,1]]
Answer: 1
Grid1 has one region {(0,0),(0,1),(0,2),(1,0),(2,0)}.
Grid2 has two regions: that same set plus {(2,2)}. Only the first matches.

解法

对两张网格分别做 BFS/DFS 提取连通块的坐标集合；把每个集合规范化为排序后的元组/字符串作 key；统计 grid2 中 key 出现在 grid1 集合里的连通块数。复杂度 O(N*M)。

def countMatchingRegions(grid1, grid2):
    def regions(g):
        n, m = len(g), len(g[0])
        seen = [[False]*m for _ in range(n)]
        out = []
        for i in range(n):
            for j in range(m):
                if g[i][j] == 1 and not seen[i][j]:
                    region, stack = set(), [(i, j)]
                    while stack:
                        x, y = stack.pop()
                        if 0 <= x < n and 0 <= y < m and g[x][y] == 1 and not seen[x][y]:
                            seen[x][y] = True
                            region.add((x, y))
                            stack += [(x+1,y),(x-1,y),(x,y+1),(x,y-1)]
                    out.append(frozenset(region))
        return out
    r1 = set(regions(grid1))
    return sum(1 for r in regions(grid2) if r in r1)

class Solution {
    int n, m;
    int[][] g;
    boolean[][] seen;

    Set<String> collect(int[][] grid) {
        g = grid; n = g.length; m = g[0].length;
        seen = new boolean[n][m];
        Set<String> regions = new HashSet<>();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (g[i][j] == 1 && !seen[i][j]) {
                    List<int[]> cells = new ArrayList<>();
                    Deque<int[]> st = new ArrayDeque<>();
                    st.push(new int[]{i, j});
                    while (!st.isEmpty()) {
                        int[] p = st.pop();
                        int x = p[0], y = p[1];
                        if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] != 1 || seen[x][y]) continue;
                        seen[x][y] = true;
                        cells.add(new int[]{x, y});
                        st.push(new int[]{x+1, y}); st.push(new int[]{x-1, y});
                        st.push(new int[]{x, y+1}); st.push(new int[]{x, y-1});
                    }
                    cells.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
                    StringBuilder sb = new StringBuilder();
                    for (int[] c : cells) sb.append(c[0]).append(',').append(c[1]).append(';');
                    regions.add(sb.toString());
                }
        return regions;
    }

    int countMatchingRegions(int[][] g1, int[][] g2) {
        Set<String> a = collect(g1), b = collect(g2);
        int cnt = 0;
        for (String r : b) if (a.contains(r)) cnt++;
        return cnt;
    }
}

set<string> collect(vector<vector<int>>& g) {
 int n = g.size(), m = g[0].size();
 vector<vector<int>> seen(n, vector<int>(m, 0));
 set<string> regions;
 int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
 for (int i = 0; i < n; i++)
 for (int j = 0; j < m; j++)
 if (g[i][j] == 1 && !seen[i][j]) {
 vector<pair<int,int>> cells;
 stack<pair<int,int>> st;
 st.push({i, j});
 while (!st.empty()) {
 auto [x, y] = st.top(); st.pop();
 if (x < 0 || x >= n || y < 0 || y >= m || g[x][y] != 1 || seen[x][y]) continue;
 seen[x][y] = 1;
 cells.push_back({x, y});
 for (int d = 0; d < 4; d++) st.push({x + dx[d], y + dy[d]});
 }
 sort(cells.begin(), cells.end());
 string key;
 for (auto& [x, y] : cells) key += to_string(x) + "," + to_string(y) + ";";
 regions.insert(key);
 }
 return regions;
}

int countMatchingRegions(vector<vector<int>>& g1, vector<vector<int>>& g2) {
 auto a = collect(g1), b = collect(g2);
 int cnt = 0;
 for (auto& r : b) if (a.count(r)) cnt++;
 return cnt;
}

A biological researcher is examining bacteria interactions, where some bacteria are poisonous to others. The samples are arranged consecutively in a row from 1 to n. Given a list detailing which bacteria are poisonous to others, determine the number of intervals (contiguous, no reorder) within the row that contain only samples capable of coexisting.

Example

n = 3, allergic = [2, 1, 3], poisonous = [3, 3, 1]
Answer: 4
Conflicts: {2,3}, {1,3}, {1,3}. Valid intervals: (1), (2), (3), (1,2).

解法

滑动窗口：枚举右端 r，若 r 的任一冲突菌 x 在 [l, r-1] 且 x >= l，则把 l 跳到 x + 1；累加窗口长度 r - l + 1。复杂度 O(n + m)。

def bioHazard(n, allergic, poisonous):
    conflict = [[] for _ in range(n + 1)]
    for a, p in zip(allergic, poisonous):
        conflict[a].append(p)
        conflict[p].append(a)
    ans = 0
    l = 1
    in_window = [False] * (n + 1)
    for r in range(1, n + 1):
        for x in conflict[r]:
            if in_window[x] and x >= l:
                while l <= x:
                    in_window[l] = False
                    l += 1
        in_window[r] = True
        ans += r - l + 1
    return ans

class Solution {
    static long bioHazard(int n, int[] allergic, int[] poisonous) {
        List<List<Integer>> conflict = new ArrayList<>();
        for (int i = 0; i <= n; i++) conflict.add(new ArrayList<>());
        for (int i = 0; i < allergic.length; i++) {
            conflict.get(allergic[i]).add(poisonous[i]);
            conflict.get(poisonous[i]).add(allergic[i]);
        }
        long ans = 0;
        int l = 1;
        boolean[] inWin = new boolean[n + 1];
        for (int r = 1; r <= n; r++) {
            for (int x : conflict.get(r)) {
                if (inWin[x] && x >= l) {
                    while (l <= x) { inWin[l] = false; l++; }
                }
            }
            inWin[r] = true;
            ans += r - l + 1;
        }
        return ans;
    }
}

long long bioHazard(int n, vector<int>& allergic, vector<int>& poisonous) {
 vector<vector<int>> conflict(n + 1);
 for (size_t i = 0; i < allergic.size(); i++) {
 conflict[allergic[i]].push_back(poisonous[i]);
 conflict[poisonous[i]].push_back(allergic[i]);
 }
 long long ans = 0;
 int l = 1;
 vector<int> inWin(n + 1, 0);
 for (int r = 1; r <= n; r++) {
 for (int x : conflict[r]) {
 if (inWin[x] && x >= l) {
 while (l <= x) { inWin[l] = 0; l++; }
 }
 }
 inWin[r] = 1;
 ans += r - l + 1;
 }
 return ans;
}

Complete the function below. The function receives the full standard input as a single string and returns the exact standard output lines for a chat-event tracker. Implement two operations for tracking chat events:

• processEvent(userId, chatId, timestamp): record that userId had an event in chatId at timestamp.
• getCount(userId, chatId, timestamp): return how many events for that exact (userId, chatId) pair occurred in the last 15 minutes, inclusive of the query timestamp and exclusive of events older than timestamp - 15 minutes. In this command-based version, each line is either EVENT userId chatId timestamp or COUNT userId chatId timestamp. Return one output line for each COUNT command. Function Description Complete solveChatEventCounts. It has one parameter, String input, containing newline-separated commands. Return the stdout payload as an array of lines, without trailing newline characters.

Constraints

Timestamps are integer minutes and commands are processed in input order. Counts are keyed by both user id and chat id.

Example 1

Input:

input = "EVENT u1 c1 0\nEVENT u1 c1 10\nEVENT u1 c2 12\nCOUNT u1 c1 14\nCOUNT u1 c1 16\nEVENT u1 c1 20\nCOUNT u1 c1 25\nCOUNT u1 c2 25"

Output:

["2","1","2","1"]

Explanation: At timestamp 16, the event at minute 0 is older than 15 minutes and is not counted.

解法

为每个 (userId, chatId) 维护一个有序时间戳列表。EVENT 直接 append；COUNT 时用二分找到 ≥ ts - 15 的下标，结果 = 列表长度 - 下标。时间 O(E + Q log E)。

from bisect import bisect_left
from collections import defaultdict
from typing import List

def solveChatEventCounts(input: str) -> List[str]:
    store = defaultdict(list)
    out = []
    for line in input.split('\n'):
        if not line:
            continue
        parts = line.split()
        op, user, chat = parts[0], parts[1], parts[2]
        ts = int(parts[3])
        key = (user, chat)
        if op == 'EVENT':
            store[key].append(ts)
        else:  # COUNT
            arr = store[key]
            lo = ts - 15
            idx = bisect_left(arr, lo)
            # 同时 ≤ ts
            hi = bisect_left(arr, ts + 1)
            out.append(str(hi - idx))
    return out

import java.util.*;

class Solution {
    String[] solveChatEventCounts(String input) {
        Map<String, List<Integer>> store = new HashMap<>();
        List<String> out = new ArrayList<>();
        for (String line : input.split("\n")) {
            if (line.isEmpty()) continue;
            String[] p = line.split(" ");
            String op = p[0], key = p[1] + "|" + p[2];
            int ts = Integer.parseInt(p[3]);
            store.computeIfAbsent(key, k -> new ArrayList<>());
            if (op.equals("EVENT")) {
                store.get(key).add(ts);
            } else {
                List<Integer> arr = store.get(key);
                int lo = lowerBound(arr, ts - 15);
                int hi = lowerBound(arr, ts + 1);
                out.add(String.valueOf(hi - lo));
            }
        }
        return out.toArray(new String[0]);
    }
    int lowerBound(List<Integer> a, int target) {
        int lo = 0, hi = a.size();
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (a.get(mid) < target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}

class Solution {
public:
    vector<string> solveChatEventCounts(string input) {
        unordered_map<string, vector<int>> store;
        vector<string> out;
        size_t pos = 0;
        while (pos < input.size()) {
            size_t end = input.find('\n', pos);
            if (end == string::npos) end = input.size();
            string line = input.substr(pos, end - pos);
            pos = end + 1;
            if (line.empty()) continue;
            // parse tokens
            stringstream ss(line);
            string op, user, chat;
            int ts;
            ss >> op >> user >> chat >> ts;
            string key = user + "|" + chat;
            auto& arr = store[key];
            if (op == "EVENT") {
                arr.push_back(ts);
            } else {
                auto lo = lower_bound(arr.begin(), arr.end(), ts - 15);
                auto hi = lower_bound(arr.begin(), arr.end(), ts + 1);
                out.push_back(to_string(hi - lo));
            }
        }
        return out;
    }
};

Implement a small in-memory chat application that supports multiple channels and extensible bots. Each channel maintains its own message history and any bot state associated with that channel. The design should allow new bot types to be added without modifying the core chat logic. For this problem, process a list of commands:

• REGISTER botName ...: register one or more bots
• SEND channelId userId text...: append the user message to that channel and then append any bot replies triggered by the message
• PRINT channelId: emit the full message history for that channel in order Assume two example bots exist: EchoBot replies with the same text it receives, and HelpBot replies with a help string when the message text is help. Function Description Complete the function runChatAppCommands in the editor below. runChatAppCommands has the following parameter:
• String[] commands: the commands to process in order Returns String[]: the lines produced by all PRINT commands, in order.

Constraints

• 1 ≤ commands.length ≤ 10⁵
• The number of channels is at most 10⁴.
• The number of registered bots is at most 10².
• Commands arrive sequentially; no concurrency handling is required.

Given n and a list of pairs of numbers that a

Example 1

Input:

n = 4
pairs = [[1, 3]]

Output:

8

Explanation: The valid sequences are (1),(2),(3),(4),(1,2),(2,3),(3,4),(2,3,4). Sequences (1,2,3) and (1,2,3,4) are invalid as they contain the forbidden pair (1,3).

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem. Grid Infection with Recovery After D Days (Become Immune) Building on (2), add recovery: Each infected cell 'X' recovers after D days since it got infected and becomes immune 'I' at the end of that day. Immune 'I' can never be infected and does not infect others. A healthy '.' becomes infected 'X' at the end of a day if it has at least T infected 'X' neighbors among its 8 neighbors. Return the number of days until the grid becomes stable, defined as: there are no infected 'X' cells left. Updates are synchronous. You must track infection age per cell. Example Input 3 3 1 1 .X. ... Output 2 Function Description Complete solveGridInfectionRecoveryAfterDays. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.

Constraints

Use the limits and requirements stated in the prompt.

Example 1

Input:

input = "3 3\n1 1\n.X.\n...\n..."

Output:

["2"]

Explanation: The returned string array must match the expected standard output lines for the sample input.

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem. Grid Infection Spread Until Stable (8-direction, threshold) You are given an m×n grid grid where each cell is either infected 'X' or healthy '.'. Each day, perform a synchronous update: for every healthy cell '.', count the number of infected 'X' cells among its 8 neighbors (4-directional + 4 diagonals). If the count is ≥ T, that cell becomes infected 'X' at the end of the day. Infected cells never recover or disappear. Return the number of days until the grid becomes stable (i.e., after some day’s update, no new infections occur). Notes: Updates are synchronous: changes on day d depend only on the state at the start of day d. You may assume 1 ≤ m,n ≤ 200 and 0 ≤ T ≤ 8. Examples: grid=["...", ".X.", "..."], T=1 → 1 same grid, T=2 → 0 Example Input 3 3 1 ... .X. ... Output 1 Function Description Complete solveGridInfectionSpreadUntilStable. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.

Constraints

Use the limits and requirements stated in the prompt.

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem. Extending the previous problem, the grid may also contain immune cells 'I': 'I' can never be infected. 'I' does not infect others (it is not counted as infected). Each day (synchronously), any healthy '.' cell with at least T infected 'X' neighbors among its 8 neighbors becomes 'X'. 'I' always stays 'I'. Return the number of days until the grid becomes stable (no new infections occur). Example Input 3 3 1 I.. .X. ... Output 1 Function Description Complete solveGridInfectionWithImmuneCells. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.

Constraints

Use the limits and requirements stated in the prompt.

Example 1

Input:

input = "3 3\n1\nI..\n.X.\n..."

Output:

["1"]

Explanation: The returned string array must match the expected standard output lines for the sample input.

Given a starting IPv4 address startIp and a positive integer count, return the minimum set of CIDR blocks that exactly covers the count consecutive IPv4 addresses starting at startIp. Each CIDR block must be written in the form a.b.c.d/prefix. The returned blocks must cover the range exactly and use the minimum possible number of blocks. You may assume the input is a valid IPv4 address and that the range stays within the IPv4 space. Function Description Complete the function ipRangeToCidrBlocks in the editor below. ipRangeToCidrBlocks has the following parameters:

• String startIp: the first IPv4 address in the range
• long count: the number of consecutive IPv4 addresses to cover Returns String[]: the minimum CIDR cover for the range.

Constraints

• 1 ≤ count ≤ 2³²
• startIp is a valid IPv4 address.
• The answer must cover exactly the requested range using the minimum number of blocks.

Example 1

Input:

startIp = "0.0.0.0"
count = 1

Output:

["0.0.0.0/32"]

Explanation: A single IPv4 address is represented by a /32 CIDR block.

Example 2

Input:

startIp = "0.0.0.0"
count = 256

Output:

["0.0.0.0/24"]

Explanation: The range from 0.0.0.0 through 0.0.0.255 is exactly one /24 block.

We have a number line and there are walls provided at coordinates x+0.5, where x is any integer. Each wall has some thickness to it. The player starts from x = 0 and every time they take a step to the left or right, they are exerting energy of 1 unit. However, when they go through a wall of thickness t, they are exerting energy of t units. You are also given the maximum energy you can spend in the whole simulation. The main goal of this algorithm is to return the maximum number of walls you can hit. (After you hit the wall it still exists so you can keep going back and forth to hit the same wall). You can also go left and right at any point in time. NOTE: You always start from x - 0 :) Function Description Complete the function maximizeTheHits in the editor. maximizeTheHits has the following parameters:

• 1. int[] walls: an array of integers representing the positions of the walls
• 2. int[] thickness: an array of integers representing the thickness of each wall
• 3. int energy: the maximum energy you can spend Returns int: the maximum number of walls you can hit