数据结构和算法是编程路上永远无法避开的两个核心知识点，本系列【算法题】旨在记录刷题过程中的一些心得体会，将会挑出LeetCode等最具代表性的题目进行解析，题解基本都来自于LeetCode官网（https://leetcode-cn.com/），本文是第六篇。

1.颜色分类（原第75题）

给定一个包含红色、白色和蓝色，一共?n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、?1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。

示例:

输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]

（1）知识点

原地算法

（2）解题方法

方法转自：https://leetcode-cn.com/problems/sort-colors/solution/yan-se-fen-lei-by-leetcode/

方法：一次遍历

相比之前的题目经常用到的双指针法，这个其实是个三指针。事实上，一般遇到要排序的问题，无非就是多加几个指针就可以解决了。
我们用三个指针（p0, p2 和curr）来分别追踪0的最右边界，2的最左边界和当前考虑的元素。本解法的思路是沿着数组移动 curr 指针，若nums[curr] = 0，则将其与 nums[p0]互换；若 nums[curr] = 2 ，则与 nums[p2]互换。

• 时间复杂度：O(n)，由于对长度 N的数组进行了一次遍历。
• 空间复杂度：O(1)，不需要额外的空间开销。

（3）伪代码

函数头：void sortColors(int[] nums)

方法：一次遍历

• 定义p0=curr=0,p2=len-1
• 第一重循环：（curr<=p2）
  • 如果curr=0，交换p0和curr的值，p0++,curr++
  • 如果curr=1，curr++
  • 如果curr=2，交换p2和curr的值，p2--

（4）代码示例

2.子集（原第78题）

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
[3],
? [1],
? [2],
? [1,2,3],
? [1,3],
? [2,3],
? [1,2],
? []
]

（1）知识点

子集

（2）解题方法

方法转自：https://leetcode-cn.com/problems/subsets/solution/zi-ji-by-leetcode/

方法一：递归

根据题目可以判断，对于n个元素，每个元素都有放or不放两种状态，那么总共就有2^n种情况。
比如集合[1,2,3]：

不放，不放，不放：[]
放，不放，不放：[1]
不放，放，不放：[2]
不放，不放，放：[3]
放，放，不放：[1,2]
放，不放，放：[1,3]
不放，放，放：[2,3]
放，放，放：[1,2,3]

另外，我们考虑：

如果没有元素[]，他的子集是[]
如果有一个元素[1]，他的子集是[],[1]
如果有两个元素[1,2]，他的子集是[],[1],[2],[1,2]
如果有三个元素[1,2,3]，他的子集是[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]

发现什么了？每次增加一个元素，只需要在前一个的基础上的末尾添加一个元素就行了，所以总的子集数量是呈指数级别的增长的。这就容易想到递归算法了。

• 时间复杂度：O(N×2^N)，生成所有子集，并复制到输出结果中。
• 空间复杂度：O(N×2^N)，这是子集的数量。
• 对于给定的任意元素，它在子集中有两种情况，存在或者不存在（对应二进制中的 0 和 1）。因此，N 个数字共有 2^N个子集。

方法二：回溯法

我们知道，在遇到这种排列组合的情况下，基本上都能用到回溯法，而回溯法本身是一棵树，这里就需要每一层的情况都得加到最后的集合中去

• 时间复杂度：O(N×2^N)，生成所有子集，并复制到输出结果中。
• 空间复杂度：O(N×2^N)，存储所有子集，共 nn 个元素，每个元素都有可能存在或者不存在。

方法三：字典排序（二进制排序）

将每个子集映射到长度为 n 的位掩码中，其中第 i 位掩码 nums[i] 为 1，表示第 i 个元素在子集中；如果第 i 位掩码 nums[i] 为 0，表示第 i 个元素不在子集中。

例如，位掩码 0..00（全 0）表示空子集，位掩码 1..11（全 1）表示输入数组 nums。
因此要生成所有子集，只需要生成从 0..00 到 1..11 的所有 n 位掩码。

• 时间复杂度：O(N×2^N)，生成所有子集，并复制到输出结果中。
• 空间复杂度：O(N×2^N)，存储所有子集，共 nn 个元素，每个元素都有可能存在或者不存在。

（3）伪代码

函数头：List<List> subsets(int[] nums)

方法一：递归

• 定义List<List> res用作返回
• 将空集加入到res
• 第一重循环：（num:nums）
  • 定义List<List> sub用作添加当前num的集合
  • 将res里的每一个List都填上num然后放进sub里面（注意java有一个简单的写法（curr是res中的某个list）：sub.add(new ArrayList(curr){{add(num);}});）
  • 将sub里面的每个list再加到res中

