【题解】—— LeetCode一周小结48

🌟欢迎来到 我的博客 —— 探索技术的无限可能！

🌟博客的简介（文章目录）

---

【题解】—— 每日一道题目栏

---

上接：【题解】—— LeetCode一周小结47

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; // 恢复现场}}}
} 

下接：【题解】—— LeetCode一周小结49

---