算法模块

总结下算法题总的常见模版,包括回溯模版,广度和深度搜索,动态规划的模版等。以LeetCode的一些例题为例。

回溯模块

LeetCode上几个经典的回溯例题,包括子集,全排列,组合总和。可以看出不同的剪枝方式,和输出结果的时机。

78.子集

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
[3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

start的设置在剪枝上的作用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> track;
backtrack(track, nums, 0);
return ans;
}
void backtrack(vector<int>& track, vector<int>& nums, int start){
ans.push_back(track);
for(int i = start; i < nums.size(); i++){
track.push_back(nums[i]);
backtrack(track, nums, i+1);
track.pop_back();
}
}
};

90.子集2

给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

这边出现了重复元素的情况,第一步是sort之后把重复元素排列在一起,nums[i] == nums[i-1]这个条件挺好理解的,关键是!used[i-1],为什么记录nums中元素使用情况的used为false的时候,下一个同样值的元素不能push进track,是因为每次回溯回退的时候track.pop_back(); used[i] = false;。举个例子,对于[1,2,2]来说,track状态为[1]时候,第一个2进入,输出了[1,2]之后,经过pop,此时 第一个2的used状态修改成false,并且此时track又回溯成[1]。这时候for循环到了第二个2,如果我们再输出一个[1,2]显然就重复输出了。对于这个例子,used[i-1]为 true的情况是,我们需要输出[1,2,2]的时候,这时候我们允许第二个2进入track。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<int> track;
sort(nums.begin(), nums.end());
vector<bool> used(nums.size(), false);
backtrack(nums, track, used, 0);
return ans;

}
void backtrack(vector<int>& nums, vector<int>& track, vector<bool>& used, int start){
ans.push_back(track);
for (int i = start; i < nums.size(); i++){
if (used[i] || (i>start && nums[i] == nums[i-1]&& !used[i-1])){
continue;
}
track.push_back(nums[i]);
used[i] = true;
backtrack(nums, track, used, i+1);
track.pop_back();
used[i] = false;
}
}
};

46.全排列

给定一个 没有重复 数字的序列,返回其所有可能的全排列。
示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def permute(self, s: List[int]) -> List[List[int]]:
ans = []
def backtrack(track):
if len(track) == len(s):
ans.append(track[:])
return
for i in range(len(s)):
if s[i] not in track:
track.append(s[i])
# print("append:{0}".format(track))
backtrack(track)
track.pop()
# print("pop:{0}".format(track))

backtrack([])
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> permute(vector<int>& nums) {
vector<int> track;
backtrack(nums, track);
return ans;
}
void backtrack(vector<int>& nums, vector<int>& track){
if (track.size() == nums.size()){
ans.push_back(track);
}
for (int i = 0; i < nums.size(); i++){
if (find(track.begin(), track.end(), nums[i]) != track.end())
continue;
track.push_back(nums[i]);
backtrack(nums, track);
track.pop_back();
}

}
};

47.全排列2

给定一个可包含重复数字的序列,返回所有不重复的全排列。
示例:

1
2
3
4
5
6
7
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

关键区别在于有重复元素

这边先进行排序,使得重复元素在一起

sort(nums.begin(), nums.end());

对于相邻的两个相同元素, 互换两者位置会产生一样的结果。 我们按照回溯顺序的先后,对于用后一个元素,但是前面的一个元素没有用的重复情况进行排除。

used[i] || (i>0 && nums[i] == nums[i-1] && !used[i-1])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<int> track;
vector<bool> helper(nums.size(), false);
sort(nums.begin(), nums.end());
backtrack(nums, track, helper);
return ans;
}

void backtrack(vector<int>& nums, vector<int>& track, vector<bool> used){
if (track.size() == nums.size()){
ans.push_back(track);
return;
}
for (int i = 0; i < nums.size(); i++){
if (used[i] || (i>0 && nums[i] == nums[i-1] && !used[i-1])){
continue;
}
track.push_back(nums[i]);
used[i] = true;
backtrack(nums, track, used);
track.pop_back();
used[i] = false;
}
}
};

