额外题目汇总4-回溯算法,贪心,动态规划,图论,并查集,模拟,位运算

回溯算法

1.52. N皇后II

题目链接：https://leetcode.cn/problems/n-queens-ii/(opens new window)

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n，返回 n 皇后不同的解决方案的数量。

示例:

输入: 4

输出: 2

解释: 4 皇后问题存在如下两个不同的解法。

解法 1

[  [".Q..",   "...Q",   "Q...",   "..Q."],

解法 2

["..Q.",   "Q...",   "...Q",   ".Q.."] ]

思路

详看：51.N皇后 (opens new window)，基本没有区别

public class N_QueensII {int count = 0;//用于记录可行解决方案的数量。public int totalNQueens(int n) {char[][] board = new char[n][n];//创建一个 n×n 的字符数组 board 表示棋盘，并将所有位置初始化为 .。for (char[] chars : board) {Arrays.fill(chars, '.');}backTrack(n, 0, board);//调用 backTrack 方法开始回溯搜索，初始行号为 0。return count;}private void backTrack(int n, int row, char[][] board) {if (row == n) {//当 row == n 时，说明已经处理完所有行，找到了一种可行的解决方案，计数器 count 加 1，并返回。count++;return;}for (int col = 0; col < n; col++) {//对于当前行 row，尝试在每一列 col 放置皇后。if (isValid(row, col, n, board)) {//调用 isValid 方法检查该位置是否可以放置皇后。board[row][col] = 'Q';//如果该位置合法，将该位置标记为 Q，并递归调用 backTrack 方法处理下一行。backTrack(n, row + 1, board);board[row][col] = '.';//递归返回后，将该位置恢复为 .，继续尝试下一列。}}}private boolean isValid(int row, int col, int n, char[][] board) {for (int i = 0; i < row; ++i) {//从第 0 行开始，遍历到当前行 row - 1，检查同一列 col 上是否已经有皇后存在。因为代码采用逐行放置皇后的策略，所以只需检查当前行之上的列元素。if (board[i][col] == 'Q') {//若发现 board[i][col] 为 'Q'，说明该列已有皇后，当前位置 (row, col) 不能放置皇后，直接返回 false。若遍历完该列都未发现皇后，则继续进行对角线的检查。return false;}}for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {//从当前位置 (row, col) 向左上方进行遍历，也就是 45 度对角线方向。只要 i 和 j 都不小于 0，就继续遍历。每次循环 i 和 j 都减 1，意味着向左上方移动一格。if (board[i][j] == 'Q') {//若在该对角线上发现 board[i][j] 为 'Q'，说明该对角线已有皇后，当前位置 (row, col) 不能放置皇后，返回 false。若遍历完该对角线都未发现皇后，则继续检查另一条对角线。return false;}}for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {//从当前位置 (row, col) 向右上方进行遍历，即 135 度对角线方向。只要 i 不小于 0 且 j 不超过 n - 1，就继续遍历。每次循环 i 减 1，j 加 1，代表向右上方移动一格。if (board[i][j] == 'Q') {//若在该对角线上发现 board[i][j] 为 'Q'，说明该对角线已有皇后，当前位置 (row, col) 不能放置皇后，返回 false。return false;}}return true;//若上述三个检查都未发现冲突，说明当前位置 (row, col) 可以安全放置皇后，返回 true。}
]

时间复杂度

在最坏的情况下，算法需要遍历所有可能的皇后摆放方式。对于每一行，最多可以尝试放置 N 个皇后，因此时间复杂度为 O(N!)。这是因为在每一行放置一个皇后后，下一行的选择会减少，最终形成一个递归树，每个节点的分支数在逐渐减小。

空间复杂度 空间复杂度主要由以下几个部分组成： 1.棋盘的存储：需要一个 n x n 的棋盘来存储皇后的位置，空间复杂度为 O(N^2)。 2. 递归调用栈：在最坏的情况下，递归的深度为 N，因此递归调用栈的空间复杂度为 O(N)。 综合以上两部分，空间复杂度为 O(N^2) + O(N)，简化后可以认为是 O(N^2)。

时间复杂度：O(N!)

空间复杂度：O(N^2) 

4 皇后问题要求在一个 4×4 的棋盘上放置 4 个皇后，使得任意两个皇后都不能处于同一行、同一列或同一对角线上。

回溯

假设我们在第 0 行第 0 列放置了一个皇后，然后递归处理第 1 行。在第 1 行，我们尝试在第 2 列放置皇后，接着递归处理第 2 行。但在处理第 2 行时，会发现无论在哪个列放置皇后，都会与前面已放置的皇后产生冲突（在同一列或同一对角线上），这意味着我们在第 1 行第 2 列放置皇后这个选择是错误的，无法得到有效的解决方案。

此时，就需要进行回溯操作，撤销在第 1 行第 2 列放置皇后的操作（将该位置恢复为 .），然后尝试在第 1 行的其他列放置皇后，继续探索其他可能的解决方案。

初始化

在 main 方法中，我们创建了 N_QueensII 类的实例，并调用 totalNQueens 方法，传入参数 n = 4。totalNQueens 方法会初始化一个 4×4 的棋盘 board，并将所有位置初始化为 .，然后调用 backTrack 方法开始回溯搜索，初始行号 row = 0。

2. 回溯搜索过程

处理第 0 行

• 尝试第 0 列：调用 isValid(0, 0, 4, board) 检查位置 (0, 0) 是否合法。由于此时棋盘为空，该位置合法，将 board[0][0] 置为 'Q'，然后递归调用 backTrack(4, 1, board) 处理第 1 行。
• 处理第 1 行：
  • 尝试第 0 列：调用 isValid(1, 0, 4, board)，由于第 0 列已经有皇后（board[0][0] = 'Q'），该位置不合法。
  • 尝试第 1 列：调用 isValid(1, 1, 0, 4, board)，由于该位置与 (0, 0) 在对角线上，不合法。
  • 尝试第 2 列：调用 isValid(1, 2, 4, board)，该位置合法，将 board[1][2] 置为 'Q'，然后递归调用 backTrack(4, 2, board) 处理第 2 行。
• 处理第 2 行：
  • 无论尝试哪一列，都会与前面已放置的皇后冲突（在同一列或对角线上），因此 isValid 方法都会返回 false，无法在第 2 行找到合法位置。此时，backTrack(4, 2, board) 调用结束，回溯到第 1 行。
• 回溯到第 1 行：将 board[1][2] 恢复为 .，继续尝试第 3 列。
  • 尝试第 3 列：调用 isValid(1, 3, 4, board)，该位置合法，将 board[1][3] 置为 'Q'，然后递归调用 backTrack(4, 2, board) 处理第 2 行。
• 处理第 2 行：
  • 同样，无论尝试哪一列，都会与前面已放置的皇后冲突，无法在第 2 行找到合法位置。此时，backTrack(4, 2, board) 调用结束，回溯到第 1 行。
• 回溯到第 1 行：将 board[1][3] 恢复为 .，第 1 行的所有列都尝试过了，回溯到第 0 行。
• 回溯到第 0 行：将 board[0][0] 恢复为 .，继续尝试第 1 列。

尝试第 0 行第 1 列

• 尝试第 1 列：调用 isValid(0, 1, 4, board)，该位置合法，将 board[0][1] 置为 'Q'，然后递归调用 backTrack(4, 1, board) 处理第 1 行。
• 处理第 1 行：
  • 尝试第 3 列：调用 isValid(1, 3, 4, board)，该位置合法，将 board[1][3] 置为 'Q'，然后递归调用 backTrack(4, 2, board) 处理第 2 行。
• 处理第 2 行：
  • 尝试第 0 列：调用 isValid(2, 0, 4, board)，该位置合法，将 board[2][0] 置为 'Q'，然后递归调用 backTrack(4, 3, board) 处理第 3 行。
• 处理第 3 行：
  • 尝试第 2 列：调用 isValid(3, 2, 4, board)，该位置合法，将 board[3][2] 置为 'Q'，然后递归调用 backTrack(4, 4, board)。
• 找到一个可行解：当 row == 4 时，说明已经处理完所有行，找到了一个可行解，计数器 count 加 1，然后返回。
• 回溯：将 board[3][2] 恢复为 .，继续尝试第 3 行的其他列，但都不合法，回溯到第 2 行，依次类推，继续尝试其他可能的位置。

3. 最终结果

经过不断地尝试和回溯，代码会遍历所有可能的皇后放置方案，最终找到所有可行解。对于 4 皇后问题，可行解的数量为 2

贪心

1.649. Dota2 参议院

力扣题目链接(opens new window)

Dota2 的世界里有两个阵营：Radiant(天辉)和 Dire(夜魇)

Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中，每一位参议员都可以行使两项权利中的一项：

1. 禁止一名参议员的权利：参议员可以让另一位参议员在这一轮和随后的几轮中丧失所有的权利。

2. 宣布胜利：如果参议员发现有权利投票的参议员都是同一个阵营的，他可以宣布胜利并决定在游戏中的有关变化。

给定一个字符串代表每个参议员的阵营。字母 “R” 和 “D” 分别代表了 Radiant（天辉）和 Dire（夜魇）。然后，如果有 n 个参议员，给定字符串的大小将是 n。

以轮为基础的过程从给定顺序的第一个参议员开始到最后一个参议员结束。这一过程将持续到投票结束。所有失去权利的参议员将在过程中被跳过。

假设每一位参议员都足够聪明，会为自己的政党做出最好的策略，你需要预测哪一方最终会宣布胜利并在 Dota2 游戏中决定改变。输出应该是 Radiant 或 Dire。

示例 1：

• 输入："RD"
• 输出："Radiant"
• 解释：第一个参议员来自 Radiant 阵营并且他可以使用第一项权利让第二个参议员失去权力，因此第二个参议员将被跳过因为他没有任何权利。然后在第二轮的时候，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人

示例 2：

• 输入："RDD"
• 输出："Dire"
• 解释： 第一轮中,第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利， 第二个来自 Dire 阵营的参议员会被跳过因为他的权利被禁止， 第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利， 因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利。

思路

输入"RRDDD"

• 第一轮：senate[0]的R消灭senate[2]的D，senate[1]的R消灭senate[3]的D，senate[4]的D消灭senate[0]的R，此时剩下"RD"，第一轮结束！
• 第二轮：senate[0]的R消灭senate[1]的D，第二轮结束
• 第三轮：只有R了，R胜利

R和D数量相同怎么办，究竟谁赢，其实这是一个持续消灭的过程！ 即：如果同时存在R和D就继续进行下一轮消灭，轮数直到只剩下R或者D为止！

例如：RDDRD

第一轮：senate[0]的R消灭senate[1]的D，那么senate[2]的D，是消灭senate[0]的R还是消灭senate[3]的R呢？

当然是消灭senate[3]的R，因为当轮到这个R的时候，它可以消灭senate[4]的D。

所以消灭的策略是，尽量消灭自己后面的对手，因为前面的对手已经使用过权利了，而后序的对手依然可以使用权利消灭自己的同伴！

那么局部最优：有一次权利机会，就消灭自己后面的对手。全局最优：为自己的阵营赢取最大利益。

局部最优可以退出全局最优，举不出反例，那么试试贪心关于贪心算法，你该了解这些！ (opens new window)

用一个变量记录当前参议员之前有几个敌对对手了，进而判断自己是否被消灭了。

字节数组

在 Java 中，字节数组（byte[]）是一种基本的数据结构，用于存储一系列字节类型的数据。每个字节（byte）是 8 位有符号整数，其取值范围是 -128 到 127。字节数组可以用来表示各种数据，比如文本、图像、音频等。

在解决 Dota2 参议院问题时，代码将输入的字符串转换为字节数组，主要是出于以下考虑：

• 性能优化：对字节数组的操作通常比直接对字符串进行操作更快，因为字符串是不可变对象，每次对字符串进行修改都会创建一个新的字符串对象，而字节数组是可变的，可以直接在原数组上进行修改。
• 方便标记：在代码中，需要标记哪些参议员被禁止行使权力，将字符替换为 0 来表示该参议员被消灭，字节数组可以方便地进行这种修改操作。

