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 ansclass 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 thatuserIdhad an event inchatIdattimestamp.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 thantimestamp - 15minutes. In this command-based version, each line is eitherEVENT userId chatId timestamporCOUNT userId chatId timestamp. Return one output line for eachCOUNTcommand. Function Description CompletesolveChatEventCounts. 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 outimport 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;
}
};