🌟欢迎来到 我的博客 —— 探索技术的无限可能！
25.网络延迟时间
题目链接：743. 网络延迟时间
有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
示例 1：
输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2
示例 2：
输入：times = [[1,2,1]], n = 2, k = 1
输出：1
示例 3：
输入：times = [[1,2,1]], n = 2, k = 2
输出：-1
提示：
1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
所有 (ui, vi) 对都 互不相同（即，不含重复边）
题解：
方法：Dijkstra
class Solution { public int networkDelayTime(int[][] times, int n, int k) { final int INF = Integer.MAX_VALUE / 2; // 防止加法溢出 int[][] g = new int[n][n]; // 邻接矩阵 for (int[] row : g) { Arrays.fill(row, INF); } for (int[] t : times) { g[t[0] - 1][t[1] - 1] = t[2]; } int maxDis = 0; int[] dis = new int[n]; Arrays.fill(dis, INF); dis[k - 1] = 0; boolean[] done = new boolean[n]; while (true) { int x = -1; for (int i = 0; i < n; i++) { if (!done[i] && (x < 0 || dis[i] < dis[x])) { x = i; } } if (x < 0) { return maxDis; // 最后一次算出的最短路就是最大的 } if (dis[x] == INF) { // 有节点无法到达 return -1; } maxDis = dis[x]; // 求出的最短路会越来越大 done[x] = true; // 最短路长度已确定（无法变得更小） for (int y = 0; y < n; y++) { // 更新 x 的邻居的最短路 dis[y] = Math.min(dis[y], dis[x] + g[x][y]); } } } }
26.交替组 I
题目链接：3206. 交替组 I
给你一个整数数组 colors ，它表示一个由红色和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i] ：
colors[i] == 0 表示第 i 块瓷砖的颜色是 红色 。
colors[i] == 1 表示第 i 块瓷砖的颜色是 蓝色 。
环中连续 3 块瓷砖的颜色如果是 交替 颜色（也就是说中间瓷砖的颜色与它 左边 和 右边 的颜色都不同），那么它被称为一个 交替 组。
请你返回 交替 组的数目。
注意 ，由于 colors 表示一个 环 ，第一块 瓷砖和 最后一块 瓷砖是相邻的。
示例 1：
输入：colors = [1,1,1]
输出：0
解释：
示例 2：
输入：colors = [0,1,0,0,1]
输出：3
解释：
交替组包括：
提示：
3 <= colors.length <= 100
0 <= colors[i] <= 1
题解：
方法：遍历
class Solution { public int numberOfAlternatingGroups(int[] colors) { int k = 3; int n = colors.length; int ans = 0, cnt = 0; for (int i = 0; i < n << 1; ++i) { if (i > 0 && colors[i % n] == colors[(i - 1) % n]) { cnt = 1; } else { ++cnt; } ans += i >= n && cnt >= k ? 1 : 0; } return ans; } }
27.交替组 II
题目链接：3208. 交替组 II
给你一个整数数组 colors 和一个整数 k ，colors表示一个由红色和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i] ：
colors[i] == 0 表示第 i 块瓷砖的颜色是 红色 。
colors[i] == 1 表示第 i 块瓷砖的颜色是 蓝色 。
环中连续 k 块瓷砖的颜色如果是 交替 颜色（也就是说除了第一块和最后一块瓷砖以外，中间瓷砖的颜色与它 左边 和 右边 的颜色都不同），那么它被称为一个 交替 组。
请你返回 交替 组的数目。
注意 ，由于 colors 表示一个 环 ，第一块 瓷砖和 最后一块 瓷砖是相邻的。
示例 1：
输入：colors = [0,1,0,1,0], k = 3
输出：3
解释：
交替组包括：
示例 2：
输入：colors = [0,1,0,0,1,0,1], k = 6
输出：2
解释：
交替组包括：
示例 3：
输入：colors = [1,1,0,1], k = 4
输出：0
解释：
提示：
3 <= colors.length <= 105
0 <= colors[i] <= 1
3 <= k <= colors.length
题解：
方法：动态规划
class Solution { public int numberOfAlternatingGroups(int[] colors, int k) { int n = colors.length; int ans = 0; int cnt = 0; for (int i = 0; i < n * 2; i++) { if (colors[i % n] == colors[(i + 1) % n]) { cnt = 0; } cnt++; if (i >= n && cnt >= k) { ans++; } } return ans; } }
28.单调数组对的数目 I
题目链接：3250. 单调数组对的数目 I
给你一个长度为 n 的 正 整数数组 nums 。
如果两个 非负 整数数组 (arr1, arr2) 满足以下条件，我们称它们是 单调 数组对：
两个数组的长度都是 n 。
arr1 是单调 非递减 的，换句话说 arr1[0] <= arr1[1] <= … <= arr1[n - 1] 。
arr2 是单调 非递增 的，换句话说 arr2[0] >= arr2[1] >= … >= arr2[n - 1] 。
对于所有的 0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。
请你返回所有 单调 数组对的数目。
由于答案可能很大，请你将它对 109 + 7 取余 后返回。
示例 1：
输入：nums = [2,3,2]
输出：4
解释：
单调数组对包括：
([0, 1, 1], [2, 2, 1])
([0, 1, 2], [2, 2, 0])
([0, 2, 2], [2, 1, 0])
([1, 2, 2], [1, 1, 0])
示例 2：
输入：nums = [5,5,5,5]
输出：126
提示：
1 <= n == nums.length <= 2000
1 <= nums[i] <= 50
题解：
方法：动态规划 + 前缀和优化
class Solution { public int countOfPairs(int[] nums) { final int mod = (int) 1e9 + 7; int n = nums.length; int m = Arrays.stream(nums).max().getAsInt(); int[][] f = new int[n][m + 1]; for (int j = 0; j <= nums[0]; ++j) { f[0][j] = 1; } int[] g = new int[m + 1]; for (int i = 1; i < n; ++i) { g[0] = f[i - 1][0]; for (int j = 1; j <= m; ++j) { g[j] = (g[j - 1] + f[i - 1][j]) % mod; } for (int j = 0; j <= nums[i]; ++j) { int k = Math.min(j, j + nums[i - 1] - nums[i]); if (k >= 0) { f[i][j] = g[k]; } } } int ans = 0; for (int j = 0; j <= nums[n - 1]; ++j) { ans = (ans + f[n - 1][j]) % mod; } return ans; } }
29.单调数组对的数目 II
题目链接：3251. 单调数组对的数目 II
给你一个长度为 n 的 正 整数数组 nums 。
如果两个 非负 整数数组 (arr1, arr2) 满足以下条件，我们称它们是 单调 数组对：
两个数组的长度都是 n 。
arr1 是单调 非递减 的，换句话说 arr1[0] <= arr1[1] <= … <= arr1[n - 1] 。
arr2 是单调 非递增 的，换句话说 arr2[0] >= arr2[1] >= … >= arr2[n - 1] 。
对于所有的 0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。
请你返回所有 单调 数组对的数目。
由于答案可能很大，请你将它对 109 + 7 取余 后返回。
示例 1：
输入：nums = [2,3,2]
输出：4
解释：
单调数组对包括：
([0, 1, 1], [2, 2, 1])
([0, 1, 2], [2, 2, 0])
([0, 2, 2], [2, 1, 0])
([1, 2, 2], [1, 1, 0])
示例 2：
输入：nums = [5,5,5,5]
输出：126
提示：
1 <= n == nums.length <= 2000
1 <= nums[i] <= 1000
题解：
方法：动态规划 + 前缀和优化
class Solution { public int countOfPairs(int[] nums) { final int mod = (int) 1e9 + 7; int n = nums.length; int m = Arrays.stream(nums).max().getAsInt(); int[][] f = new int[n][m + 1]; for (int j = 0; j <= nums[0]; ++j) { f[0][j] = 1; } int[] g = new int[m + 1]; for (int i = 1; i < n; ++i) { g[0] = f[i - 1][0]; for (int j = 1; j <= m; ++j) { g[j] = (g[j - 1] + f[i - 1][j]) % mod; } for (int j = 0; j <= nums[i]; ++j) { int k = Math.min(j, j + nums[i - 1] - nums[i]); if (k >= 0) { f[i][j] = g[k]; } } } int ans = 0; for (int j = 0; j <= nums[n - 1]; ++j) { ans = (ans + f[n - 1][j]) % mod; } return ans; } }
30.判断是否可以赢得数字游戏
题目链接：3232. 判断是否可以赢得数字游戏
给你一个 正整数 数组 nums。
Alice 和 Bob 正在玩游戏。在游戏中，Alice 可以从 nums 中选择所有个位数 或 所有两位数，剩余的数字归 Bob 所有。如果 Alice 所选数字之和 严格大于 Bob 的数字之和，则 Alice 获胜。
如果 Alice 能赢得这场游戏，返回 true；否则，返回 false。
示例 1：
输入：nums = [1,2,3,4,10]
输出：false
解释：
Alice 不管选个位数还是两位数都无法赢得比赛。
示例 2：
输入：nums = [1,2,3,4,5,14]
输出：true
解释：
Alice 选择个位数可以赢得比赛，所选数字之和为 15。
示例 3：
输入：nums = [5,5,5,25]
输出：true
解释：
Alice 选择两位数可以赢得比赛，所选数字之和为 25。
提示：
1 <= nums.length <= 100
1 <= nums[i] <= 99
题解：
class Solution { public boolean canAliceWin(int[] nums) { int s = 0; for (int x : nums) { s += x < 10 ? x : -x; } return s != 0; } }
2024.12
1.N 皇后
题目链接：51. N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。 示例 2：
输入：n = 1
输出：[[“Q”]]
提示：
1 <= n <= 9
题解：
方法：递归 回溯
class Solution { public List<List<String>> solveNQueens(int n) { List<List<String>> ans = new ArrayList<>(); int[] queens = new int[n]; // 皇后放在 (r,queens[r]) boolean[] col = new boolean[n]; boolean[] diag1 = new boolean[n * 2 - 1]; boolean[] diag2 = new boolean[n * 2 - 1]; dfs(0, queens, col, diag1, diag2, ans); return ans; } private void dfs(int r, int[] queens, boolean[] col, boolean[] diag1, boolean[] diag2, List<List<String>> ans) { int n = col.length; if (r == n) { List<String> board = new ArrayList<>(n); // 预分配空间 for (int c : queens) { char[] row = new char[n]; Arrays.fill(row, '.'); row[c] = 'Q'; board.add(new String(row)); } ans.add(board); return; } // 在 (r,c) 放皇后 for (int c = 0; c < n; c++) { int rc = r - c + n - 1; if (!col[c] && !diag1[r + c] && !diag2[rc]) { // 判断能否放皇后 queens[r] = c; // 直接覆盖，无需恢复现场 col[c] = diag1[r + c] = diag2[rc] = true; // 皇后占用了 c 列和两条斜线 dfs(r + 1, queens, col, diag1, diag2, ans); col[c] = diag1[r + c] = diag2[rc] = false; // 恢复现场 } } } }