public class Dota2_Senate {public String predictPartyVictory(String senateStr) {boolean R = true, D = true;//用于标记本轮循环结束后字符串中是否仍然存在 'R' 和 'D'。初始值都设为 true，表示两种阵营的参议员都可能存在。int flag = 0;//用于记录两种阵营参议员行使权力的先后顺序和数量对比。当 flag > 0 时，说明在当前循环中 'R' 在 'D' 前出现，'R' 可以消灭 'D'；当 flag < 0 时，说明 'D' 在 'R' 前出现，'D' 可以消灭 'R'。byte[] senate =  senateStr.getBytes();//字节数组，将输入的字符串 senateStr 转换为字节数组，方便后续操作。while (R && D) {//只要 R 和 D 都为 true，说明本轮循环结束后两种阵营的参议员都还存在，需要继续进行投票。在每次循环开始时，将 R 和 D 都设为 false，后续根据实际情况更新它们的值。R = false;D = false;for (int i = 0; i < senate.length; i++) {//遍历字节数组 senate 中的每个元素。if (senate[i] == 'R') {//处理 'R' 阵营的参议员：如果 flag < 0，说明之前有 'D' 阵营的参议员先行使了权力，当前 'R' 阵营的参议员会被消灭，将 senate[i] 设为 0。如果 flag >= 0，说明当前 'R' 阵营的参议员没有被消灭，将 R 设为 true，表示本轮循环结束后仍然有 'R' 阵营的参议员存在。无论是否被消灭，flag 都加 1，表示 'R' 阵营的参议员行使了一次权力。if (flag < 0) senate[i] = 0;else R = true;flag++;}if (senate[i] == 'D') {//处理 'D' 阵营的参议员：如果 flag > 0，说明之前有 'R' 阵营的参议员先行使了权力，当前 'D' 阵营的参议员会被消灭，将 senate[i] 设为 0。如果 flag <= 0，说明当前 'D' 阵营的参议员没有被消灭，将 D 设为 true，表示本轮循环结束后仍然有 'D' 阵营的参议员存在。无论是否被消灭，flag 都减 1，表示 'D' 阵营的参议员行使了一次权力。if (flag > 0) senate[i] = 0;else D = true;flag--;}}}return R ? "Radiant" : "Dire";//R 和 D 中只有一个为 true，表示只剩下一个阵营的参议员。如果 R 为 true，返回 "Radiant"，表示天辉阵营获胜；否则返回 "Dire"，表示夜魇阵营获胜。}
}

时间复杂度 在最坏的情况下，循环会遍历整个 senateStr 字符串，直到其中一个阵营的参议员被全部消灭。每次循环中，都会遍历整个字符串。假设字符串的长度为 n ，则最坏情况下的时间复杂度是 O(n^2)。 这是因为在每一轮投票中，可能需要遍历整个字符串，而在最坏情况下，这种投票过程可能会重复多次，直到最终只剩下一个阵营的参议员。

空间复杂度 空间复杂度主要由以下几个部分组成： 1. 字节数组的存储：将输入字符串转换为字节数组 senate ，其大小为  n ，因此占用 O(n) 的空间。 2. 常量空间：一些额外的变量（如 R , D , flag ）占用的空间是常量级别的 O(1)。 因此，整体的空间复杂度是 O(n)。

时间复杂度：O(n^2)

空间复杂度：O(n) 

"RDDR"

初始化

• 输入字符串 senateStr = "RDDR"。
• R = true，D = true，表示初始时认为两种阵营的参议员都可能存在。
• flag = 0，表示目前两种阵营行使权力的先后顺序和数量对比平衡。
• senate 字节数组初始化为 [82, 68, 68, 82]，分别对应字符 'R'、'D'、'D'、'R' 的 ASCII 码值。

第一轮循环

1. 将 R 和 D 重置为 false：

   • R = false
   • D = false

2. 遍历 senate 数组：

   • 处理第一个元素 'R'（索引 i = 0）：
     • 此时 flag = 0，flag >= 0，所以 R = true，表示本轮循环结束后还有 'R' 阵营的参议员存在。
     • flag 加 1，flag = 1。
   • 处理第二个元素 'D'（索引 i = 1）：
     • 此时 flag = 1，flag > 0，说明之前有 'R' 阵营的参议员先行使了权力，当前 'D' 阵营的参议员会被消灭，将 senate[1] 设为 0。
     • flag 减 1，flag = 0。
   • 处理第三个元素 'D'（索引 i = 2）：
     • 此时 flag = 0，flag <= 0，所以 D = true，表示本轮循环结束后还有 'D' 阵营的参议员存在。
     • flag 减 1，flag = -1。
   • 处理第四个元素 'R'（索引 i = 3）：
     • 此时 flag = -1，flag < 0，说明之前有 'D' 阵营的参议员先行使了权力，当前 'R' 阵营的参议员会被消灭，将 senate[3] 设为 0。
     • flag 加 1，flag = 0。

   第一轮循环结束后，senate 数组变为 [82, 0, 68, 0]，R = true，D = true，由于 R 和 D 都为 true，说明两种阵营的参议员都还存在，继续下一轮循环。

第二轮循环

1. 将 R 和 D 重置为 false：

   • R = false
   • D = false

2. 遍历 senate 数组：

   • 处理第一个元素 'R'（索引 i = 0）：
     • 此时 flag = 0，flag >= 0，所以 R = true。
     • flag 加 1，flag = 1。
   • 处理第二个元素（已被标记为 0）：跳过。
   • 处理第三个元素 'D'（索引 i = 2）：
     • 此时 flag = 1，flag > 0，将 senate[2] 设为 0。
     • flag 减 1，flag = 0。
   • 处理第四个元素（已被标记为 0）：跳过。

   第二轮循环结束后，senate 数组变为 [82, 0, 0, 0]，R = true，D = false，由于 D 为 false，说明本轮循环结束后只剩下 'R' 阵营的参议员，循环结束。

返回结果

由于 R = true，所以返回 "Radiant"，表示天辉阵营获胜。

2.1221. 分割平衡字符串

力扣题目链接(opens new window)

在一个 平衡字符串 中，'L' 和 'R' 字符的数量是相同的。

给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。

注意：分割得到的每个字符串都必须是平衡字符串。

返回可以通过分割得到的平衡字符串的 最大数量 。

示例 1：

• 输入：s = "RLRRLLRLRL"
• 输出：4
• 解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。

示例 2：

• 输入：s = "RLLLLRRRLR"
• 输出：3
• 解释：s 可以分割为 "RL"、"LLLRRR"、"LR" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。

示例 3：

• 输入：s = "LLLLRRRR"
• 输出：1
• 解释：s 只能保持原样 "LLLLRRRR".

示例 4：

• 输入：s = "RLRRRLLRLL"
• 输出：2
• 解释：s 可以分割为 "RL"、"RRRLLRLL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。

思路

局部最优可以推出全局最优，贪心:关于贪心算法，你该了解这些！ (opens new window)。

从前向后遍历，只要遇到平衡子串，计数就+1，遍历一遍即可。

局部最优：从前向后遍历，只要遇到平衡子串 就统计

全局最优：统计了最多的平衡子串。

例如，LRLR 这本身就是平衡子串 , 但要遇到LR就可以分割。

拓展

一些同学可能想，你这个推理不靠谱，都没有数学证明。怎么就能说是合理的呢，怎么就能说明 局部最优可以推出全局最优呢？

一般数学证明有如下两种方法：

• 数学归纳法
• 反证法

所以贪心题目的思考过程是： 如果发现局部最优好像可以推出全局最优，那么就 尝试一下举反例，如果举不出反例，那么就试试贪心。

public class Split_a_Balanced_String {public int balancedStringSplit(String s) {int result = 0;//用于记录最终分割出的平衡子字符串的数量，初始值为 0。int count = 0;//用于记录当前子字符串中 'R' 和 'L' 的数量差值。初始时差值为 0。for (int i = 0; i < s.length(); i++) {//历输入字符串 s 中的每一个字符。if (s.charAt(i) == 'R') count++;//s.charAt(i) 用于获取字符串 s 中索引为 i 的字符。else count--;//如果该字符是 'R'，则将 count 加 1，表示 'R' 的数量增加了一个。如果该字符是 'L'，则将 count 减 1，表示 'L' 的数量增加了一个。if (count == 0) result++;//当 count 的值为 0 时，说明从当前分割起点到当前位置的子字符串中 'R' 和 'L' 的数量相等，即找到了一个平衡子字符串。此时将 result 的值加 1，用于记录新找到的平衡子字符串。}return result;}
}

时间复杂度 该算法通过一次遍历字符串 s 来计算平衡子字符串的数量。具体步骤如下： 遍历字符串的每一个字符，时间复杂度为 O(n)，其中 n 是字符串的长度。 - 在遍历过程中，进行常数时间的操作（如增加或减少计数、比较等）。 因此，整体的时间复杂度为 O(n)。

空间复杂度 空间复杂度主要由以下几个部分组成： 1. 常量空间：使用了几个整型变量（ result 和 count ），这些变量所占用的空间是常量级别的 O(1)。 2. 不使用额外的数据结构：算法没有使用任何额外的数据结构来存储中间结果。 因此，整体的空间复杂度为 O(1)。

时间复杂度：O(n)

空间复杂度：O(1) 

s = "RLRRLLRLRL"

初始化

• result = 0：用于记录平衡子字符串的数量，初始为 0。
• count = 0：用于记录当前子字符串中 'R' 和 'L' 的数量差值，初始为 0。

遍历字符串

第 1 个字符 'R'（i = 0）

• s.charAt(0) == 'R' 成立，执行 count++，此时 count = 1。
• count != 0，result 保持为 0。

第 2 个字符 'L'（i = 1）

• s.charAt(1) == 'R' 不成立，执行 count--，此时 count = 0。
• count == 0 成立，执行 result++，此时 result = 1，说明找到了一个平衡子字符串 "RL"。

第 3 个字符 'R'（i = 2）

• s.charAt(2) == 'R' 成立，执行 count++，此时 count = 1。
• count != 0，result 保持为 1。

第 4 个字符 'R'（i = 3）

• s.charAt(3) == 'R' 成立，执行 count++，此时 count = 2。
• count != 0，result 保持为 1。

第 5 个字符 'L'（i = 4）

• s.charAt(4) == 'R' 不成立，执行 count--，此时 count = 1。
• count != 0，result 保持为 1。

第 6 个字符 'L'（i = 5）

• s.charAt(5) == 'R' 不成立，执行 count--，此时 count = 0。
• count == 0 成立，执行 result++，此时 result = 2，说明又找到了一个平衡子字符串 "RRLL"。

第 7 个字符 'R'（i = 6）

• s.charAt(6) == 'R' 成立，执行 count++，此时 count = 1。
• count != 0，result 保持为 2。

第 8 个字符 'L'（i = 7）

• s.charAt(7) == 'R' 不成立，执行 count--，此时 count = 0。
• count == 0 成立，执行 result++，此时 result = 3，说明又找到了一个平衡子字符串 "RL"。

第 9 个字符 'R'（i = 8）

• s.charAt(8) == 'R' 成立，执行 count++，此时 count = 1。
• count != 0，result 保持为 3。

第 10 个字符 'L'（i = 9）

• s.charAt(9) == 'R' 不成立，执行 count--，此时 count = 0。
• count == 0 成立，执行 result++，此时 result = 4，说明又找到了一个平衡子字符串 "RL"。

最终结果

遍历结束后，result = 4，表示字符串 "RLRRLLRLRL" 可以分割成 4 个平衡子字符串，分别是 "RL"、"RRLL"、"RL" 和 "RL"。

动态规划

1.5.最长回文子串

力扣题目链接(opens new window)

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

• 输入：s = "babad"
• 输出："bab"
• 解释："aba" 同样是符合题意的答案。

示例 2：

• 输入：s = "cbbd"
• 输出："bb"

示例 3：

• 输入：s = "a"
• 输出："a"

示例 4：

• 输入：s = "ac"
• 输出："a"

思路

本题和647.回文子串 (opens new window)差不多是一样的，但647.回文子串更基本一点，建议可以先做647.回文子串

暴力解法

两层for循环，遍历区间起始位置和终止位置，然后判断这个区间是不是回文。

时间复杂度：O(n^3)

动态规划

动规五部曲：

1. 确定dp数组（dp table）以及下标的含义

布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

1. 确定递推公式

在确定递推公式时，就要分析如下几种情况。

整体上是两种，就是s[i]与s[j]相等，s[i]与s[j]不相等这两种。

当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。

当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况

• 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
• 情况二：下标i 与 j相差为1，例如aa，也是文子串
• 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

没有列出当s[i]与s[j]不相等的时候，因为在下面dp[i][j]初始化的时候，就初始为false。

在得到[i,j]区间是否是回文子串的时候，直接保存最长回文子串的左边界和右边界.

1. dp数组如何初始化

dp[i][j]可以初始化为true么？ 当然不行，怎能刚开始就全都匹配上了。

所以dp[i][j]初始化为false。

1. 确定遍历顺序

遍历顺序可有有点讲究了。

首先从递推公式中可以看出，情况三是根据dp[i + 1][j - 1]是否为true，在对dp[i][j]进行赋值true的。

dp[i + 1][j - 1] 在 dp[i][j]的左下角，如图：

如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的dp[i + 1][j - 1]，也就是根据不确定是不是回文的区间[i+1,j-1]，来判断了[i,j]是不是回文，那结果一定是不对的。

所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。

有的代码实现是优先遍历列，然后遍历行，其实也是一个道理，都是为了保证dp[i + 1][j - 1]都是经过计算的。

1. 举例推导dp数组

举例，输入："aaa"，dp[i][j]状态如下：

注意因为dp[i][j]的定义，所以j一定是大于等于i的，那么在填充dp[i][j]的时候一定是只填充右上半部分。

双指针

首先确定回文串，就是找中心然后想两边扩散看是不是对称的就可以了。

在遍历中心点的时候，要注意中心点有两种情况。

一个元素可以作为中心点，两个元素也可以作为中心点。

三个元素就可以由一个元素左右添加元素得到，四个元素则可以由两个元素左右添加元素得到。

所以我们在计算的时候，要注意一个元素为中心点和两个元素为中心点的情况。

这两种情况可以放在一起计算，但分别计算思路更清晰，我倾向于分别计算

Manacher 算法

Manacher 算法的关键在于高效利用回文的对称性，通过插入分隔符和维护中心、边界等信息，在线性时间内找到最长回文子串。这种方法避免了重复计算，是处理回文问题的最优解。

• 若 j - i = 1，子串长度 j - i + 1 = 2，当首尾字符相等时，这个子串（如 "aa"）就是回文串。
• 若 j - i = 2，子串长度 j - i + 1 = 3，当首尾字符相等时，这个子串（如 "aba"）同样是回文串。

public class Longest_Palindromic_Substring {public String longestPalindrome1(String s) {if (s.length() == 0 || s.length() == 1) return s;//如果输入字符串 s 的长度为 0 或者 1，那么它本身就是回文串，直接返回该字符串。int length = 1;//用于记录当前找到的最长回文子串的长度，初始值设为 1，因为单个字符也是回文串。int index = 0;//记录最长回文子串的起始索引，初始值为 0。boolean[][] palindrome = new boolean[s.length()][s.length()];//二维布尔数组，palindrome[i][j] 表示从索引 i 到索引 j 的子串是否为回文串。for (int i = 0; i < s.length(); i++) {//单个字符一定是回文串，所以将 palindrome[i][i] 都初始化为 true。palindrome[i][i] = true;}for (int L = 2; L <= s.length(); L++) {//外层循环 L 表示子串的长度，从 2 开始逐步增加到字符串的长度。for (int i = 0; i < s.length(); i++) {//内层循环 i 表示子串的起始索引。int j = i + L - 1;//计算子串的结束索引。if (j >= s.length()) break;//如果 j 超出了字符串的长度，说明当前子串越界，跳出内层循环。if (s.charAt(i) != s.charAt(j)) {//如果子串的首尾字符不相等，那么该子串不是回文串，将 palindrome[i][j] 设为 false。palindrome[i][j] = false;} else {//如果首尾字符相等，分两种情况if (j - i < 3) {//当子串长度小于 3 时（即 j - i < 3），例如长度为 2（如 "aa"）或 3（如 "aba"），由于首尾相等，所以该子串是回文串，将 palindrome[i][j] 设为 true。palindrome[i][j] = true;} else {//当子串长度大于等于 3 时，该子串是否为回文串取决于去掉首尾字符后的子串是否为回文串，即 palindrome[i][j] = palindrome[i + 1][j - 1]。palindrome[i][j] = palindrome[i + 1][j - 1];}}if (palindrome[i][j] && j - i + 1 > length) {//如果 palindrome[i][j] 为 true，说明从索引 i 到索引 j 的子串是回文串，并且其长度 j - i + 1 大于当前记录的最长回文子串长度 length，则更新 length 和 index。length = j - i + 1;index = i;}}}return s.substring(index, index + length);//使用 substring 方法从字符串 s 中截取从索引 index 开始，长度为 length 的子串，即最长回文子串，并将其返回。}
}

时间复杂度 该算法的时间复杂度为 O(n^2)，其中 n是输入字符串 s 的长度。原因如下： 1. 外层循环遍历所有可能的子串长度 L，从 2 到 n，共进行n-1 次迭代。 2. 内层循环遍历所有可能的起始索引i，对于每个 L，最多需要进行n 次迭代。 3. 因此，总的时间复杂度是 O(n^2)。

空间复杂度 该算法的空间复杂度为 O(n^2)。原因如下： 1. 使用了一个二维布尔数组 palindrome ，其大小为 (n times n)，用于存储每个子串是否为回文串的状态。 2. 其他变量（如 length 、 index 、 i 、 j 等）所占用的空间是常数级别的，因此不影响总体的空间复杂度。

时间复杂度为 O(n^2)

空间复杂度为 O(n^2)

