🌟欢迎来到 我的博客 —— 探索技术的无限可能！
18.图片平滑器
题目链接：661. 图片平滑器
图像平滑器 是大小为 3 x 3 的过滤器，用于对图像的每个单元格平滑处理，平滑处理后单元格的值为该单元格的平均灰度。
每个单元格的 平均灰度 定义为：该单元格自身及其周围的 8 个单元格的平均值，结果需向下取整。（即，需要计算蓝色平滑器中 9 个单元格的平均值）。
如果一个单元格周围存在单元格缺失的情况，则计算平均灰度时不考虑缺失的单元格（即，需要计算红色平滑器中 4 个单元格的平均值）。
给你一个表示图像灰度的 m x n 整数矩阵 img ，返回对图像的每个单元格平滑处理后的图像 。
示例 1:
输入:img = [[1,1,1],[1,0,1],[1,1,1]]
输出:[[0, 0, 0],[0, 0, 0], [0, 0, 0]]
解释:
对于点 (0,0), (0,2), (2,0), (2,2): 平均(3/4) = 平均(0.75) = 0
对于点 (0,1), (1,0), (1,2), (2,1): 平均(5/6) = 平均(0.83333333) = 0
对于点 (1,1): 平均(8/9) = 平均(0.88888889) = 0
示例 2:
输入: img = [[100,200,100],[200,50,200],[100,200,100]]
输出: [[137,141,137],[141,138,141],[137,141,137]]
解释:
对于点 (0,0), (0,2), (2,0), (2,2): floor((100+200+200+50)/4) =
floor(137.5) = 137
对于点 (0,1), (1,0), (1,2), (2,1): floor((200+200+50+200+100+100)/6) =
floor(141.666667) = 141
对于点 (1,1): floor((50+200+200+200+200+100+100+100+100)/9) =
floor(138.888889) = 138
提示:
m == img.length
n == img[i].length
1 <= m, n <= 200
0 <= img[i][j] <= 255
题解：
方法：前缀和
class Solution { public int[][] imageSmoother(int[][] img) { int m = img.length, n = img[0].length; int[][] ans = new int[m][n]; int[][] dirs = new int[][]{{0,0},{1,0},{-1,0},{0,1},{0,-1},{-1,-1},{-1,1},{1,-1},{1,1}}; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { int tot = 0, cnt = 0; for (int[] di : dirs) { int nx = i + di[0], ny = j + di[1]; if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; tot += img[nx][ny]; cnt++; } ans[i][j] = tot / cnt; } } return ans; } }
19.新增道路查询后的最短距离 I
题目链接：3243. 新增道路查询后的最短距离 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 的最短路径的长度。
示例 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。
示例 2：
输入： n = 4, queries = [[0, 3], [0, 2]]
输出： [1, 1]
解释：
新增一条从 0 到 3 的道路后，从 0 到 3 的最短路径长度为 1。
新增一条从 0 到 2 的道路后，从 0 到 3 的最短路径长度仍为 1。
提示：
3 <= n <= 500
1 <= queries.length <= 500
queries[i].length == 2
0 <= queries[i][0] < queries[i][1] < n
1 < queries[i][1] - queries[i][0]
查询中没有重复的道路。
题解：
方法：DP
class Solution { public int[] shortestDistanceAfterQueries(int n, int[][] queries) { List<Integer>[] from = new ArrayList[n]; Arrays.setAll(from, i -> new ArrayList<>()); int[] f = new int[n]; for (int i = 1; i < n; i++) { f[i] = i; } int[] ans = new int[queries.length]; for (int qi = 0; qi < queries.length; qi++) { int l = queries[qi][0]; int r = queries[qi][1]; from[r].add(l); if (f[l] + 1 < f[r]) { f[r] = f[l] + 1; for (int i = r + 1; i < n; i++) { f[i] = Math.min(f[i], f[i - 1] + 1); for (int j : from[i]) { f[i] = Math.min(f[i], f[j] + 1); } } } ans[qi] = f[n - 1]; } return ans; } }
20.新增道路查询后的最短距离 II
class UnionFind {
public final int[] fa;
public UnionFind(int size) { fa = new int[size]; for (int i = 1; i < size; i++) { fa[i] = i; } } public int find(int x) { if (fa[x] != x) { fa[x] = find(fa[x]); } return fa[x]; }
}
class Solution {
public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
UnionFind uf = new UnionFind(n - 1);
int[] ans = new int[queries.length];
int cnt = n - 1; // 并查集连通块个数
for (int qi = 0; qi < queries.length; qi++) {
int l = queries[qi][0];
int r = queries[qi][1] - 1;
int fr = uf.find®;
for (int i = uf.find(l); i < r; i = uf.find(i + 1)) {
uf.fa[i] = fr;
cnt–;
}
ans[qi] = cnt;
}
return ans;
}
}
作者：灵茶山艾府
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
题解：
方法：区间并查集
class UnionFind { public final int[] fa; public UnionFind(int size) { fa = new int[size]; for (int i = 1; i < size; i++) { fa[i] = i; } } public int find(int x) { if (fa[x] != x) { fa[x] = find(fa[x]); } return fa[x]; } } class Solution { public int[] shortestDistanceAfterQueries(int n, int[][] queries) { UnionFind uf = new UnionFind(n - 1); int[] ans = new int[queries.length]; int cnt = n - 1; // 并查集连通块个数 for (int qi = 0; qi < queries.length; qi++) { int l = queries[qi][0]; int r = queries[qi][1] - 1; int fr = uf.find(r); for (int i = uf.find(l); i < r; i = uf.find(i + 1)) { uf.fa[i] = fr; cnt--; } ans[qi] = cnt; } return ans; } }
21.矩阵中的蛇
题目链接：3248. 矩阵中的蛇
大小为 n x n 的矩阵 grid 中有一条蛇。蛇可以朝 四个可能的方向 移动。矩阵中的每个单元格都使用位置进行标识： grid[i][j] = (i * n) + j。
蛇从单元格 0 开始，并遵循一系列命令移动。
给你一个整数 n 表示 grid 的大小，另给你一个字符串数组 commands，其中包括 “UP”、“RIGHT”、“DOWN” 和 “LEFT”。题目测评数据保证蛇在整个移动过程中将始终位于 grid 边界内。
返回执行 commands 后蛇所停留的最终单元格的位置。
示例 1：
输入：n = 2, commands = [“RIGHT”,“DOWN”]
输出：3
解释：
0 1
2 3
0 1
2 3
0 1
2 3
示例 2：
输入：n = 3, commands = [“DOWN”,“RIGHT”,“UP”]
输出：1
解释：
0 1 2
3 4 5
6 7 8
0 1 2
3 4 5
6 7 8
0 1 2
3 4 5
6 7 8
0 1 2
3 4 5
6 7 8
提示：
2 <= n <= 10
1 <= commands.length <= 100
commands 仅由 “UP”、“RIGHT”、“DOWN” 和 “LEFT” 组成。
生成的测评数据确保蛇不会移动到矩阵的边界外。
题解：
方法：****
class Solution { public int finalPositionOfSnake(int n, List<String> commands) { int i = 0; int j = 0; for (String s : commands) { switch (s.charAt(0)) { case 'U' -> i--; case 'D' -> i++; case 'L' -> j--; default -> j++; } } return i * n + j; } }
22.统计不是特殊数字的数字数量
题目链接：3233. 统计不是特殊数字的数字数量
给你两个 正整数 l 和 r。对于任何数字 x，x 的所有正因数（除了 x 本身）被称为 x 的 真因数。
如果一个数字恰好仅有两个 真因数，则称该数字为 特殊数字。例如：
数字 4 是 特殊数字，因为它的真因数为 1 和 2。
数字 6 不是 特殊数字，因为它的真因数为 1、2 和 3。
返回区间 [l, r] 内 不是 特殊数字 的数字数量。
示例 1：
输入： l = 5, r = 7
输出： 3
解释：
区间 [5, 7] 内不存在特殊数字。
示例 2：
输入： l = 4, r = 16
输出： 11
解释：
区间 [4, 16] 内的特殊数字为 4 和 9。
提示：
1 <= l <= r <= 109
题解：
方法：数学
class Solution { private static final int MX = 31622; private static final int[] PI = new int[MX + 1]; static { for (int i = 2; i <= MX; i++) { if (PI[i] == 0) { // i 是质数 PI[i] = PI[i - 1] + 1; for (int j = i * i; j <= MX; j += i) { // 注：如果 MX 比较大，小心 i*i 溢出 PI[j] = -1; // 标记 i 的倍数为合数 } } else { PI[i] = PI[i - 1]; } } } public int nonSpecialCount(int l, int r) { return r - l + 1 - (PI[(int) Math.sqrt(r)] - PI[(int) Math.sqrt(l - 1)]); } }
23.求出胜利玩家的数目
题目链接：3238. 求出胜利玩家的数目
给你一个整数 n ，表示在一个游戏中的玩家数目。同时给你一个二维整数数组 pick ，其中 pick[i] = [xi, yi] 表示玩家 xi 获得了一个颜色为 yi 的球。
如果玩家 i 获得的球中任何一种颜色球的数目 严格大于 i 个，那么我们说玩家 i 是胜利玩家。换句话说：
如果玩家 0 获得了任何的球，那么玩家 0 是胜利玩家。
如果玩家 1 获得了至少 2 个相同颜色的球，那么玩家 1 是胜利玩家。
…
如果玩家 i 获得了至少 i + 1 个相同颜色的球，那么玩家 i 是胜利玩家。
请你返回游戏中 胜利玩家 的数目。
注意，可能有多个玩家是胜利玩家。
示例 1：
输入：n = 4, pick = [[0,0],[1,0],[1,0],[2,1],[2,1],[2,0]]
输出：2
解释：
玩家 0 和玩家 1 是胜利玩家，玩家 2 和玩家 3 不是胜利玩家。
示例 2：
输入：n = 5, pick = [[1,1],[1,2],[1,3],[1,4]]
输出：0
解释：
没有胜利玩家。
示例 3：
输入：n = 5, pick = [[1,1],[2,4],[2,4],[2,4]]
输出：1
解释：
玩家 2 是胜利玩家，因为玩家 2 获得了 3 个颜色为 4 的球。
提示：
2 <= n <= 10
1 <= pick.length <= 100
pick[i].length == 2
0 <= xi <= n - 1
0 <= yi <= 10
题解：
方法：两次遍历
class Solution { public int winningPlayerCount(int n, int[][] pick) { int[][] cnts = new int[n][11]; for (int[] p : pick) { cnts[p[0]][p[1]]++; } int ans = 0; for (int i = 0; i < n; i++) { for (int c : cnts[i]) { if (c > i) { ans++; break; } } } return ans; } }
24.最小区间
题目链接：632. 最小区间
你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。
我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。
示例 1：
输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出：[20,24]
解释：
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。
示例 2：
输入：nums = [[1,2,3],[1,2,3],[1,2,3]]
输出：[1,1]
提示：
nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50
-105 <= nums[i][j] <= 105
nums[i] 按非递减顺序排列
题解：
方法：滑动窗口
class Solution { public int[] smallestRange(List<List<Integer>> nums) { int sumLen = 0; for (List<Integer> list : nums) { sumLen += list.size(); } int[][] pairs = new int[sumLen][2]; int pi = 0; for (int i = 0; i < nums.size(); i++) { for (int x : nums.get(i)) { pairs[pi][0] = x; pairs[pi++][1] = i; } } Arrays.sort(pairs, (a, b) -> a[0] - b[0]); int ansL = pairs[0][0]; int ansR = pairs[sumLen - 1][0]; int empty = nums.size(); int[] cnt = new int[empty]; int left = 0; for (int[] p : pairs) { int r = p[0]; int i = p[1]; if (cnt[i] == 0) { // 包含 nums[i] 的数字 empty--; } cnt[i]++; while (empty == 0) { // 每个列表都至少包含一个数 int l = pairs[left][0]; if (r - l < ansR - ansL) { ansL = l; ansR = r; } i = pairs[left][1]; cnt[i]--; if (cnt[i] == 0) { // 不包含 nums[i] 的数字 empty++; } left++; } } return new int[]{ansL, ansR}; } }