类似的

输入一个字符串,打印出该字符串中字符的所有排列。这边的方法基本和上面一致。区别在于这边用了set()去判断这个位置是否有重复字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
def permutation(self, s):
"""
:type s: str
:rtype: List[str]
"""
res = []
used = [False] * len(s)
def dfs(track, used):
if len(track) == len(s):
res.append(''.join(track))
return
dic = set()
for i in range(len(s)):
if s[i] in dic or used[i]: continue
dic.add(s[i])
track.append(s[i])
used[i] = True
dfs(track, used)
track.pop()
used[i] = False
dfs([], used)
return res

取消掉used和track的额外开销,直接原地交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
def permutation(self, s: str) -> List[str]:
c, res = list(s), []
def dfs(x):
if x == len(c) - 1:
res.append(''.join(c)) # 添加排列方案
return
dic = set()
for i in range(x, len(c)):
if c[i] in dic: continue # 重复,因此剪枝
dic.add(c[i])
c[i], c[x] = c[x], c[i] # 交换,将 c[i] 固定在第 x 位
dfs(x + 1) # 开启固定第 x + 1 位字符
c[i], c[x] = c[x], c[i] # 恢复交换
dfs(0)
return res

39.组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

所有数字(包括 target)都是正整数。
解集不能包含重复的组合。
示例 1:

1
2
3
4
5
6
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]

示例 2:

1
2
3
4
5
6
7
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> track;
//sort(candidates.begin(), candidates.end());
backtrack(candidates, track, target, 0);
return ans;
}
void backtrack(vector<int>& candidates, vector<int>& track, int target, int start){
if (target == 0 ){
ans.push_back(track);
return;
}
if (target < 0) return;
for(int i = start; i < candidates.size(); i++){
if (candidates[i] > target) continue;
track.push_back(candidates[i]);
backtrack(candidates, track, target-candidates[i], i);
track.pop_back();
}
}
};

40.组合总和2

给定一个有重复元素的数组 candidates

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> track;
sort(candidates.begin(), candidates.end());
//vector<bool> used(track.size(), false);
backtrack(candidates, track, target, 0);
return ans;
}
void backtrack(vector<int>& candidates, vector<int>& track, int target, int start){
if (target == 0 ){
ans.push_back(track);
return;
}
if (target < 0) return;
for(int i = start; i < candidates.size(); i++){
if (candidates[i] > target || ( i>start && candidates[i] == candidates[i-1]) ) continue;
track.push_back(candidates[i]);
backtrack(candidates, track, target-candidates[i], i+1);
track.pop_back();
}
}
};

DFS和BFS

785.判断二分图

给定一个无向图graph,当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集A和B,并使图中的每一条边的两个节点一个来自A集合,一个来自B集合,我们就将这个图称为二分图。

graph将会以邻接表方式给出,graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边: graph[i] 中不存在i,并且graph[i]中没有重复的值。

1
2
3
4
5
6
7
8
9
10
11

示例 1:
输入: [[1,3], [0,2], [1,3], [0,2]]
输出: true
解释:
无向图如下:
0----1
| |
| |
3----2
我们可以将节点分成两组: {0, 2} 和 {1, 3}。
1
2
3
4
5
6
7
8
9
10
示例 2:
输入: [[1,2,3], [0,2], [0,1,3], [0,2]]
输出: false
解释:
无向图如下:
0----1
| \ |
| \ |
3----2
我们不能将节点分割成两个独立的子集。
  • graph 的长度范围为 [1, 100]。
  • graph[i] 中的元素的范围为 [0, graph.length - 1]。
  • graph[i] 不会包含 i 或者有重复的值。
  • 图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。

图的遍历与染色问题。这边开一个colors数组,用0代表没有染色,1和-1表示相反的两种颜色。

DFS