 s = "babad"

初始化

• 输入字符串 s = "babad"，长度为 5。
• length = 1，表示当前最长回文子串长度初始为 1。
• index = 0，表示最长回文子串起始索引初始为 0。
• palindrome 是一个 5x5 的二维布尔数组，用于记录子串是否为回文串。
• 初始化 palindrome[i][i] 为 true，即 palindrome[0][0]、palindrome[1][1]、palindrome[2][2]、palindrome[3][3]、palindrome[4][4] 都为 true，因为单个字符是回文串。

动态规划过程

当子串长度 L = 2

• i = 0，j = 1：
  • s.charAt(0) = 'b'，s.charAt(1) = 'a'，s.charAt(0) != s.charAt(1)，所以 palindrome[0][1] = false。
• i = 1，j = 2：
  • s.charAt(1) = 'a'，s.charAt(2) = 'b'，s.charAt(1) != s.charAt(2)，所以 palindrome[1][2] = false。
• i = 2，j = 3：
  • s.charAt(2) = 'b'，s.charAt(3) = 'a'，s.charAt(2) != s.charAt(3)，所以 palindrome[2][3] = false。
• i = 3，j = 4：
  • s.charAt(3) = 'a'，s.charAt(4) = 'd'，s.charAt(3) != s.charAt(4)，所以 palindrome[3][4] = false。

当子串长度 L = 3

• i = 0，j = 2：
  • s.charAt(0) = 'b'，s.charAt(2) = 'b'，s.charAt(0) == s.charAt(2)，且 j - i = 2 < 3，所以 palindrome[0][2] = true。
  • 此时子串长度 j - i + 1 = 3 > length，更新 length = 3，index = 0。
• i = 1，j = 3：
  • s.charAt(1) = 'a'，s.charAt(3) = 'a'，s.charAt(1) == s.charAt(3)，且 j - i = 2 < 3，所以 palindrome[1][3] = true。
  • 此时子串长度 j - i + 1 = 3，等于当前 length，不更新 length 和 index。
• i = 2，j = 4：
  • s.charAt(2) = 'b'，s.charAt(4) = 'd'，s.charAt(2) != s.charAt(4)，所以 palindrome[2][4] = false。

当子串长度 L = 4

• i = 0，j = 3：
  • s.charAt(0) = 'b'，s.charAt(3) = 'a'，s.charAt(0) != s.charAt(3)，所以 palindrome[0][3] = false。
• i = 1，j = 4：
  • s.charAt(1) = 'a'，s.charAt(4) = 'd'，s.charAt(1) != s.charAt(4)，所以 palindrome[1][4] = false。

当子串长度 L = 5

• i = 0，j = 4：
  • s.charAt(0) = 'b'，s.charAt(4) = 'd'，s.charAt(0) != s.charAt(4)，所以 palindrome[0][4] = false。

返回结果

最终，length = 3，index = 0，调用 s.substring(index, index + length) 即 s.substring(0, 3)，得到最长回文子串 "bab"，并将其返回。

所以，程序输出结果为：

最长回文子串是: bab

2.132. 分割回文串 II

力扣题目链接(opens new window)

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。

返回符合要求的 最少分割次数 。

示例 1：

输入：s = "aab" 输出：1 解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

示例 2： 输入：s = "a" 输出：0

示例 3： 输入：s = "ab" 输出：1

提示：

• 1 <= s.length <= 2000
• s 仅由小写英文字母组成

思路

这道题目回溯算法：131.分割回文串 (opens new window)。

关于回文子串，两道题目题目大家是一定要掌握的。

• 动态规划：647. 回文子串(opens new window)
• 5.最长回文子串 和 647.回文子串基本一样的

动规五部曲分析如下：

1. 确定dp数组（dp table）以及下标的含义

dp[i]：范围是[0, i]的回文子串，最少分割次数是dp[i]。

1. 确定递推公式

来看一下由什么可以推出dp[i]。

如果要对长度为[0, i]的子串进行分割，分割点为j。

那么如果分割后，区间[j + 1, i]是回文子串，那么dp[i] 就等于 dp[j] + 1。

这里可能有同学就不明白了，为什么只看[j + 1, i]区间，不看[0, j]区间是不是回文子串呢？

那么在回顾一下dp[i]的定义： 范围是[0, i]的回文子串，最少分割次数是dp[i]。

[0, j]区间的最小切割数量，我们已经知道了就是dp[j]。

此时就找到了递推关系，当切割点j在[0, i] 之间时候，dp[i] = dp[j] + 1;

本题是要找到最少分割次数，所以遍历j的时候要取最小的dp[i]。

所以最后递推公式为：dp[i] = min(dp[i], dp[j] + 1);

注意这里不是要 dp[j] + 1 和 dp[i]去比较，而是要在遍历j的过程中取最小的dp[i]！

可以有dp[j] + 1推出，当[j + 1, i] 为回文子串

1. dp数组如何初始化

首先来看一下dp[0]应该是多少。

dp[i]： 范围是[0, i]的回文子串，最少分割次数是dp[i]。

那么dp[0]一定是0，长度为1的字符串最小分割次数就是0。这个是比较直观的。

在看一下非零下标的dp[i]应该初始化为多少？

在递推公式dp[i] = min(dp[i], dp[j] + 1) 中我们可以看出每次要取最小的dp[i]。

那么非零下标的dp[i]就应该初始化为一个最大数，这样递推公式在计算结果的时候才不会被初始值覆盖！

如果非零下标的dp[i]初始化为0，在那么在递推公式中，所有数值将都是零。

非零下标的dp[i]初始化为一个最大数。

其实也可以这样初始化，更具dp[i]的定义，dp[i]的最大值其实就是i，也就是把每个字符分割出来。

1. 确定遍历顺序

根据递推公式：dp[i] = min(dp[i], dp[j] + 1);

j是在[0，i]之间，所以遍历i的for循环一定在外层，这里遍历j的for循环在内层才能通过 计算过的dp[j]数值推导出dp[i]。

代码里有一个isPalindromic函数，这是一个二维数组isPalindromic[i][j]，记录[i, j]是不是回文子串。

那么这个isPalindromic[i][j]是怎么的代码的呢？

就是其实这两道题目的代码：

• 647. 回文子串(opens new window)
• 5.最长回文子串

所以先用一个二维数组来保存整个字符串的回文情况。

1. 举例推导dp数组

以输入："aabc" 为例：

public class Partitioning_Palindromic_Strings {public int minCut(String s) {//如果输入字符串 s 为 null 或者为空字符串，那么不需要进行分割，直接返回 0。if (null == s || "".equals(s)) {return 0;}int len = s.length();//存储输入字符串 s 的长度。boolean[][] isPalindromic = new boolean[len][len];//二维布尔数组，isPalindromic[i][j] 表示从索引 i 到索引 j 的子串是否为回文串。for (int i = len - 1; i >= 0; i--) {//从字符串的最后一个字符开始向前遍历，索引为 i。for (int j = i; j < len; j++) {//从当前的 i 开始向后遍历到字符串末尾，索引为 j。if (s.charAt(i) == s.charAt(j)) {//如果子串的首尾字符相等if (j - i <= 1) {//当子串长度小于等于 2（j - i <= 1）时，该子串是回文串，将 isPalindromic[i][j] 设为 true。isPalindromic[i][j] = true;} else {//当子串长度大于 2 时，该子串是否为回文串取决于去掉首尾字符后的子串是否为回文串，即 isPalindromic[i][j] = isPalindromic[i + 1][j - 1]。isPalindromic[i][j] = isPalindromic[i + 1][j - 1];}} else {//如果子串的首尾字符不相等，将 isPalindromic[i][j] 设为 false。isPalindromic[i][j] = false;}}}int[] dp = new int[len];//一维数组，dp[i] 表示将从索引 0 到索引 i 的子串分割成若干个回文子串所需的最少分割次数。for (int i = 0; i < len; i++) {//初始时，假设每个字符都单独作为一个回文子串，那么分割次数就是当前字符的索引值。dp[i] = i;}for (int i = 1; i < len; i++) {//从索引 1 开始遍历到字符串末尾if (isPalindromic[0][i]) {//如果从索引 0 到索引 i 的子串是回文串（isPalindromic[0][i] 为 true），那么不需要分割，将 dp[i] 设为 0，并跳过本次循环。dp[i] = 0;continue;}for (int j = 0; j < i; j++) {//从索引 0 到 i - 1 遍历if (isPalindromic[j + 1][i]) {//如果从索引 j + 1 到索引 i 的子串是回文串（isPalindromic[j + 1][i] 为 true），那么可以将从索引 0 到索引 i 的子串分割成从索引 0 到索引 j 的子串和从索引 j + 1 到索引 i 的子串两部分。此时，dp[i] 可以更新为 dp[j] + 1 和当前 dp[i] 中的较小值。dp[i] = Math.min(dp[i], dp[j] + 1);}}}return dp[len - 1];//表示将整个字符串分割成若干个回文子串所需的最少分割次数}
}

