🌟欢迎来到 我的博客 —— 探索技术的无限可能！
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; // 恢复现场
}
}
}
}