方法二：回溯

• 定义一个回溯方法 backtrack(first, curr)，第一个参数为索引 first，第二个参数为当前子集 curr。
• 如果当前子集构造完成，将它添加到输出集合中。
• 否则，第一重循环从i: first->n-1
  • 将整数 nums[i] 添加到当前子集 curr。
  • 继续向子集中添加整数：backtrack(i + 1, curr)。
  • 从 curr 中删除 nums[i] 进行回溯。

方法三：字典排序（二进制排序）

• 生成所有长度为 n 的二进制位掩码。
• 将每个子集都映射到一个位掩码数：位掩码中第 i 位如果是 1 表示子集中存在 nums[i]，0 表示子集中不存在 nums[i]。

（4）代码示例

3.单词搜索（原第79题）

给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
[‘A‘,‘B‘,‘C‘,‘E‘],
[‘S‘,‘F‘,‘C‘,‘S‘],
[‘A‘,‘D‘,‘E‘,‘E‘]
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

（1）知识点

回溯法

（2）解题方法

方法转自：https://leetcode-cn.com/problems/word-search/solution/zai-er-wei-ping-mian-shang-shi-yong-hui-su-fa-pyth/

方法：回溯法

这个题同样考虑回溯法，因为每跑到一个点就会遇到几种不同的情况，比如下图中的‘C‘，到这里就有两个路可以走，如果“走错了”，就需要回来换一条路，这里就用到了回溯算法。

我们考虑从第一个点开始遍历，直到找到待查的第一个字母，然后上下左右（可以自定义顺序）来找到下一个，如果不对就回溯。并且在行进的过程中，需要标记已经走过的点，因为不能重复。

（3）伪代码

函数头：boolean exist(char[][] board, String word)

方法：回溯法

• 两重循环遍历board中的每个元素，调用backtrack函数，判断以该字符开头满不满足情况。

boolean backtrack(int i, int j, int start)：start是word中的某个字符

• 如果start是word的最后一个字符，直接判断是否和board[i][j]相等返回。——递归终止条件
• 如果start位置的字符和board[i][j]相等，进一步判断：
  • 标记i,j位置已经走过（这里需要一个全局变量数组来记录）
  • 第一重循环（k:0->3）：这里是分别走i,j位置的上下左右四个方向（这里也需要定义一个全局变量数组来记录偏移量，具体就是int[][]direct={{0,1},{0,-1},{1,0},{-1,0}}）
    • 定义newX=i+direct[k][0]，newY=j+direct[k][1]
    • 如果newX和newY均未走过，并且newX和newY都在board的范围里面（需要提前定义好全局变量board的范围，所有direct的四个方向不一定都能走到），调用backtrack(newX,newY,start+1)
  • 回溯（标记i,j未走过）
• 返回false

（4）代码示例

4.子集2（原第90题）

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

（1）知识点

回溯法

（2）解题方法

方法转自：https://leetcode-cn.com/problems/subsets-ii/solution/shi-yong-mapji-shu-yi-bian-sao-miao-jia-ru-suo-you/

方法：回溯法

这个题和子集那题不同，如果依旧按照那个方法的话会得出很多重复的结果。我们以[1,2,2]为例，利用回溯法，并且对每种情况进行判断。要实现同层比较的关键就是比较for循环里的j和回溯函数的实参i,j是当前检查元素下标；i是本层开始检查的元素下标
如果nums[j]是在同层的在for循环里重复出现的，那么j肯定大于i，否则比较的两个元素就处于不同层。实际上就是判断j是否大于i，然后还需要nums[j]!=[j-1]
下图中第一层第三个说明有点错误。（应该是nums[2]==nums[1]）

（3）伪代码

函数头： List<List> subsetsWithDup(int[] nums)

方法：回溯法

• 需要定义两个全局变量数组（一个二维数组用于返回最后的结果res，一个一位数组用来装临时的子集tmp）
• 先对nums排序
• 调用backtrack(0)

void backtrack(int i)

• 如果i=len，直接返回——递归终止条件
• 第一重循环（j:i->len-1）：
  • 如果j>i且nums[j]==nums[j-1]跳过
  • tmp添加nums[j]
  • res添加一个新List（拷贝tmp）
  • backtrack(i+1)
  • tmp.remove(最后一个元素）——回溯

（4）代码示例

【算法题】LeetCode刷题（六）

原文：https://www.cnblogs.com/echizen/p/13450612.html