 时间复杂度 该算法的时间复杂度为 O(n^2)，其中 n 是输入字符串 s的长度。原因如下： 1. 回文检查：在构建 isPalindromic 数组时，外层循环从后往前遍历字符串的每个字符（总共 n次），内层循环从当前字符向后遍历到字符串末尾（最多也是 n次）。因此，构建 isPalindromic 数组的时间复杂度是 O(n^2)。 2. 动态规划计算：在计算 dp 数组时，外层循环遍历每个字符（总共n 次），内层循环遍历从 0 到 i-1的所有可能的分割点（最多也是 n次）。因此，计算 dp 数组的时间复杂度同样是 O(n^2)。 综上所述，总的时间复杂度为 O(n^2)。

空间复杂度 该算法的空间复杂度为 O(n^2)。原因如下： 1. 回文检查数组：使用了一个二维布尔数组 isPalindromic ，其大小为 (n times n)，用于存储每个子串是否为回文串的状态。 2. 动态规划数组：还使用了一个一维数组 dp ，其大小为 n，用于存储从索引 0 到索引 i的子串分割成若干个回文子串所需的最少分割次数。 因此，总的空间复杂度为 O(n^2)（主要由 isPalindromic 数组决定）。

时间复杂度：O(n^2)

空间复杂度：O(n^2)

s = "aab"

初始化

• 输入字符串 s = "aab"，长度 len = 3。
• isPalindromic 是一个 3x3 的二维布尔数组，用于记录子串是否为回文串。
• dp 是一个长度为 3 的一维数组，初始值分别为 dp[0] = 0，dp[1] = 1，dp[2] = 2。

填充 isPalindromic 数组

外层循环 i 从 len - 1 到 0，内层循环 j 从 i 到 len - 1。

• 当 i = 2：
  • j = 2：
    • s.charAt(2) = 'b'，s.charAt(2) == s.charAt(2)，且 j - i = 0 <= 1，所以 isPalindromic[2][2] = true。
• 当 i = 1：
  • j = 1：
    • s.charAt(1) = 'a'，s.charAt(1) == s.charAt(1)，且 j - i = 0 <= 1，所以 isPalindromic[1][1] = true。
  • j = 2：
    • s.charAt(1) = 'a'，s.charAt(2) = 'b'，s.charAt(1) != s.charAt(2)，所以 isPalindromic[1][2] = false。
• 当 i = 0：
  • j = 0：
    • s.charAt(0) = 'a'，s.charAt(0) == s.charAt(0)，且 j - i = 0 <= 1，所以 isPalindromic[0][0] = true。
  • j = 1：
    • s.charAt(0) = 'a'，s.charAt(1) = 'a'，s.charAt(0) == s.charAt(1)，且 j - i = 1 <= 1，所以 isPalindromic[0][1] = true。
  • j = 2：
    • s.charAt(0) = 'a'，s.charAt(2) = 'b'，s.charAt(0) != s.charAt(2)，所以 isPalindromic[0][2] = false。

此时，isPalindromic 数组的值如下：

plaintext

[[true, true, false],[false, true, false],[false, false, true]
]

动态规划求解 dp 数组

• 当 i = 1：
  • isPalindromic[0][1] = true，说明从索引 0 到索引 1 的子串 "aa" 是回文串，不需要分割，所以 dp[1] = 0。
• 当 i = 2：
  • isPalindromic[0][2] = false，继续内层循环。
  • 当 j = 0：
    • isPalindromic[1][2] = false，不满足条件，不更新 dp[2]。
  • 当 j = 1：
    • isPalindromic[2][2] = true，此时可以将 "aab" 分割成 "aa" 和 "b" 两部分。
    • dp[2] = Math.min(dp[2], dp[1] + 1) = Math.min(2, 0 + 1) = 1。

返回结果

最终，dp[len - 1] = dp[2] = 1，表示将字符串 "aab" 分割成若干个回文子串所需的最少分割次数为 1，即分割为 "aa" 和 "b"。

所以，程序输出结果为：

将字符串分割成回文子串所需的最少分割次数为: 1

3.673.最长递增子序列的个数

力扣题目链接(opens new window)

给定一个未排序的整数数组，找到最长递增子序列的个数。

示例 1:

• 输入: [1,3,5,4,7]
• 输出: 2
• 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

示例 2:

• 输入: [2,2,2,2,2]
• 输出: 5
• 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

思路

这道题可以说是 300.最长上升子序列 (opens new window)的进阶版本

1. 确定dp数组（dp table）以及下标的含义

这道题目我们要一起维护两个数组。

dp[i]：i之前（包括i）最长递增子序列的长度为dp[i]

count[i]：以nums[i]为结尾的字符串，最长递增子序列的个数为count[i]

1. 确定递推公式

在300.最长上升子序列 中，我们给出的状态转移是：

if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

即：位置i的最长递增子序列长度 等于j从0到i-1各个位置的最长升序子序列 + 1的最大值。

本题就没那么简单了，我们要考虑两个维度，一个是dp[i]的更新，一个是count[i]的更新。

那么如何更新count[i]呢？

以nums[i]为结尾的字符串，最长递增子序列的个数为count[i]。

那么在nums[i] > nums[j]前提下，如果在[0, i-1]的范围内，找到了j，使得dp[j] + 1 > dp[i]，说明找到了一个更长的递增子序列。

那么以j为结尾的子串的最长递增子序列的个数，就是最新的以i为结尾的子串的最长递增子序列的个数，即：count[i] = count[j]。

在nums[i] > nums[j]前提下，如果在[0, i-1]的范围内，找到了j，使得dp[j] + 1 == dp[i]，说明找到了两个相同长度的递增子序列。

那么以i为结尾的子串的最长递增子序列的个数 就应该加上以j为结尾的子串的最长递增子序列的个数，即：count[i] += count[j];

这里count[i]记录了以nums[i]为结尾的字符串，最长递增子序列的个数。dp[i]记录了i之前（包括i）最长递增序列的长度。

题目要求最长递增序列的长度的个数，我们应该把最长长度记录下来。

1. dp数组如何初始化

再回顾一下dp[i]和count[i]的定义

count[i]记录了以nums[i]为结尾的字符串，最长递增子序列的个数。

那么最少也就是1个，所以count[i]初始为1。

dp[i]记录了i之前（包括i）最长递增序列的长度。

最小的长度也是1，所以dp[i]初始为1。

1. 确定遍历顺序

dp[i] 是由0到i-1各个位置的最长升序子序列 推导而来，那么遍历i一定是从前向后遍历。

j其实就是0到i-1，遍历i的循环里外层，遍历j则在内层,最后还有再遍历一遍dp[i]，把最长递增序列长度对应的count[i]累计下来就是结果了。

1. 举例推导dp数组

输入：[1,3,5,4,7]

public class Number_of_Longest_Increasing_Subsequences {public int findNumberOfLIS(int[] nums) {if (nums.length <= 1) return nums.length;//如果输入数组 nums 的长度小于等于 1，那么最长递增子序列的个数就是数组的长度，直接返回该长度。int[] dp = new int[nums.length];//dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。初始时，每个元素自身都可以构成一个长度为 1 的递增子序列，所以将 dp 数组的所有元素初始化为 1。Arrays.fill(dp, 1);int[] count = new int[nums.length];//count[i] 表示以 nums[i] 结尾的最长递增子序列的个数。同样，初始时每个元素自身构成的递增子序列个数为 1，所以将 count 数组的所有元素也初始化为 1。Arrays.fill(count, 1);int maxCount = 0;//用于记录最长递增子序列的长度。for (int i = 1; i < nums.length; i++) {//从索引 1 开始遍历数组 numsfor (int j = 0; j < i; j++) {//从索引 0 到 i - 1 遍历数组 numsif (nums[i] > nums[j]) {//如果 nums[i] > nums[j]，说明可以将 nums[i] 接在以 nums[j] 结尾的递增子序列后面。if (dp[j] + 1 > dp[i]) {//如果 dp[j] + 1 > dp[i]，说明找到了一个更长的以 nums[i] 结尾的递增子序列，更新 dp[i] = dp[j] + 1，同时更新 count[i] = count[j]，因为新的最长递增子序列的个数等于以 nums[j] 结尾的最长递增子序列的个数。dp[i] = dp[j] + 1;count[i] = count[j];} else if (dp[j] + 1 == dp[i]) {//如果 dp[j] + 1 == dp[i]，说明又找到了一种以 nums[i] 结尾的长度相同的最长递增子序列，将 count[i] 累加 count[j]。count[i] += count[j];}}if (dp[i] > maxCount) maxCount = dp[i];//每次更新 dp[i] 后，检查 dp[i] 是否大于 maxCount，如果是，则更新 maxCount。}}int result = 0;//用于存储最长递增子序列的个数。for (int i = 0; i < nums.length; i++) {//遍历 dp 数组，对于每个 dp[i]，如果其值等于 maxCount，说明以 nums[i] 结尾的最长递增子序列就是最长的，将对应的 count[i] 累加到 result 中。if (maxCount == dp[i]) result += count[i];}return result;}
}