递归实现的DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
bool DFS(int cur, vector<int> & colors, vector<vector<int>>& graph){
for (auto next : graph[cur]) {
if (colors[next] == 0){
colors[next] = -colors[cur];
if(!DFS(next, colors, graph)) return false;
}
if (colors[next] == colors[cur]) return false;
}
return true;
}
bool isBipartite(vector<vector<int>>& graph) {
int nodes_num = graph.size();
vector<int> colors(nodes_num, 0);
for(int i = 0; i < nodes_num; i++){
if(colors[i] == 0){colors[i] = 1;}
if(!DFS(i, colors, graph)){
return false;
}
}
return true;
}
};

BFS

利用队列实现BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
bool isBipartite(vector<vector<int>>& graph) {
int nodes_num = graph.size();
queue<int> temp;
vector<int> colors(nodes_num, 0);
for (int i = 0; i < graph.size(); i++) {
if (colors[i] != 0) continue;
temp.push(i);
colors[i] = 1;
while (!temp.empty()){
int cur = temp.front();
temp.pop();
for(auto next : graph[cur]){
if(colors[next] == 0){
colors[next] = -colors[cur];
temp.push(next);
}
if(colors[next] == colors[cur]) return false;
}
}
}
return true;
}
};

133.克隆图

给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。

图中的每个节点都包含它的值 val(int) 和其邻居的列表(list[Node])。

class Node {
public int val;
public List neighbors;
}

首先是对无向图进行拷贝,所以需要一个hashmap来记录已经访问过的点。

对于图的问题,BFS和DFS

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
from collections import deque
lookup = {}

def bfs(node):
if not node: return
clone = Node(node.val, [])
lookup[node] = clone
queue = deque()
queue.appendleft(node)
while queue:
tmp = queue.pop()
for n in tmp.neighbors:
if n not in lookup:
lookup[n] = Node(n.val, [])
queue.appendleft(n)
lookup[tmp].neighbors.append(lookup[n])
return clone

return bfs(node)

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
lookup = {}

def dfs(node):
#print(node.val)
if not node: return
if node in lookup:
return lookup[node]
clone = Node(node.val, [])
lookup[node] = clone
for n in node.neighbors:
clone.neighbors.append(dfs(n))

return clone

return dfs(node)

动态规划DP

明确 base case -> 明确「状态」(从头到尾还是从尾到头)-> 明确「选择」 -> 定义 dp 数组/函数的含义。

https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/dong-tai-gui-hua-xiang-jie-jin-jie

高楼扔鸡蛋

你面前有一栋从 1 到N共N层的楼,然后给你K个鸡蛋(K至少为 1)。现在确定这栋楼存在楼层0 <= F <= N,在这层楼将鸡蛋扔下去,鸡蛋恰好没摔碎(高于F的楼层都会碎,低于F的楼层都不会碎)。现在问你,最坏情况下,你至少要扔几次鸡蛋,才能确定这个楼层F呢?

PS:F 可以为 0,比如说鸡蛋在 1 层都能摔碎,那么 F = 0。

题目解析

进阶分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def superEggDrop(K: int, N: int):

memo = dict()
def dp(K, N) -> int:
# base case
if K == 1: return N
if N == 0: return 0
# 避免重复计算
if (K, N) in memo:
return memo[(K, N)]

res = float('INF')
# 穷举所有可能的选择
for i in range(1, N + 1):
res = min(res,
max(
dp(K, N - i),
dp(K - 1, i - 1)
) + 1
)
# 记入备忘录
memo[(K, N)] = res
return res

return dp(K, N)

爬楼梯

在做LeetCode时候做到一道不算难的题目,第70道Climbing Stairs。题目描述如下:
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

1
2
3
4
5
6
7
Input: 3
Output: 3
Explanation: There are three ways to climb to the top.

1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

解决方法

其实明眼人一眼就能看见,这不是正是斐波那契数列的求逆过程嘛。对的,确实如此,所以解决这个问题的方法可以用动态规划解决,但是由于是逆过程,又会使人很想用递归法求解,下面是一开始写的代码。

