以后周赛日早上就发个简单题解和代码，下午会看时间更新一下题解。
欢迎大家加QQ群：623375442，可以方便群里面交流。
100294. Count the Number of Special Characters I
给你一个字符串 word。如果 word 中同时存在某个字母的小写形式和大写形式，则称这个字母为 特殊字母 。
返回 word 中 特殊字母 的数量。
测试样例：
输入：word = "aaAbcBC"
输出：3
解释：word 中的特殊字母是 'a'、'b' 和 'c'。
解答：用俩数组记录大小写出现的情况，如果两个数组都hit，那么res + 1.
class Solution {
public int numberOfSpecialChars(String word) {
int[] first = new int[26], last = new int[26];
Arrays.fill(first, -1);
Arrays.fill(last, -1);
for (int i = 0; i < word.length(); ++i) {
char c = word.charAt(i);
if (c >= 'a' && c <= 'z') {
last[c - 'a'] = i;
} else if (first[c - 'A'] == -1) {
first[c - 'A'] = i;
}
}
int res = 0;
for (int i = 0; i < 26; ++i) {
if (first[i] != -1 && last[i] != -1) {
++res;
}
}
return res;
}
}
100291. Count the Number of Special Characters II
给你一个字符串 word。如果 word 中同时出现某个字母 c 的小写形式和大写形式，并且 每个 小写形式的 c 都出现在第一个大写形式的 c 之前，则称字母 c 是一个 特殊字母 。
返回 word 中 特殊字母 的数量。
测试样例：
输入：word = "aaAbcBC"
输出：3
解释：特殊字母是 'a'、'b' 和 'c'。
解答：用俩数组记录大小写出现的情况，如果两个数组都hit，那么res + 1。和第一题的区别，只在于，这俩数组记录的小写最后出现位置和大写最早出现位置，需要满足first[i] > last[i]。
class Solution {
public int numberOfSpecialChars(String word) {
int[] first = new int[26], last = new int[26];
Arrays.fill(first, -1);
Arrays.fill(last, -1);
for (int i = 0; i < word.length(); ++i) {
char c = word.charAt(i);
if (c >= 'a' && c <= 'z') {
last[c - 'a'] = i;
} else if (first[c - 'A'] == -1) {
first[c - 'A'] = i;
}
}
int res = 0;
for (int i = 0; i < 26; ++i) {
if (first[i] != -1 && last[i] != -1 && first[i] > last[i]) {
++res;
}
}
return res;
}
}100290. Minimum Number of Operations to Satisfy Conditions
给你一个大小为 m x n 的二维矩形 grid 。每次 操作 中，你可以将 任一 格子的值修改为 任意 非负整数。完成所有操作后，你需要确保每个格子 grid[i][j] 的值满足：
- 如果下面相邻格子存在的话，它们的值相等，也就是 grid[i][j] == grid[i + 1][j]（如果存在）。
- 如果右边相邻格子存在的话，它们的值不相等，也就是 grid[i][j] != grid[i][j + 1]（如果存在）。
请你返回需要的 最少 操作数目。
测试样例：
输入：grid = [[1,0,2],[1,0,2]]
输出：0
解释：矩阵中所有格子已经满足要求。
解答：个人觉得，这周最难的一道题目。如果注意到提示：0 <= grid[i][j] <= 9，那就会发现这题其实很简单。对于每个格子的变化，存在两个大类：变化到<= 9，或者变化到> 9。前者会对后面的数组产生影响，后者可以任意选择数字，不会产生影响。这样我们利用动态规划，记录当前列变化到0 - 9和 > 9的最小变化次数。
动态规划的过程是，按照每一列遍历。当前列只会收到之前一列的影响。暴力当前为n的情况下，最小的修改次数。
class Solution {
public int minimumOperations(int[][] grid) {
int m = grid.length, n = grid[0].length;
int[][] count = new int[n][10];
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
count[j][grid[i][j]] += 1;
}
}
int[] dp = new int[11];
for (int i = 0; i < n; ++i) {
int[] nextDp = new int[11];
for (int j = 0; j <= 10; ++j) {
int tmp = Integer.MAX_VALUE;
for (int k = 0; k <= 10; ++k) {
// 只与之前列有关，10为大于9的情况，可以任意设置一个较大的数，且不引起冲突。
if (j == 10 || j != k) {
tmp = Math.min(dp[k], tmp);
}
}
if (j < 10) {
nextDp[j] = tmp + m - count[i][j];
} else {
nextDp[j] = tmp + m;
}
}
dp = nextDp;
}
int res = Integer.MAX_VALUE;
for (int r : dp) {
res = Math.min(r, res);
}
return res;
}
}100276. Find Edges in Shortest Paths
给你一个 n 个节点的无向带权图，节点编号为 0 到 n - 1 。图中总共有 m 条边，用二维数组 edges 表示，其中 edges[i] = [ai, bi, wi] 表示节点 ai 和 bi 之间有一条边权为 wi 的边。
对于节点 0 为出发点，节点 n - 1 为结束点的所有最短路，你需要返回一个长度为 m 的 boolean 数组 answer ，如果 edges[i] 至少 在其中一条最短路上，那么 answer[i] 为 true ，否则 answer[i] 为 false 。
请你返回数组 answer 。
注意，图可能不连通。
测试样例：
输入：n = 6, edges = [[0,1,4],[0,2,1],[1,3,2],[1,4,3],[1,5,1],[2,3,1],[3,5,3],[4,5,2]]
输出：[true,true,true,false,true,true,true,false]
解释：以下为节点 0 出发到达节点 5 的 所有 最短路：
- 路径 0 -> 1 -> 5 ：边权和为 4 + 1 = 5 。
- 路径 0 -> 2 -> 3 -> 5 ：边权和为 1 + 1 + 3 = 5 。
- 路径 0 -> 2 -> 3 -> 1 -> 5 ：边权和为 1 + 1 + 2 + 1 = 5 。
解答：手速的第四题，两次BFS。
我的题解中，把两次BFS合并。第一次BFS会得到到达某个点，最短的距离与经过的边。这样从终点出发反向就能计算出所有最短路径上的边。
class Solution {
public boolean[] findAnswer(int n, int[][] _edges) {
List<int[]>[] edges = new List[n];
for (int i = 0; i < n; ++i) {
edges[i] = new ArrayList<>();
}
for (int i = 0; i < _edges.length; ++i) {
int[] e = _edges[i];
edges[e[0]].add(new int[]{e[1], i});
edges[e[1]].add(new int[]{e[0], i});
}
List<Integer>[] connection = new List[n];
int[] min = new int[n];
Arrays.fill(min, Integer.MAX_VALUE);
TreeSet<Integer> queue = new TreeSet<>((a, b) -> (Integer.compare(min[a], min[b]) == 0 ?
Integer.compare(a, b) : Integer.compare(min[a], min[b])));
min[0] = 0;
queue.add(0);
while (!queue.isEmpty()) {
int t = queue.pollFirst();
for (int[] node : edges[t]) {
// 同时更新最短路径上的边和最短路径的值。
if (min[t] + _edges[node[1]][2] < min[node[0]]) {
queue.remove(node[0]);
min[node[0]] = min[t] + _edges[node[1]][2];
queue.add(node[0]);
connection[node[0]] = new ArrayList<>();
connection[node[0]].add(node[1]);
} else if (min[t] + _edges[node[1]][2] == min[node[0]]) {
connection[node[0]].add(node[1]);
}
}
}
boolean[] res = new boolean[_edges.length];
if (min[n - 1] == Integer.MAX_VALUE) {
return res;
}
boolean[] isNodeVisit = new boolean[n];
Queue<Integer> nodeQueue = new LinkedList<>();
nodeQueue.add(n - 1);
isNodeVisit[n - 1] = true;
// 逆向遍历，获取答案
while (!nodeQueue.isEmpty()) {
int tmp = nodeQueue.poll();
if (tmp != 0) {
for (int e : connection[tmp]) {
res[e] = true;
int o = _edges[e][0] == tmp ? _edges[e][1] : _edges[e][0];
if (!isNodeVisit[o]) {
isNodeVisit[o] = true;
nodeQueue.add(o);
}
}
}
}
return res;
}
}