 时间复杂度 该算法的时间复杂度为 O(n^2)，其中 n是输入数组 nums 的长度。原因如下： 1. 双重循环：外层循环遍历数组 nums 的每个元素（从索引 1 开始），总共进行 n-1次迭代。内层循环遍历从索引 0 到 i-1的所有元素（最多 i 次），因此内层循环的最坏情况也是 O(n)。 2. 因此，双重循环的总时间复杂度为 O(n^2)。

空间复杂度 该算法的空间复杂度为 O(n)。原因如下： 1. 动态规划数组：使用了两个一维数组 dp 和 count ，每个数组的大小都是 n，分别用于存储以每个元素结尾的最长递增子序列的长度和个数。 2. 其他变量（如 maxCount 和 result ）所占用的空间是常数级别的，因此不影响总体的空间复杂度。 综上所述，该算法的时间复杂度为 O(n^2)，空间复杂度为 O(n)。

时间复杂度：O(n^2) 

空间复杂度：O(n)

nums = [1, 3, 5, 4, 7]

初始化

• 输入数组 nums = [1, 3, 5, 4, 7]，数组长度为 5。
• dp 数组：初始化为 [1, 1, 1, 1, 1]，因为每个元素自身构成长度为 1 的递增子序列。
• count 数组：初始化为 [1, 1, 1, 1, 1]，每个元素自身构成的递增子序列个数为 1。
• maxCount 初始化为 0。

动态规划过程

当 i = 1（nums[i] = 3）

• 内层循环 j 从 0 到 0：
  • 因为 nums[1] > nums[0]（3 > 1），且 dp[0] + 1 = 2 > dp[1] = 1，所以更新 dp[1] = dp[0] + 1 = 2，count[1] = count[0] = 1。
  • 此时 dp[1] = 2 > maxCount = 0，更新 maxCount = 2。

此时 dp 数组为 [1, 2, 1, 1, 1]，count 数组为 [1, 1, 1, 1, 1]。

当 i = 2（nums[i] = 5）

• 内层循环 j 从 0 到 1：
  • 当 j = 0 时，nums[2] > nums[0]（5 > 1），且 dp[0] + 1 = 2 > dp[2] = 1，更新 dp[2] = dp[0] + 1 = 2，count[2] = count[0] = 1。
  • 当 j = 1 时，nums[2] > nums[1]（5 > 3），且 dp[1] + 1 = 3 > dp[2] = 2，更新 dp[2] = dp[1] + 1 = 3，count[2] = count[1] = 1。
  • 此时 dp[2] = 3 > maxCount = 2，更新 maxCount = 3。

此时 dp 数组为 [1, 2, 3, 1, 1]，count 数组为 [1, 1, 1, 1, 1]。

当 i = 3（nums[i] = 4）

• 内层循环 j 从 0 到 2：
  • 当 j = 0 时，nums[3] > nums[0]（4 > 1），且 dp[0] + 1 = 2 > dp[3] = 1，更新 dp[3] = dp[0] + 1 = 2，count[3] = count[0] = 1。
  • 当 j = 1 时，nums[3] > nums[1]（4 > 3），且 dp[1] + 1 = 3 > dp[3] = 2，更新 dp[3] = dp[1] + 1 = 3，count[3] = count[1] = 1。
  • 当 j = 2 时，nums[3] < nums[2]（4 < 5），不进行更新。

此时 dp 数组为 [1, 2, 3, 3, 1]，count 数组为 [1, 1, 1, 1, 1]。

当 i = 4（nums[i] = 7）

• 内层循环 j 从 0 到 3：
  • 当 j = 0 时，nums[4] > nums[0]（7 > 1），且 dp[0] + 1 = 2 > dp[4] = 1，更新 dp[4] = dp[0] + 1 = 2，count[4] = count[0] = 1。
  • 当 j = 1 时，nums[4] > nums[1]（7 > 3），且 dp[1] + 1 = 3 > dp[4] = 2，更新 dp[4] = dp[1] + 1 = 3，count[4] = count[1] = 1。
  • 当 j = 2 时，nums[4] > nums[2]（7 > 5），且 dp[2] + 1 = 4 > dp[4] = 3，更新 dp[4] = dp[2] + 1 = 4，count[4] = count[2] = 1。
  • 当 j = 3 时，nums[4] > nums[3]（7 > 4），且 dp[3] + 1 = 4 == dp[4]，更新 count[4] += count[3] = 2。
  • 此时 dp[4] = 4 > maxCount = 3，更新 maxCount = 4。

此时 dp 数组为 [1, 2, 3, 3, 4]，count 数组为 [1, 1, 1, 1, 2]。

计算最长递增子序列的个数

• 遍历 dp 数组，maxCount = 4，只有 dp[4] = 4，所以 result = count[4] = 2。

输出结果

最终返回 result = 2，即数组 [1, 3, 5, 4, 7] 中最长递增子序列的个数为 2，最长递增子序列为 [1, 3, 5, 7] 和 [1, 3, 4, 7]。

程序输出：

最长递增子序列的个数为: 2

图论

1.841.钥匙和房间

力扣题目链接(opens new window)

有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。

最初，除 0 号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true，否则返回 false。

示例 1：

• 输入: [[1],[2],[3],[]]
• 输出: true
• 解释: 我们从 0 号房间开始，拿到钥匙 1。 之后我们去 1 号房间，拿到钥匙 2。 然后我们去 2 号房间，拿到钥匙 3。 最后我们去了 3 号房间。 由于我们能够进入每个房间，我们返回 true。

示例 2：

• 输入：[[1,3],[3,0,1],[2],[0]]
• 输出：false
• 解释：我们不能进入 2 号房间。

思路

两个示例： [[1],[2],[3],[]] [[1,3],[3,0,1],[2],[0]]，画成对应的图如下：

我们可以看出图1的所有节点都是链接的，而图二中，节点2 是孤立的。

这就很容易让我们想起岛屿问题，只要发现独立的岛，就是不能进入所有房间。

此时也容易想到用并查集的方式去解决。

但本题是有向图，在有向图中，即使所有节点都是链接的，但依然不可能从0出发遍历所有边。 给大家举一个例子：

图3：[[5], [], [1, 3], [5]] ，如图：

在图3中，大家可以发现，节点0只能到节点5，然后就哪也去不了了。

所以本题是一个有向图搜索全路径的问题。 只能用深搜（DFS）或者广搜（BFS）来搜。

关于DFS的理论，如果大家有困惑，可以先看我这篇题解： DFS理论基础(opens new window)

深搜三部曲：

1. 确认递归函数，参数

需要传入二维数组rooms来遍历地图，需要知道当前我们拿到的key，以至于去下一个房间。

同时还需要一个数组，用来记录我们都走过了哪些房间，这样好知道最后有没有把所有房间都遍历的，可以定义一个一维数组。

1. 确认终止条件

这里有一个很重要的逻辑，就是在递归中，我们是处理当前访问的节点，还是处理下一个要访问的节点。

这决定 终止条件怎么写。

首先明确，本题中什么叫做处理，就是 visited数组来记录访问过的节点，该节点默认 数组里元素都是false，把元素标记为true就是处理 本节点了。

如果我们是处理当前访问的节点，当前访问的节点如果是 true ，说明是访问过的节点，那就终止本层递归，如果不是true，我们就把它赋值为true，因为这是我们处理本层递归的节点。

如果我们是处理下一层访问的节点，而不是当前层。那么就要在 深搜三部曲中第三步：处理目前搜索节点出发的路径的时候对 节点进行处理。

这样的话，就不需要终止条件，而是在 搜索下一个节点的时候，直接判断 下一个节点是否是我们要搜的节点。

1. 处理目前搜索节点出发的路径

有递归就有回溯，回溯就在递归函数的下面， 那么之前我们做的dfs题目，都需要回溯操作，例如：797.所有可能的路径 (opens new window)， 为什么本题就没有回溯呢？

本题是需要判断 0节点是否能到所有节点，那么我们就没有必要回溯去撤销操作了，只要遍历过的节点一律都标记上。

那什么时候需要回溯操作呢？

当我们需要搜索一条可行路径的时候，就需要回溯操作了，因为没有回溯，就没法“调头”， 如果不理解的话，去看我写的 797.所有可能的路径 (opens new window)的题解。

public class Keys_and_Rooms {
public boolean canVisitAllRooms3(List<List<Integer>> rooms) {int count = 1;//初始值为 1，因为一开始就可以访问 0 号房间，后续每访问一个新房间，count 就加 1。boolean[] visited = new boolean[rooms.size()];//长度为房间的数量，用于标记每个房间是否被访问过。将 visited[0] 设为 true，表示 0 号房间已被访问。visited[0] = true;Queue<Integer> queue = new ArrayDeque<>();//初始时将 0 号房间的编号加入队列，作为 BFS 的起始点。queue.add(0);while (!queue.isEmpty()) {//只要队列不为空，就继续进行搜索。int curKey = queue.poll();//从队列中取出一个房间编号 curKey，表示当前正在访问的房间。for (int key: rooms.get(curKey)) {//遍历当前房间的钥匙if (visited[key]) continue;//已经被访问过，跳过本次循环。++count;//如果该房间未被访问过，将 count 加 1，表示新访问了一个房间；将 visited[key] 设为 true，标记该房间已被访问。visited[key] = true;queue.add(key);//将 key 加入队列，表示后续需要访问该房间。}}return count == rooms.size();//比较 count 的值和房间的总数（rooms.size()）。如果相等，说明可以访问所有房间，返回 true；否则返回 false。}
}

时间复杂度 该算法的时间复杂度为 O(V + E)，其中 V是房间的数量，E 是钥匙的数量。原因如下： 1. 遍历房间：在 BFS 中，每个房间会被访问一次，因此对房间的访问时间复杂度为 O(V)。 2. 遍历钥匙：对于每个房间，可能会有多把钥匙（即房间中存储的整数）。在最坏情况下，所有房间的钥匙总数为 E。遍历所有钥匙的时间复杂度为 O(E)。 因此，总的时间复杂度为 O(V + E)。 #空间复杂度 该算法的空间复杂度为 O(V)。原因如下： 1. 访问标记数组：使用了一个布尔数组 visited ，其大小为 V，用于标记每个房间是否被访问过。 2. 队列：在 BFS 中，队列 queue 最多会存储 V 个房间的编号，因此队列的空间复杂度也是 O(V)。 综上所述，该算法的空间复杂度为 O(V)。

时间复杂度：O(V + E)

空间复杂度：O(V)

rooms = [[1, 3], [2], [3], [0]]

初始化

• 输入 rooms = [[1, 3], [2], [3], [0]]，这表示有 4 个房间，每个房间的钥匙情况如下：
  • 0 号房间有钥匙 1 和 3。
  • 1 号房间有钥匙 2。
  • 2 号房间有钥匙 3。
  • 3 号房间有钥匙 0。
• count 初始化为 1，因为一开始能访问 0 号房间。
• visited 数组初始化为 [false, false, false, false]，然后将 visited[0] 设为 true，即 [true, false, false, false]。
• 队列 queue 初始时加入 0 号房间的编号，queue = [0]。

广度优先搜索过程

第一次循环（当前房间为 0 号房间）

• 从队列 queue 中取出 curKey = 0，此时 queue = []。
• 遍历 0 号房间的钥匙列表 [1, 3]：
  • 对于钥匙 1，visited[1] 为 false，执行 ++count，count 变为 2；将 visited[1] 设为 true，此时 visited = [true, true, false, false]；将 1 加入队列，queue = [1]。
  • 对于钥匙 3，visited[3] 为 false，执行 ++count，count 变为 3；将 visited[3] 设为 true，此时 visited = [true, true, false, true]；将 3 加入队列，queue = [1, 3]。

第二次循环（当前房间为 1 号房间）

• 从队列 queue 中取出 curKey = 1，此时 queue = [3]。
• 遍历 1 号房间的钥匙列表 [2]，visited[2] 为 false，执行 ++count，count 变为 4；将 visited[2] 设为 true，此时 visited = [true, true, true, true]；将 2 加入队列，queue = [3, 2]。

第三次循环（当前房间为 3 号房间）

• 从队列 queue 中取出 curKey = 3，此时 queue = [2]。
• 遍历 3 号房间的钥匙列表 [0]，visited[0] 为 true，跳过本次循环。

第四次循环（当前房间为 2 号房间）

• 从队列 queue 中取出 curKey = 2，此时 queue = []。
• 遍历 2 号房间的钥匙列表 [3]，visited[3] 为 true，跳过本次循环。此时队列 queue 为空，循环结束。

判断是否能访问所有房间

房间总数 rooms.size() 为 4，count 的值也为 4，count == rooms.size() 条件成立，返回 true。

2.127. 单词接龙

力扣题目链接(opens new window)

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：

• 序列中第一个单词是 beginWord 。
• 序列中最后一个单词是 endWord 。
• 每次转换只能改变一个字母。
• 转换过程中的中间单词必须是字典 wordList 中的单词。
• 给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。

示例 1：

• 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
• 输出：5
• 解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：

• 输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
• 输出：0
• 解释：endWord "cog" 不在字典中，所以无法进行转换。

思路

以示例1为例，从这个图中可以看出 hit 到 cog的路线，不止一条，有三条，一条是最短的长度为5，两条长度为6。

本题只需要求出最短路径的长度就可以了，不用找出路径。

所以这道题要解决两个问题：

• 图中的线是如何连在一起的
• 起点和终点的最短路径长度

首先题目中并没有给出点与点之间的连线，而是要我们自己去连，条件是字符只能差一个，所以判断点与点之间的关系，要自己判断是不是差一个字符，如果差一个字符，那就是有链接。

然后就是求起点和终点的最短路径长度，这里无向图求最短路，广搜最为合适，广搜只要搜到了终点，那么一定是最短的路径。因为广搜就是以起点中心向四周扩散的搜索。

本题如果用深搜，会比较麻烦，要在到达终点的不同路径中选则一条最短路。 而广搜只要达到终点，一定是最短路。

另外需要有一个注意点：

• 本题是一个无向图，需要用标记位，标记着节点是否走过，否则就会死循环！
• 本题给出集合是数组型的，可以转成set结构，查找更快一些

也可以用双向BFS，就是从头尾两端进行搜索

public class Word_Ladder {public int ladderLength1(String beginWord, String endWord, List<String> wordList) {//beginWord：起始单词。endWord：目标单词。wordList：可供转换的单词列表。HashSet<String> wordSet = new HashSet<>(wordList); //转换为hashset 加快速度if (wordSet.size() == 0 || !wordSet.contains(endWord)) {  //如果 wordSet 为空或者不包含 endWord，则无法完成转换，直接返回 0。return 0;}Queue<String> queue = new LinkedList<>(); //用于 BFS 搜索。将 beginWord 加入队列。queue.offer(beginWord);Map<String, Integer> map = new HashMap<>(); //使用 HashMap 记录每个单词对应的最短路径长度。将 beginWord 的路径长度初始化为 1。map.put(beginWord, 1);while (!queue.isEmpty()) {String word = queue.poll(); //取出队头单词：从队列中取出一个单词 word，并获取其对应的路径长度 path。int path  = map.get(word);for (int i = 0; i < word.length(); i++) { //遍历单词的每个字符char[] chars = word.toCharArray(); //对于 word 中的每个字符位置 i，将其转换为字符数组 chars。for (char k = 'a'; k <= 'z'; k++) { //从 'a' 到 'z' 遍历，将 chars[i] 替换为当前字符 k，得到新的单词 newWord。chars[i] = k;String newWord = String.valueOf(chars);if (newWord.equals(endWord)) {  //如果 newWord 等于 endWord，则说明找到了最短转换序列，返回 path + 1。return path + 1;}if (wordSet.contains(newWord) && !map.containsKey(newWord)) { //如果 newWord 在 wordSet 中且还没有被访问过（即 map 中不包含该单词），则将其加入队列，并记录其路径长度为 path + 1。map.put(newWord, path + 1); //记录单词对应的路径长度queue.offer(newWord);//加入队尾}}}}return 0; //如果队列为空时还没有找到 endWord，则说明无法完成转换，返回 0。}
}