传统递归法

1
2
3
4
5
6
7
8
int climbStairs(int n)
{
if(n==0) return 0;
if(n==1) return 1;
if(n==2) return 2;
else
return (climbStairs(n-1)+climbStairs(n-2));
}

上面这个代码确实很简洁,思路也很简单,问题就是在LeetCode上提交后会超时。
所以稍微考虑了一下想到了这题和斐波那契数列的关系,改用了动态规划缩短一下时间。

动态规划

1
2
3
4
5
6
7
8
9
10
11
int climbStairs(int n) 
{
vector<int> steps(n,0);
steps[0]=1;
steps[1]=2;
for(int i=2;i<n;i++)
{
steps[i]=steps[i-2]+steps[i-1];
}
return steps[n-1];
}

后面在LeetCode的讨论里面看到了一个人也是用递归法,想问怎么才能解决超时,下面是一个回答者的解法,很有意思,能看到动态规划本身就是为了解决多余次数的递归的设计意义。

改进版的递归法(实际上也是动态规划)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
unordered_map<int,int> cache;
int climbStairs(int n) {
if(cache.find(n)!=cache.end()) return cache[n];
int result = 0;
if (n == 0) result = 0;
else if (n == 1) result= 1;
else if (n == 2) result = 2;
else result = climbStairs(n-1) + climbStairs(n-2);

cache[n]=result;
return result;
}
};

答主的原话:Because you were doing recursion without memorization, then you end up recalculating lots of stuff . e.g: when calculating f(44)=f(43)+f(42), you first calculate f(43) , then you calculate f(42), while f(42) is already available when calculating f(43). So… use a cache to store all your intermediate results and return the result immediately if it’s already calculated .
所以其实也就是另外开辟空间对之前的结果作出记录,就是动态规划。

当然对于这题还有一种更节省空间复杂度的解法,也特别棒:

动态规划法的精简法

1
2
3
4
5
6
int climbStairs(int n) {
int a = 1, b = 1;
while (n--)
a = (b += a) - a;
return a;
}

对于解法的解释引用一下LeetCode里的原话——Variable a tells you the number of ways to reach the current step, and b tells you the number of ways to reach the next step. So for the situation one step further up, the old b becomes the new a, and the new b is the old a+b, since that new step can be reached by climbing 1 step from what b represented or 2 steps from what a represented.
其实这里就是因为用动态规划解决这个问题的时候只需要用到前两步的数据记录。再之前的记录会随着计算推进由于不再需要而被丢弃。

利用矩阵乘法解Fibonacci

主要是利用

左半部分矩阵形式我们暂且称为Q,那么所要求的第n个Fibonacci数为 $Q^{n-1}$ 所得矩阵的第一列第一行对应的值。

具体的证明可与参考LeetCode上这道题的solution(主要LaTeX用起来不方便,要写好多公式)
给出对应的Java代码:
(c++里面也有pow函数用来求a的b次方,但是像这里边的multiply()支持对二维数组直接计算还真不能。Java里的Math类功能确实强。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
public int climbStairs(int n) {
int[][] q = {{1, 1}, {1, 0}};
int[][] res = pow(q, n);
return res[0][0];
}
public int[][] pow(int[][] a, int n) {
int[][] ret = {{1, 0}, {0, 1}};
while (n > 0) {
if ((n & 1) == 1) {
ret = multiply(ret, a);
}
n >>= 1;
a = multiply(a, a);
}
return ret;
}
public int[][] multiply(int[][] a, int[][] b) {
int[][] c = new int[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
}
}
return c;
}

利用Fibonacci公式

$F_n=1/{\sqrt{5}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^{n}]}$

java解法:

1
2
3
4
5
6
7
public class Solution {
public int climbStairs(int n) {
double sqrt5=Math.sqrt(5);
double fibn=Math.pow((1+sqrt5)/2,n+1)-Math.pow((1-sqrt5)/2,n+1);
return (int)(fibn/sqrt5);
}
}