欢迎大家加QQ群：623375442。
100378. Design Neighbor Sum Service
给你一个 n x n 的二维数组 grid，它包含范围 [0, n2 - 1] 内的不重复元素。
实现 neighborSum 类：
- neighborSum(int [][]grid) 初始化对象。
- int adjacentSum(int value) 返回在 grid 中与 value 相邻的元素之和，相邻指的是与 value 在上、左、右或下的元素。
- int diagonalSum(int value) 返回在 grid 中与 value 对角线相邻的元素之和，对角线相邻指的是与 value 在左上、右上、左下或右下的元素。
测试样例：
输入：["neighborSum", "adjacentSum", "adjacentSum", "diagonalSum", "diagonalSum"]
输出：[[[[0, 1, 2], [3, 4, 5], [6, 7, 8]]], [1], [4], [4], [8]]
解释：[null, 6, 16, 16, 4]
解答：题目范围很小，直接暴力搜索和计算。
class neighborSum {
private int[][] grid;
private static final int[][] ad = {{-1,0},{1,0},{0,-1},{0,1}};
private static final int[][] di = {{-1,1},{-1,-1},{1,1},{1,-1}};
public neighborSum(int[][] grid) {
this.grid = grid;
}
public int adjacentSum(int value) {
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid.length; ++j) {
if (grid[i][j] == value) {
int res = 0;
for (int[] mv : ad) {
int xt = i + mv[0], yt = j + mv[1];
if (isInScope(xt, yt)) {
res += grid[xt][yt];
}
}
return res;
}
}
}
return -1;
}
public int diagonalSum(int value) {
for (int i = 0; i < grid.length; ++i) {
for (int j = 0; j < grid.length; ++j) {
if (grid[i][j] == value) {
int res = 0;
for (int[] mv : di) {
int xt = i + mv[0], yt = j + mv[1];
if (isInScope(xt, yt)) {
res += grid[xt][yt];
}
}
return res;
}
}
}
return -1;
}
private boolean isInScope(int x, int y) {
return x >= 0 && x < grid.length && y >= 0 && y < grid.length;
}
}100379. Shortest Distance After Road Addition Queries I
给你一个整数 n 和一个二维整数数组 queries。
有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 <= i < n - 1）。
queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后，你需要找到从城市 0 到城市 n - 1 的最短路径的长度。
返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的长度。
测试样例：
输入：n = 5, queries = [[2, 4], [0, 2], [0, 4]]
输出：[3, 2, 1]
解释：新增一条从 2 到 4 的道路后，从 0 到 4 的最短路径长度为 3。新增一条从 0 到 2 的道路后，从 0 到 4 的最短路径长度为 2。新增一条从 0 到 4 的道路后，从 0 到 4 的最短路径长度为 1。
解答：这题和第三题不太一样。可以记录所有路径信息，利用DP来记录最短距离。
class Solution {
public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
boolean[][] isConnect = new boolean[n][n];
for (int i = 0; i < n - 1; ++i) {
isConnect[i][i + 1] = true;
}
int[] res = new int[queries.length];
int[] minimum = new int[n];
for (int i = 0; i < n; ++i) {
minimum[i] = i;
}
for (int i = 0; i < queries.length; ++i) {
isConnect[queries[i][0]][queries[i][1]] = true;
for (int j = 0; j < n; ++j) {
for (int k = 0; k < j; ++k) {
if (isConnect[k][j]) {
minimum[j] = Math.min(minimum[j], minimum[k] + 1);
}
}
}
res[i] = minimum[n - 1];
}
return res;
}
}100376. Shortest Distance After Road Addition Queries II
给你一个整数 n 和一个二维整数数组 queries。
有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 <= i < n - 1）。
queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后，你需要找到从城市 0 到城市 n - 1 的最短路径的长度。
所有查询中不会存在两个查询都满足 queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]。
返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的长度。
测试样例：
输入：n = 5, queries = [[2, 4], [0, 2], [0, 4]]
输出：[3, 2, 1]
解释：新增一条从 2 到 4 的道路后，从 0 到 4 的最短路径长度为 3。新增一条从 0 到 2 的道路后，从 0 到 4 的最短路径长度为 2。新增一条从 0 到 4 的道路后，从 0 到 4 的最短路径长度为 1。
解答：有一个很重要的地方，queries[i][0] < queries[j][0] < queries[i][1] < queries[j][1]。这题就简单了很多。类似区间组合。
class Solution {
public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
int[] res = new int[queries.length];
TreeSet<int[]> set = new TreeSet<>((a, b) -> (Integer.compare(a[0], b[0])));
int cur = n - 1;
for (int i = 0; i < queries.length; ++i) {
int[] floor = set.floor(queries[i]);
// 查看区间merge
if (floor != null && floor[1] >= queries[i][1]) {
res[i] = cur;
continue;
}
// 查看高区间merge
int[] higher = set.ceiling(queries[i]);
while (higher != null) {
if (higher[1] <= queries[i][1]) {
cur += higher[1] - higher[0] - 1;
set.remove(higher);
higher = set.higher(queries[i]);
} else {
break;
}
}
cur -= queries[i][1] - queries[i][0] - 1;
set.add(queries[i]);
res[i] = cur;
}
return res;
}
}100388. Alternating Groups III
给你一个整数数组 colors 和一个二维整数数组 queries 。colors表示一个由红色和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i] ：
- colors[i] == 0 表示第 i 块瓷砖的颜色是 红色 。
- colors[i] == 1 表示第 i 块瓷砖的颜色是 蓝色 。
环中连续若干块瓷砖的颜色如果是 交替 颜色（也就是说这组瓷砖中除了第一块和最后一块瓷砖以外，中间瓷砖的颜色与它 左边 和 右边 的颜色都不同），那么它被称为一个 交替组。
你需要处理两种类型的查询：
- queries[i] = [1, sizei]，确定大小为sizei的 交替组 的数量。
- queries[i] = [2, indexi, colori]，将colors[indexi]更改为colori。
返回数组 answer，数组中按顺序包含第一种类型查询的结果。
注意 ，由于 colors 表示一个 环 ，第一块 瓷砖和 最后一块 瓷砖是相邻的。
测试样例：
输入：colors = [0,1,1,0,1], queries = [[2,1,0],[1,4]]
输出：[2]
解释：第一次查询：将 colors[1] 改为 0。第二次查询：统计大小为 4 的交替组的数量：
解答：来不及做了，感觉用线段树可以过这题。
补充一下题解。这题就是用线段树。我们首先把整个数字相邻取一下异或（第0位和最后一位）。比如例子里面就会变成[1,1,0,1,1]。连续1的子序列长度是4 * 1，那么长度为4的交替组有2个，长度为5的交替组有1个。
然后变化一次，会变成[1,0,1,1,1]。连续1的子序列长度是4 * 1，那么长度为4的交替组有2个，长度为5的交替组有1个。
所以我们利用线段树记录各个连续1子序列的出现次数。每次数组发生变化之后，也相应修改一下异或数组，并且查询连续1数组长度的变化情况。
class Solution {
class SegmentTree {
int[] tree1, tree2;
int n;
public SegmentTree(int _n) {
n = _n;
tree1 = new int[n * 2];
tree2 = new int[n * 2];
}
void update(int pos, int val) {
pos += n;
tree1[pos] += val;
tree2[pos] += (pos - n) * val;
while (pos > 0) {
int left = pos;
int right = pos;
if (pos % 2 == 0) {
right = pos + 1;
} else {
left = pos - 1;
}
tree1[pos / 2] = tree1[left] + tree1[right];
tree2[pos / 2] = tree2[left] + tree2[right];
pos /= 2;
}
}
public int[] sumRange(int l) {
l += n;
int r = 2 * n - 1;
int[] sum = {0, 0};
while (l <= r) {
if ((l % 2) == 1) {
sum[0] += tree1[l];
sum[1] += tree2[l];
l++;
}
if ((r % 2) == 0) {
sum[0] += tree1[r];
sum[1] += tree2[r];
r--;
}
l /= 2;
r /= 2;
}
return sum;
}
}
public List<Integer> numberOfAlternatingGroups(int[] colors, int[][] queries) {
int len = colors.length;
TreeSet<Integer> zeroPos = new TreeSet<>();
for (int i = 0; i < len; ++i) {
if (findColor(i, colors) == 0) {
// 记录异或数组0出现的位置，0的出现代表连续1的子数组被截断
zeroPos.add(i);
}
}
SegmentTree tree = new SegmentTree(colors.length + 1);
// 不存在0的情况需要特判。
if (zeroPos.isEmpty()) {
tree.update(len, 1);
} else {
// 更新各个连续1数组长度的信息
for (int n : zeroPos) {
int[] tmp = findCount(zeroPos, n, len);
tree.update(tmp[0], 1);
}
}
List<Integer> res = new ArrayList<>();
for (int[] q : queries) {
if (q[0] == 1) {
if (zeroPos.isEmpty()) {
res.add(len);
} else {
int[] tmp = tree.sumRange(q[1] - 1);
res.add(tmp[1] - tmp[0] * (q[1] - 2));
}
} else {
if (colors[q[1]] != q[2]) {
// 当前颜色发生变化，更新数组
updatePos(q[1], colors, tree, zeroPos);
updatePos((q[1] + 1) % len, colors, tree, zeroPos);
colors[q[1]] = q[2];
}
}
}
return res;
}
private int findColor(int i, int[] colors) {
int tmp;
if (i == 0) {
tmp = colors[0] ^ colors[colors.length - 1];
} else {
tmp = colors[i] ^ colors[i - 1];
}
return tmp;
}
private int[] findCount(TreeSet<Integer> set, int pos, int max) {
int[] res = {-1,0};
if (set.isEmpty()) {
res[0] = max - 1;
return res;
}
Integer higher = set.higher(pos);
if (higher == null) {
higher = set.first();
res[0] = max - pos + higher - 1;
} else {
res[0] = higher - pos - 1;
}
Integer lower = set.lower(pos);
if (lower == null) {
lower = set.last();
res[1] = max - lower + pos - 1;
} else {
res[1] = pos - lower - 1;
}
return res;
}
private void updatePos(int pos, int[] color, SegmentTree tree, TreeSet<Integer> zeroPos) {
int ori = findColor(pos, color);
if (ori == 0) {
int[] tmp = findCount(zeroPos, pos, color.length);
zeroPos.remove(pos);
tree.update(tmp[0], -1);
if (zeroPos.isEmpty()) {
tree.update(tmp[0] + 1, 1);
} else {
tree.update(tmp[0] + tmp[1] + 1, 1);
tree.update(tmp[1], -1);
}
} else {
int[] tmp = findCount(zeroPos, pos, color.length);
tree.update(tmp[0] + tmp[1] + 1, -1);
tree.update(tmp[0], 1);
tree.update(tmp[1], 1);
zeroPos.add(pos);
}
}
}