 时间复杂度 该算法的时间复杂度为 O(N cdot M cdot 26)，N是 wordList 中单词的数量。 M 是单词的长度（假设所有单词长度相同）。  26 是字母表中的字母数量（从 'a' 到 'z'）。 原因如下： 1. 队列操作：在 BFS 中，每个单词最多会被访问一次，因此在最坏情况下，所有单词都可能被加入队列进行处理，时间复杂度为 O(N)。 2. 字符替换：对于每个单词，我们需要遍历其每个字符并尝试替换为 26 个字母，因此对于每个单词的处理时间复杂度为 O(M cdot 26)。 3. 综合上述，整体的时间复杂度为 O(N cdot M cdot 26)，可以简化为 O(N cdot M)。

空间复杂度 该算法的空间复杂度为 O(N + M)，其中N是 wordList 中单词的数量（用于存储在 HashSet 和 HashMap 中）。 M 是单词的长度（用于存储当前单词的字符数组）。 原因如下： 1. 哈希集合：使用 HashSet 存储 wordList 中的单词，最坏情况下需要O(N)的空间。 2. 哈希映射：使用 HashMap 存储每个单词及其对应的路径长度，最坏情况下也需要 O(N) 的空间。 3. 字符数组：存储当前单词的字符数组占用 O(M)的空间。 综上所述，空间复杂度主要由 HashSet 和 HashMap 的大小决定，因此总体空间复杂度为 O(N + M)。

时间复杂度：O(N cdot M)

空间复杂度：O(N + M)

beginWord = "hit"，endWord = "cog"，wordList = ["hot", "dot", "dog", "lot", "log", "cog"]

初始化

• beginWord = "hit"，endWord = "cog"，wordList = ["hot", "dot", "dog", "lot", "log", "cog"]。
• wordSet = {"hot", "dot", "dog", "lot", "log", "cog"}。
• queue = ["hit"]。
• map = {"hit": 1}。

第一次循环（当前单词为 "hit"）

• 从队列中取出 word = "hit"，path = 1。
• 遍历 "hit" 的每个字符位置：
  • 当 i = 0 时，将 h 依次替换为 a 到 z 的字符：
    • 当替换为 h 到 o 时，得到 "hot"，"hot" 在 wordSet 中且不在 map 中，将 "hot" 加入 map 并设置路径长度为 path + 1 = 2，同时将 "hot" 加入队列。此时 map = {"hit": 1, "hot": 2}，queue = ["hot"]。
  • 当 i = 1 和 i = 2 时，替换后得到的其他新单词不在 wordSet 中，不做处理。

第二次循环（当前单词为 "hot"）

• 从队列中取出 word = "hot"，path = 2。
• 遍历 "hot" 的每个字符位置：
  • 当 i = 0 时，将 h 替换为 d 得到 "dot"，"dot" 在 wordSet 中且不在 map 中，将 "dot" 加入 map 并设置路径长度为 path + 1 = 3，同时将 "dot" 加入队列。此时 map = {"hit": 1, "hot": 2, "dot": 3}，queue = ["dot"]。
  • 当 i = 1 时，替换后得到的新单词不在 wordSet 中，不做处理。
  • 当 i = 2 时，将 t 替换为 l 得到 "lot"，"lot" 在 wordSet 中且不在 map 中，将 "lot" 加入 map 并设置路径长度为 path + 1 = 3，同时将 "lot" 加入队列。此时 map = {"hit": 1, "hot": 2, "dot": 3, "lot": 3}，queue = ["dot", "lot"]。

第三次循环（当前单词为 "dot"）

• 从队列中取出 word = "dot"，path = 3。
• 遍历 "dot" 的每个字符位置：
  • 当 i = 0 时，替换后得到的新单词不在 wordSet 中，不做处理。
  • 当 i = 1 时，替换后得到的新单词不在 wordSet 中，不做处理。
  • 当 i = 2 时，将 t 替换为 g 得到 "dog"，"dog" 在 wordSet 中且不在 map 中，将 "dog" 加入 map 并设置路径长度为 path + 1 = 4，同时将 "dog" 加入队列。此时 map = {"hit": 1, "hot": 2, "dot": 3, "lot": 3, "dog": 4}，queue = ["lot", "dog"]。

第四次循环（当前单词为 "lot"）

• 从队列中取出 word = "lot"，path = 3。
• 遍历 "lot" 的每个字符位置：
  • 当 i = 0 时，替换后得到的新单词不在 wordSet 中，不做处理。
  • 当 i = 1 时，替换后得到的新单词不在 wordSet 中，不做处理。
  • 当 i = 2 时，将 t 替换为 g 得到 "log"，"log" 在 wordSet 中且不在 map 中，将 "log" 加入 map 并设置路径长度为 path + 1 = 4，同时将 "log" 加入队列。此时 map = {"hit": 1, "hot": 2, "dot": 3, "lot": 3, "dog": 4, "log": 4}，queue = ["dog", "log"]。

第五次循环（当前单词为 "dog"）

• 从队列中取出 word = "dog"，path = 4。
• 遍历 "dog" 的每个字符位置：
  • 当 i = 0 时，替换后得到的新单词不在 wordSet 中，不做处理。
  • 当 i = 1 时，替换后得到的新单词不在 wordSet 中，不做处理。
  • 当 i = 2 时，将 g 替换为 c 得到 "cog"，"cog" 等于 endWord，返回 path + 1 = 5。

输出结果

程序输出：

最短转换序列的长度为: 5

最短转换序列为 "hit" -> "hot" -> "dot" -> "dog" -> "cog"。

并查集

1.684.冗余连接

力扣题目链接(opens new window)

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

提示:

• n == edges.length
• 3 <= n <= 1000
• edges[i].length == 2
• 1 <= ai < bi <= edges.length
• ai != bi
• edges 中无重复元素
• 给定的图是连通的

思路

主要就是集合问题，两个节点在不在一个集合，也可以将两个节点添加到一个集合中。

并查集主要有三个功能。

1. 寻找根节点，函数：find(int u)，也就是判断这个节点的祖先节点是哪个
2. 将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点上
3. 判断两个节点是否在同一个集合，函数：isSame(int u, int v)，就是判断两个节点是不是同一个根节点

如果还不了解并查集，可以看这里：并查集理论基础(opens new window)

题目说是无向图，返回一条可以删去的边，使得结果图是一个有着N个节点的树（即：只有一个根节点）。

如果有多个答案，则返回二维数组中最后出现的边。

那么我们就可以从前向后遍历每一条边（因为优先让前面的边连上），边的两个节点如果不在同一个集合，就加入集合（即：同一个根节点）。

如图所示：

节点A 和节点 B 不在同一个集合，那么就可以将两个 节点连在一起。

（如果题目中说：如果有多个答案，则返回二维数组中最前出现的边。 那我们就要 从后向前遍历每一条边了）

如果边的两个节点已经出现在同一个集合里，说明着边的两个节点已经连在一起了，再加入这条边一定就出现环了。

如图所示：

已经判断 节点A 和 节点B 在在同一个集合（同一个根），如果将 节点A 和 节点B 连在一起就一定会出现环。

主函数的代码很少，就判断一下边的两个节点在不在同一个集合就可以了。

并查集（Union-Find），也称为不相交集合数据结构（Disjoint Set Data Structure），是一种用于处理不相交集合的合并与查询问题的数据结构。它支持两种主要操作：查找（Find）和合并（Union），并可以高效地判断两个元素是否属于同一个集合。

主要操作

1. 查找（Find）

查找操作用于确定某个元素所属的集合。通常会找到该集合的代表元素（也称为根元素），通过比较两个元素的代表元素是否相同，可以判断它们是否属于同一个集合。

2. 合并（Union）

合并操作用于将两个不相交的集合合并成一个集合。具体做法是将一个集合的代表元素指向另一个集合的代表元素

public class Redundant_Connection {private int[] father;//是并查集中用于记录每个节点的父节点的数组，father[i] 表示节点 i 的父节点。public void Solution() {//初始化并查集，将每个节点的父节点初始化为自身。int n = 1005;//创建一个长度为 1005 的 father 数组，并将数组中每个元素初始化为其索引值，表示每个节点的父节点是它自己。father = new int[n];for (int i = 0; i < n; ++i) {father[i] = i;}}private int find(int u) {//查找节点 u 的根节点if (u == father[u]) {//如果 u 等于 father[u]，说明 u 是根节点，直接返回 u。return u;}father[u] = find(father[u]);//否则，递归地查找 father[u] 的根节点，并将 u 的父节点直接设置为根节点，实现路径压缩。return father[u];}private void join(int u, int v) {//将节点 u 和节点 v 所在的集合合并。u = find(u);//首先分别查找 u 和 v 的根节点。v = find(v);if (u == v) return;//如果它们的根节点相同，说明它们已经在同一个集合中，直接返回。father[v] = u;//否则，将 v 的根节点的父节点设置为 u 的根节点，完成集合的合并。}private Boolean same(int u, int v) {//判断节点 u 和节点 v 是否在同一个集合中。u = find(u);//分别查找 u 和 v 的根节点，如果它们的根节点相同，则返回 true，否则返回 false。v = find(v);return u == v;}public int[] findRedundantConnection(int[][] edges) {//遍历给定的边数组，找出导致图中出现环的冗余连接。for (int[] edge : edges) {//对于每条边 edge，使用 same 方法判断边的两个端点是否在同一个集合中。if (same(edge[0], edge[1])) {//如果在同一个集合中，说明加入这条边会形成环，这条边就是冗余连接，直接返回该边。return edge;} else {//否则，使用 join 方法将边的两个端点所在的集合合并。join(edge[0], edge[1]);}}return null;//如果遍历完所有边都没有找到冗余连接，返回 null。}
}

时间复杂度 该算法的时间复杂度为 O(alpha(N) + E)，其中N 是节点的数量（在这里是 1005）。 E是边的数量（即输入的 edges 数组的长度）。 (alpha(N)) 是阿克曼函数的反函数，表示并查集的查找和合并操作的时间复杂度，通常被认为是常数时间（对于实际应用，(alpha(N)) 的最大值非常小，通常小于 5）。 原因如下： 1. 查找操作：在 find 方法中，每次查找节点的根节点，时间复杂度为 O(alpha(N)))。 2. 合并操作：在 join 方法中，合并两个集合的操作也是 O(alpha(N)))。 3. 遍历边：在 findRedundantConnection 方法中，遍历所有边的时间复杂度为 O(E)。 因此，总的时间复杂度为 O(E + alpha(N))，在实际应用中可以简化为 O(E)。

空间复杂度 该算法的空间复杂度为 O(N)，其中 N是节点的数量（在这里是 1005）。 原因如下： 1. 父节点数组：使用了一个大小为 N 的数组 father 来存储每个节点的父节点，因此占用 O(N) 的空间。 2. 其他变量（如 edge 和临时变量）所占用的空间是常数级别，因此不影响总体的空间复杂度。

时间复杂度：O(E) 

空间复杂度：O(N)

edges = [[1, 2], [1, 3], [2, 3]]

初始化

在 main 方法中创建 Redundant_Connection 类的实例，并调用 Solution 方法进行初始化

此时 father 数组被初始化为 [0, 1, 2, ..., 1004]，表示每个节点的父节点是它自己。

处理第一条边 [1, 2]

int[][] edges = {{1, 2}, {1, 3}, {2, 3}};

• 调用 same(1, 2) 方法：
  • 在 same 方法中，分别调用 find(1) 和 find(2)。由于初始时 father[1] = 1，father[2] = 2，所以 find(1) 返回 1，find(2) 返回 2，1 != 2，same(1, 2) 返回 false。
• 调用 join(1, 2) 方法：
  • 在 join 方法中，find(1) 返回 1，find(2) 返回 2，因为 1 != 2，将 father[2] 设置为 1，即节点 2 的父节点变为 1。此时 father 数组中 father[1] = 1，father[2] = 1。

处理第二条边 [1, 3]

• 调用 same(1, 3) 方法：
  • find(1) 返回 1，find(3) 返回 3，1 != 3，same(1, 3) 返回 false。
• 调用 join(1, 3) 方法：
  • find(1) 返回 1，find(3) 返回 3，因为 1 != 3，将 father[3] 设置为 1，即节点 3 的父节点变为 1。此时 father 数组中 father[1] = 1，father[2] = 1，father[3] = 1。

处理第三条边 [2, 3]

• 调用 same(2, 3) 方法：
  • find(2) 返回 1（因为 father[2] = 1），find(3) 返回 1（因为 father[3] = 1），1 == 1，same(2, 3) 返回 true。
• 由于 same(2, 3) 返回 true，说明加入边 [2, 3] 会形成环，所以 findRedundantConnection 方法返回 [2, 3]。

输出结果

程序输出：

冗余连接为: [2, 3]

2.冗余连接II 

力扣题目链接(opens new window)

在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。

输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。

结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。

返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

提示：

• n == edges.length
• 3 <= n <= 1000
• edges[i].length == 2
• 1 <= ui, vi <= n\

思路

先重点读懂题目中的这句该图由一个有着N个节点 (节点值不重复1, 2, ..., N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。

这说明题目中的图原本是是一棵树，只不过在不增加节点的情况下多加了一条边！

还有**若有多个答案，返回最后出现在给定二维数组的答案。**这说明在两条边都可以删除的情况下，要删顺序靠后的！

那么有如下三种情况，前两种情况是出现入度为2的点，如图：

且只有一个节点入度为2，为什么不看出度呢，出度没有意义，一棵树中随便一个父节点就有多个出度。

第三种情况是没有入度为2的点，那么图中一定出现了有向环（注意这里强调是有向环！）

如图：

首先先计算节点的入度，这里不少录友在计算入度的时候就搞蒙了，分不清 edges[i][j] 表示的都是什么。

例如题目示例一给的是：edges = [[1,2],[1,3],[2,3]]

那大家很自然就想 对应二维数组的数值是： edges[1][2] ，edges[1][3]，edges[2][3]，但又想不出来 edges[1][2] 数值又是什么呢？ 越想约懵。

其实 edges = [[1,2],[1,3],[2,3]]，表示的是

edges[0][0] = 1，edges[0][1] = 2，

edges[1][0] = 1，edges[1][1] = 3，

edges[2][0] = 2，edges[2][1] = 3，

二维数组大家都学过，但是往往和图结合在一起的时候，就非常容易搞混，哪里是数组，哪里是下标了。

搞清楚之后，我们如何统计入度呢？

即 edges[i][1] 表示的节点都是 箭头指向的节点，即这个节点有一个入度！ （如果想统计出度，那么就是 edges[i][0]）。

前两种入度为2的情况，一定是删除指向入度为2的节点的两条边其中的一条，如果删了一条，判断这个图是一个树，那么这条边就是答案，同时注意要从后向前遍历，因为如果两条边删哪一条都可以成为树，就删最后那一条。

在来看情况三，明确没有入度为2的情况，那么一定有向环，找到构成环的边就是要删除的边。

要实现两个最为关键的函数：

• isTreeAfterRemoveEdge() 判断删一个边之后是不是树了
• getRemoveEdge 确定图中一定有了有向环，那么要找到需要删除的那条边

此时应该是用到并查集了，并查集为什么可以判断 一个图是不是树呢？

因为如果两个点所在的边在添加图之前如果就可以在并查集里找到了相同的根，那么这条边添加上之后 这个图一定不是树了

如果还不了解并查集，可以看这里：并查集理论基础(opens new window)

public class Redundant_ConnectionII {private static final int N = 1010;//一个常量，用于定义数组的大小，这里设置为 1010，意味着可以处理最多 1010 个节点的图。private int[] father;//并查集数组，father[i] 表示节点 i 的父节点。public void Solution() {//用于初始化并查集，将每个节点的父节点初始化为自身。father = new int[N];for (int i = 0; i < N; ++i) {father[i] = i;}}private int find(int u) {//用于查找节点 u 的根节点，并进行路径压缩，提高后续查找效率。if(u == father[u]) {return u;}father[u] = find(father[u]);return father[u];}private void join(int u, int v) {//将节点 u 和 v 所在的集合合并。如果它们已经在同一个集合中（根节点相同），则不进行操作。u = find(u);v = find(v);if (u == v) return ;father[v] = u;}private Boolean same(int u, int v) {//判断节点 u 和 v 是否在同一个集合中，即它们的根节点是否相同。u = find(u);v = find(v);return u == v;}private void initFather() {//重新初始化并查集，将每个节点的父节点重置为自身。for (int i = 0; i < N; ++i) {father[i] = i;}}private int[] getRemoveEdge(int[][] edges) {//找出会导致图中形成环的边。initFather();//调用 initFather 方法初始化并查集。for (int[] edge : edges) {//遍历每条边，使用 same 方法判断边的两个端点是否在同一个集合中。如果是，则说明加入这条边会形成环，返回该边。if (same(edge[0], edge[1])) {return edge;}//如果没有形成环，则使用 join 方法将边的两个端点所在的集合合并。join(edge[0], edge[1]);}return null;//如果遍历完所有边都没有找到形成环的边，返回 null。}private Boolean isTreeAfterRemoveEdge(int[][] edges, int deleteEdge)//判断移除指定边后，图是否能成为一棵树（无环）。{initFather();//调用 initFather 方法初始化并查集。for(int i = 0; i < edges.length; i++){if(i == deleteEdge) continue;//遍历每条边，跳过指定要移除的边。if(same(edges[i][0], edges[i][1])) {//使用 same 方法判断边的两个端点是否在同一个集合中。如果是，则说明加入这条边会形成环，返回 false。return false;}join(edges[i][0], edges[i][1]);//如果没有形成环，则使用 join 方法将边的两个端点所在的集合合并。}return true;//如果遍历完所有边都没有形成环，返回 true。}public int[] findRedundantDirectedConnection(int[][] edges) {//找出冗余连接。int[] inDegree = new int[N];//统计每个节点的入度，存储在 inDegree 数组中。for (int[] edge : edges) {inDegree[edge[1]] += 1;}ArrayList<Integer> twoDegree = new ArrayList<Integer>();for(int i = edges.length - 1; i >= 0; i--)//从后往前遍历边，找出入度为 2 的节点对应的边的索引，存储在 twoDegree 列表中。{if(inDegree[edges[i][1]] == 2) {//如果 twoDegree 列表不为空，说明存在入度为 2 的节点：尝试移除 twoDegree 列表中的第一条边，调用 isTreeAfterRemoveEdge 方法判断移除后图是否能成为树。如果可以，返回这条边。否则，返回 twoDegree 列表中的第二条边。twoDegree.add(i);}}if(!twoDegree.isEmpty())//如果 twoDegree 列表为空，说明不存在入度为 2 的节点，调用 getRemoveEdge 方法找出会形成环的边并返回。{if(isTreeAfterRemoveEdge(edges, twoDegree.get(0))) {return edges[ twoDegree.get(0)];}return edges[ twoDegree.get(1)];}return getRemoveEdge(edges);}
}

时间复杂度 该算法的时间复杂度为 O(E)，其中 E 是输入边的数量。 1. 计算入度：遍历所有边以计算每个节点的入度，时间复杂度为 O(E)。 2. 找出入度为 2 的边：再次遍历边以找出入度为 2 的节点，时间复杂度为 O(E)。 3. 判断是否可以形成树：在 isTreeAfterRemoveEdge 方法中，最坏情况下也需要遍历所有边，时间复杂度为 O(E)。 4. 查找冗余连接：在 getRemoveEdge 方法中，最坏情况下也需要遍历所有边，时间复杂度为 O(E)。 综上所述，所有操作的时间复杂度都是线性的，因此总的时间复杂度为 O(E)。

空间复杂度 该算法的空间复杂度为 O(N)，其中 N是节点的数量（在这里是 1010）。 1. 父节点数组：使用了一个大小为 N的数组 father 来存储每个节点的父节点，因此占用 O(N) 的空间。 2. 入度数组：使用了一个大小为 N的数组 inDegree 来存储每个节点的入度，因此也占用 O(N)的空间。 3. 列表：使用了一个 ArrayList 来存储入度为 2 的边的索引，最坏情况下也会占用 O(N)的空间。 因此，总的空间复杂度为 O(N)。

时间复杂度：O(E)

空间复杂度：O(N)

edges = [[1, 2], [1, 3], [2, 3]]

1. 初始化

在 main 方法中，创建 Redundant_ConnectionII 类的实例，并调用 Solution 方法初始化并查集：

此时 father 数组被初始化为 [0, 1, 2, ..., 1009]，每个节点的父节点是其自身。

2. 进入 findRedundantDirectedConnection 方法

统计入度

• 对于边 [1, 2]，inDegree[2] 变为 1。
• 对于边 [1, 3]，inDegree[3] 变为 1。
• 对于边 [2, 3]，inDegree[3] 变为 2。 此时 inDegree 数组中 inDegree[2] = 1，inDegree[3] = 2。

找出入度为 2 的边的索引

从后往前遍历边，边 [2, 3] 的终点 3 的入度为 2，其索引为 2；边 [1, 3] 的终点 3 的入度也为 2，其索引为 1。所以 twoDegree 列表为 [2, 1]。

判断是否存在入度为 2 的节点

• 调用 isTreeAfterRemoveEdge(edges, 2)：
  • 首先在 isTreeAfterRemoveEdge 方法中调用 initFather 方法，将 father 数组重置为 [0, 1, 2, ..., 1009]。
  • 遍历边，跳过索引为 2 的边 [2, 3]。
    • 处理边 [1, 2]：调用 same(1, 2)，此时 find(1) 返回 1，find(2) 返回 2，same(1, 2) 为 false，调用 join(1, 2)，将 father[2] 设置为 1。
    • 处理边 [1, 3]：调用 same(1, 3)，此时 find(1) 返回 1，find(3) 返回 3，same(1, 3) 为 false，调用 join(1, 3)，将 father[3] 设置为 1。
  • 遍历完所有边都没有形成环，isTreeAfterRemoveEdge(edges, 2) 返回 true。
• 由于 isTreeAfterRemoveEdge(edges, 2) 返回 true，所以返回 edges[2]，即 [2, 3]。

输出结果

冗余连接为: [2, 3]

模拟位

1.657. 机器人能否返回原点

力扣题目链接(opens new window)

在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。

移动顺序由字符串表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。

注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。

示例 1:

• 输入: "UD"
• 输出: true
• 解释：机器人向上移动一次，然后向下移动一次。所有动作都具有相同的幅度，因此它最终回到它开始的原点。因此，我们返回 true。

示例 2:

• 输入: "LL"
• 输出: false
• 解释：机器人向左移动两次。它最终位于原点的左侧，距原点有两次 “移动” 的距离。我们返回 false，因为它在移动结束时没有返回原点。

思路

其实就是，x，y坐标，初始为0，然后：

• if (moves[i] == 'U') y++;
• if (moves[i] == 'D') y--;
• if (moves[i] == 'L') x--;
• if (moves[i] == 'R') x++;

最后判断一下x，y是否回到了(0, 0)位置就可以了。

如图所示： 

public class Can_the_robot_return_to_the_origin {public boolean judgeCircle(String moves) {int x = 0;//x 和 y 分别表示机器人在二维平面上的 x 坐标和 y 坐标，初始值都为 0，即机器人初始位置在原点 (0, 0)。int y = 0;for (char c : moves.toCharArray()) {//moves.toCharArray() 将字符串 moves 转换为字符数组，以便遍历其中的每个字符。if (c == 'U') y++;//if (c == 'U') y++;：如果当前字符是 'U'，表示机器人向上移动一步，y 坐标加 1。if (c == 'D') y--;：如果当前字符是 'D'，表示机器人向下移动一步，y 坐标减 1。if (c == 'L') x++;：如果当前字符是 'L'，表示机器人向左移动一步，x 坐标加 1。if (c == 'R') x--;：如果当前字符是 'R'，表示机器人向右移动一步，x 坐标减 1。if (c == 'D') y--;if (c == 'L') x++;if (c == 'R') x--;}return x == 0 && y == 0;//如果 x 坐标和 y 坐标都为 0，说明机器人回到了原点，返回 true；否则返回 false。}
}

 时间复杂度 该算法的时间复杂度为 O(n)，其中 n 是输入字符串 moves 的长度。 原因如下： 1. 遍历字符：算法通过一个循环遍历字符串中的每个字符。每次循环内的操作（检查字符并更新坐标）都是常数时间操作。 2. 因此，总的时间复杂度为 O(n)。

空间复杂度 该算法的空间复杂度为 O(1)。 原因如下： 1. 常数空间：算法只使用了常数数量的额外变量（ x 和 y ），不依赖于输入字符串的大小。因此，空间复杂度是常数级别的 O(1)。 2. 不论输入字符串的长度如何，所需的额外空间都是固定的。

时间复杂度：O(n)

空间复杂度：O(1)

moves = "UDR"

1. 初始化：
   • x = 0，y = 0，机器人初始位置在原点 (0, 0)。
2. 遍历指令：
   • 当 c = 'U' 时，执行 y++，此时 y = 1，x = 0，机器人位置变为 (0, 1)。
   • 当 c = 'D' 时，执行 y--，此时 y = 0，x = 0，机器人位置回到 (0, 0)。
   • 当 c = 'R' 时，执行 x--，此时 x = -1，y = 0，机器人位置变为 (-1, 0)。
3. 判断结果：
   • 因为 x == 0 && y == 0 为 false，返回 false，说明机器人不能回到原点。

2.31.下一个排列

力扣题目链接(opens new window)

实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须 原地 修改，只允许使用额外常数空间。

示例 1：

• 输入：nums = [1,2,3]
• 输出：[1,3,2]

示例 2：

• 输入：nums = [3,2,1]
• 输出：[1,2,3]

示例 3：

• 输入：nums = [1,1,5]
• 输出：[1,5,1]

示例 4：

• 输入：nums = [1]
• 输出：[1]

思路

以1234为例子，把全排列都列出来。可以参考一下规律所在：

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

如图：

以求1243为例，流程如图：

public class Next_Permutation {public void nextPermutation1(int[] nums) {for (int i = nums.length - 1; i >= 0; i--) {//从数组的最后一个元素开始向前遍历，索引为 i。for (int j = nums.length - 1; j > i; j--) {//对于每个 i，从数组的最后一个元素开始，到 i + 1 位置结束，索引为 j。if (nums[j] > nums[i]) {//当找到 nums[j] > nums[i] 时，说明找到了可以交换的位置，将 nums[i] 和 nums[j] 交换。int temp = nums[i];nums[i] = nums[j];nums[j] = temp;Arrays.sort(nums, i + 1, nums.length);//交换后，为了得到下一个字典序排列，需要将 i + 1 到数组末尾的元素按升序排序，使用 Arrays.sort(nums, i + 1, nums.length) 实现。return;//交换并排序后，直接返回，因为已经找到了下一个排列。}}}Arrays.sort(nums);//如果双重循环都没有找到可以交换的位置，说明当前排列已经是最大的排列（降序排列）。此时，将整个数组按升序排序，得到最小的排列。}
}

 时间复杂度 该算法的时间复杂度为 O(n^2)，其中 n 是输入数组 nums 的长度。原因如下： 1. 双重循环：外层循环遍历数组的每个元素，最坏情况下需要遍历 n 次。内层循环也可能遍历 n次，因此双重循环的时间复杂度为 O(n^2)。 2. 排序：在找到可以交换的元素后，使用 Arrays.sort(nums, i + 1, nums.length) 对数组的后半部分进行排序，最坏情况下的时间复杂度也是 O(n \log n)。 3. 因此，总的时间复杂度为 O(n^2)，因为 O(n^2)的增长速度比 O(n \log n) 要快。

空间复杂度 该算法的空间复杂度为 O(1)。 原因如下： 1. 常数空间：算法只使用了常数数量的额外变量（如 temp ），不依赖于输入数组的大小。因此，空间复杂度是常数级别的 O(1)。 2. 排序方法：虽然使用了 Arrays.sort ，但这个排序是在原数组上进行的，不需要额外的空间来存储新的数组。

时间复杂度：O(n^2)

空间复杂度：O(1)

nums = [1, 2, 3]

初始状态

• 输入数组 nums = [1, 2, 3]。

第一次外层循环（i = 2）

• 内层循环：
  • 当 j = 2 时，由于 j > i 不成立，内层循环不执行。

第二次外层循环（i = 1）

• 内层循环：
  • 当 j = 2 时，比较 nums[j]（值为 3）和 nums[i]（值为 2），因为 3 > 2，满足 nums[j] > nums[i] 的条件。
  • 交换 nums[i] 和 nums[j] 的值：
    • 临时变量 temp = nums[i] = 2。
    • nums[i] = nums[j] = 3。
    • nums[j] = temp = 2。此时数组变为 [1, 3, 2]。
  • 对 i + 1 到数组末尾的元素进行排序，即对索引从 2 到 2 的元素排序（这里元素本身就是有序的）。
  • 执行 return 语句，方法结束。

输出结果

原排列: [1, 2, 3]
下一个排列: [1, 3, 2]

3.463. 岛屿的周长

力扣题目链接(opens new window)

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

• 输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
• 输出：16
• 解释：它的周长是上面图片中的 16 个黄色的边

示例 2：

• 输入：grid = [[1]]
• 输出：4

示例 3：

• 输入：grid = [[1,0]]
• 输出：4

提示：

• row == grid.length
• col == grid[i].length
• 1 <= row, col <= 100
• grid[i][j] 为 0 或 1

解法一：

遍历每一个空格，遇到岛屿，计算其上下左右的情况，遇到水域或者出界的情况，就可以计算边了。

如图：

解法二：

计算出总的岛屿数量，因为有一对相邻两个陆地，边的总数就减2，那么在计算出相邻岛屿的数量就可以了。

result = 岛屿数量 * 4 - cover * 2;

如图：

public class Perimeter_of_the_island {
public int islandPerimeter2(int[][] grid) {int landSum = 0;//用于记录网格中陆地（值为 1）的总数量。int cover = 0;//用于记录陆地之间相邻边的数量。因为每有一条相邻边，就意味着在计算陆地总周长时多算了两条边（比如两块相邻陆地，原本每块陆地有 4 条边，相邻后它们之间的两条边就不再是岛屿的周长边界了）。for (int i = 0; i < grid.length; i++) {//遍历二维网格 grid 中的每一个元素。for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] == 1) {//当前位置是陆地landSum++;//陆地数量加 1。if(i - 1 >= 0 && grid[i-1][j] == 1) cover++;//检查当前陆地的上方位置是否也是陆地。如果 i - 1 >= 0（确保不越界）且上方位置 grid[i - 1][j] 也是陆地，说明这两块陆地相邻，相邻边数量 cover 加 1。if(j - 1 >= 0 && grid[i][j-1] == 1) cover++;//检查当前陆地的左方位置是否也是陆地。如果 j - 1 >= 0（确保不越界）且左方位置 grid[i][j - 1] 也是陆地，相邻边数量 cover 加 1。}}}return landSum * 4 - cover * 2;//每一块陆地原本有 4 条边，所以陆地的总边数为 landSum * 4。但是每有一条相邻边，就会在总边数中多算了两条边（因为相邻的两条边不再是岛屿的周长边界），所以要减去 cover * 2。最终得到岛屿的周长。}
}

 时间复杂度 该算法的时间复杂度为 O(m times n)，其中 m 是网格的行数，n 是网格的列数。 原因如下： 1. 遍历网格：算法通过双重循环遍历整个二维网格 grid ，每个元素只被访问一次。因此，时间复杂度为 O(m times n)。

空间复杂度 该算法的空间复杂度为 O(1)。 原因如下： 1. 常数空间：算法只使用了常数数量的额外变量（如 landSum 和 cover ），不依赖于输入网格的大小。因此，空间复杂度是常数级别的 O(1)。

时间复杂度：O(m times n)

空间复杂度：O(1)

{0, 1, 0, 0},

{1, 1, 1, 0}

{0, 1, 0, 0}

{1, 1, 0, 0}

初始状态

• landSum = 0：用于记录陆地的总数。

• cover = 0：用于记录相邻陆地之间重合的边数。

遍历网格

• 第一行 i = 0

  • 当 j = 0 时，grid[0][0] = 0，不是陆地，跳过。

  • 当 j = 1 时，grid[0][1] = 1，是陆地：

    • landSum 加 1，此时 landSum = 1。

    • 检查上方位置 i - 1 = -1 < 0，越界；检查左方位置 j - 1 = 0，grid[0][0] = 0 不是陆地，所以 cover 不变，仍为 0。

  • 当 j = 2 和 j = 3 时，grid[0][2] = 0，grid[0][3] = 0，不是陆地，跳过。

• 第二行 i = 1

  • 当 j = 0 时，grid[1][0] = 1，是陆地：

    • landSum 加 1，此时 landSum = 2。

    • 检查上方位置 i - 1 = 0，grid[0][0] = 0 不是陆地；检查左方位置 j - 1 = -1 < 0，越界，所以 cover 不变，仍为 0。

  • 当 j = 1 时，grid[1][1] = 1，是陆地：

    • landSum 加 1，此时 landSum = 3。

    • 检查上方位置 i - 1 = 0，grid[0][1] = 1，是陆地，cover 加 1，此时 cover = 1。

    • 检查左方位置 j - 1 = 0，grid[1][0] = 1，是陆地，cover 加 1，此时 cover = 2。

  • 当 j = 2 时，grid[1][2] = 1，是陆地：

    • landSum 加 1，此时 landSum = 4。

    • 检查上方位置 i - 1 = 0，grid[0][2] = 0 不是陆地；检查左方位置 j - 1 = 1，grid[1][1] = 1，是陆地，cover 加 1，此时 cover = 3。

  • 当 j = 3 时，grid[1][3] = 0，不是陆地，跳过。

• 第三行 i = 2

  • 当 j = 0 时，grid[2][0] = 0，不是陆地，跳过。

  • 当 j = 1 时，grid[2][1] = 1，是陆地：

    • landSum 加 1，此时 landSum = 5。

    • 检查上方位置 i - 1 = 1，grid[1][1] = 1，是陆地，cover 加 1，此时 cover = 4。

    • 检查左方位置 j - 1 = 0，grid[2][0] = 0 不是陆地，cover 不变。

  • 当 j = 2 和 j = 3 时，grid[2][2] = 0，grid[2][3] = 0，不是陆地，跳过。

• 第四行 i = 3

  • 当 j = 0 时，grid[3][0] = 1，是陆地：

    • landSum 加 1，此时 landSum = 6。

    • 检查上方位置 i - 1 = 2，grid[2][0] = 0 不是陆地；检查左方位置 j - 1 = -1 < 0，越界，所以 cover 不变，仍为 4。

  • 当 j = 1 时，grid[3][1] = 1，是陆地：

    • landSum 加 1，此时 landSum = 7。

    • 检查上方位置 i - 1 = 2，grid[2][1] = 1，是陆地，cover 加 1，此时 cover = 5。

    • 检查左方位置 j - 1 = 0，grid[3][0] = 1，是陆地，cover 加 1，此时 cover = 6。

  • 当 j = 2 和 j = 3 时，grid[3][2] = 0，grid[3][3] = 0，不是陆地，跳过。

计算周长

• 最终 landSum = 7，cover = 6。

• 根据公式 landSum * 4 - cover * 2 计算周长：

  • 7 * 4 - 6 * 2 = 28 - 12 = 16。

运算

1356. 根据数字二进制下 1 的数目排序

力扣题目链接(opens new window)

题目链接：https://leetcode.cn/problems/sort-integers-by-the-number-of-1-bits/

给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。

如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。

请你返回排序后的数组。

示例 1：

• 输入：arr = [0,1,2,3,4,5,6,7,8]
• 输出：[0,1,2,4,8,3,5,6,7]
• 解释：[0] 是唯一一个有 0 个 1 的数。 [1,2,4,8] 都有 1 个 1 。 [3,5,6] 有 2 个 1 。 [7] 有 3 个 1 。按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]

示例 2：

• 输入：arr = [1024,512,256,128,64,32,16,8,4,2,1]
• 输出：[1,2,4,8,16,32,64,128,256,512,1024]
• 解释：数组中所有整数二进制下都只有 1 个 1 ，所以你需要按照数值大小将它们排序。

示例 3：

• 输入：arr = [10000,10000]
• 输出：[10000,10000]

示例 4：

• 输入：arr = [2,3,5,7,11,13,17,19]
• 输出：[2,3,5,17,7,11,13,19]

示例 5：

• 输入：arr = [10,100,1000,10000]
• 输出：[10,100,10000,1000]

思路

其实是考察如何计算一个数的二进制中1的数量。

• 方法一：

挨个计算1的数量，最多就是循环n的二进制位数，32位。

• 方法二

只循环n的二进制中1的个数次

以计算12的二进制1的数量为例，如图所示：

public class Sort_Integers_by_The_Number_of_1_Bits {private int cntInt(int val){//计算一个整数 val 的二进制表示中 1 的个数。使用 val & (val - 1) 操作可以将 val 的二进制表示中最右边的 1 变为 0。每次执行该操作后，1 的个数 count 加 1，直到 val 变为 0。int count = 0;while(val > 0) {val = val & (val - 1);count ++;}return count;}public int[] sortByBits(int[] arr) {//对输入的整数数组 arr 按照二进制中 1 的个数进行排序，如果二进制中 1 的个数相同，则按照整数本身的大小进行排序。return Arrays.stream(arr).boxed()//将数组转换为流并装箱：Arrays.stream(arr).boxed() 将 int 数组转换为 Integer 流，方便后续使用 Stream API 进行操作。.sorted(new Comparator<Integer>(){//自定义排序规则：使用 sorted 方法并传入一个自定义的 Comparator 对象。在 compare 方法中，分别调用 cntInt 方法计算 o1 和 o2 二进制中 1 的个数 cnt1 和 cnt2。如果 cnt1 等于 cnt2，则使用 Integer.compare(o1, o2) 按照整数本身的大小进行排序。否则，使用 Integer.compare(cnt1, cnt2) 按照二进制中 1 的个数进行排序。@Overridepublic int compare(Integer o1, Integer o2) {int cnt1 = cntInt(o1);int cnt2 = cntInt(o2);return (cnt1 == cnt2) ? Integer.compare(o1, o2) : Integer.compare(cnt1, cnt2);}}).mapToInt(Integer::intValue)//将流转换为 int 数组：mapToInt(Integer::intValue) 将 Integer 流转换为 int 流，toArray() 将 int 流转换为 int 数组并返回。.toArray();}
}

 时间复杂度 1. 计算每个整数的1的个数： cntInt(int val) 方法使用了一个循环来计算一个整数的二进制表示中1的个数。这个循环的复杂度是O(k)，其中k是val的二进制位数。对于32位整数，k的最大值为32，因此可以认为这个操作的复杂度是O(1)。 2. 排序：Arrays.stream(arr).sorted(...) 进行排序的复杂度是O(n log n)，其中n是数组的长度。 3. 总体时间复杂度：由于我们对每个元素都调用了 cntInt 方法，因此时间复杂度为O(n)（计算1的个数）加上O(n log n)（排序），所以总体时间复杂度为O(n log n)。

空间复杂度 1. 额外空间：在这个实现中，主要的额外空间使用是用于存储流的中间结果。 Arrays.stream(arr).boxed() 会创建一个新的Integer数组，空间复杂度为O(n)。 2. 总体空间复杂度：由于没有使用额外的数组来存储中间结果，除了输入数组和输出数组外，其他的空间使用是常数级的。因此，总体空间复杂度为O(n)。

时间复杂度: O(n log n)

空间复杂度: O(n)

arr = [0, 1, 2, 3]

1. 进入 sortByBits 方法

• Arrays.stream(arr).boxed()：将 int 数组 [0, 1, 2, 3] 转换为 Integer 流 [0, 1, 2, 3]。

2. 自定义排序规则

• 使用 sorted 方法并传入自定义的 Comparator 对象，对元素两两进行比较排序。
  • 比较 0 和 1：
    • 调用 cntInt(0)：
      • val = 0，不满足 val > 0 的条件，直接返回 count = 0。
    • 调用 cntInt(1)：
      • 初始 val = 1，val - 1 = 0，val & (val - 1) = 0，count = 1，循环结束，返回 count = 1。
    • 因为 cnt1 = 0，cnt2 = 1，cnt1 != cnt2，所以 compare 方法返回 Integer.compare(0, 1) = -1，表示 0 应该排在 1 前面。
  • 比较 0 和 2：
    • 调用 cntInt(0)，返回 0。
    • 调用 cntInt(2)：
      • 初始 val = 2（二进制 10），val - 1 = 1（二进制 01），val & (val - 1) = 0，count = 1，循环结束，返回 count = 1。
    • 因为 cnt1 = 0，cnt2 = 1，cnt1 != cnt2，所以 compare 方法返回 Integer.compare(0, 1) = -1，表示 0 应该排在 2 前面。
  • 比较 0 和 3：
    • 调用 cntInt(0)，返回 0。
    • 调用 cntInt(3)：
      • 初始 val = 3（二进制 11），val - 1 = 2（二进制 10），val & (val - 1) = 2（二进制 10），count = 1。
      • 此时 val = 2，val - 1 = 1（二进制 01），val & (val - 1) = 0，count = 2，循环结束，返回 count = 2。
    • 因为 cnt1 = 0，cnt2 = 2，cnt1 != cnt2，所以 compare 方法返回 Integer.compare(0, 2) = -1，表示 0 应该排在 3 前面。
  • 比较 1 和 2：
    • 调用 cntInt(1)，返回 1。
    • 调用 cntInt(2)，返回 1。
    • 因为 cnt1 = cnt2 = 1，所以 compare 方法返回 Integer.compare(1, 2) = -1，表示 1 应该排在 2 前面。
  • 比较 1 和 3：
    • 调用 cntInt(1)，返回 1。
    • 调用 cntInt(3)，返回 2。
    • 因为 cnt1 = 1，cnt2 = 2，cnt1 != cnt2，所以 compare 方法返回 Integer.compare(1, 2) = -1，表示 1 应该排在 3 前面。
  • 比较 2 和 3：
    • 调用 cntInt(2)，返回 1。
    • 调用 cntInt(3)，返回 2。
    • 因为 cnt1 = 1，cnt2 = 2，cnt1 != cnt2，所以 compare 方法返回 Integer.compare(1, 2) = -1，表示 2 应该排在 3 前面。

3. 转换为 int 数组

• mapToInt(Integer::intValue)：将 Integer 流转换为 int 流。
• toArray()：将 int 流转换为 int 数组，最终得到排序后的数组 [0, 1, 2, 3]。

输出结果

原数组: [0, 1, 2, 3]
排序后的数组: [0, 1, 2, 3]