DFS与回溯

回溯其实属于DFS的一种特殊场景。

1,岛屿的最大面积

给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿,则返回面积为0。)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
对于上面这个给定矩阵应返回 6。注意答案不应该是11,因为岛屿只能包含水平或垂直的四个方向的‘1’。
示例 2:
[[0,0,0,0,0,0,0,0]]
对于上面这个给定的矩阵, 返回 0。
注意: 给定的矩阵grid 的长度和宽度都不超过 50
来源: https://leetcode-cn.com/problems/max-area-of-island/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int dfs(vector<vector<int>>& grid, int i, int j)
{
if(i<0||i>=grid.size()||j<0||j>=grid[0].size())
return 0;
if(!grid[i][j])
return 0;
grid[i][j] = 0;
return 1+dfs(grid,i,j+1)+dfs(grid,i,j-1)+dfs(grid,i-1,j)+dfs(grid,i+1,j);
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
/**
深度遍历dfs
*/
if(grid.size()==0) return 0;
int result =0;
for(int i =0;i<grid.size();i++)
for(int j=0;j<grid[0].size();j++)
if(grid[i][j])
result=max(result,dfs(grid,i,j));
return result;
}

2,岛屿数目

这题与上一题不同,这个是求岛屿的个数,而不是最大的岛屿面积
11110
11010
11000
00000
Answer: 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
void dfs(vector<vector<char>>& grid, int i, int j)
{
if(i<0||i>=grid.size()||j<0||j>=grid[0].size())
return ;
if(grid[i][j]=='0')
return ;
grid[i][j] = '0';
dfs(grid,i,j+1);
dfs(grid,i,j-1);
dfs(grid,i+1,j);
dfs(grid,i-1,j);
}
int numIslands(vector<vector<char>>& grid) {
/**
与求最大的岛屿面积不同,不用做max比较,这个是直接计算岛屿数目
*/
if(grid.empty()) return 0;
int result =0;
for(int i =0;i<grid.size();i++)
for(int j=0;j<grid[0].size();j++)
if(grid[i][j]=='1')
{
dfs(grid, i , j);
++result;
}
return result;
}

3,朋友圈

班上有 N 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友,B 是 C 的朋友,那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈,是指所有朋友的集合。
给定一个 N * N 的矩阵 M,表示班级中学生之间的朋友关系。如果M[i][j] = 1,表示已知第 i 个和 j 个学生互为朋友关系,否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
示例 1:
输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明:已知学生0和学生1互为朋友,他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。
示例 2:
输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明:已知学生0和学生1互为朋友,学生1和学生2互为朋友,所以学生0和学生2也是朋友,所以他们三个在一个朋友圈,返回1。
注意:
N 在[1,200]的范围内。
对于所有学生,有M[i][i] = 1。
如果有M[i][j] = 1,则有M[j][i] = 1。
来源: https://leetcode-cn.com/problems/friend-circles/description/

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
29
30
void dfs(vector<vector<int>>& M, int k, vector<int>& flag)
{
if(k<0||k>=M.size())
return;
if(flag[k])
return;
flag[k]=1;
for(int i=0;i<M.size();i++)
if(!flag[i]&&M[k][i])
{
dfs(M,i,flag);//这里其实不需要上下左右,把当前的处理好就行
}
}
int findCircleNum(vector<vector<int>>& M) {
/**
这种互为关系的情况,应该是降为一维的;
与求岛屿数目类似
同时增加相应的标记位
*/
if(M.empty()) return 0;
int result =0;
vector<int> flag(M.size(), 0);
for(int i= 0;i<M.size();i++)
if(!flag[i])
{
dfs(M,i,flag);
result++;
}
return result;
}

4,填充封闭区域

给定一个二维的矩阵,包含 ‘X’ 和 ‘O’(字母 O)。
找到所有被 ‘X’ 围绕的区域,并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
示例:
X X X X
X O O X
X X O X
X O X X
运行你的函数后,矩阵变为:
X X X X
X X X X
X X X X
X O X X
解释:
被围绕的区间不会存在于边界上,换句话说,任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上,或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。
来源: https://leetcode-cn.com/problems/surrounded-regions/description/

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
29
30
31
32
33
34
void dfs(vector<vector<char>>& board,int i,int j)
{
if(i<0||i>=board.size()||j<0||j>=board[0].size()||board[i][j]!='O')
return;
board[i][j] ='H';
dfs(board,i+1,j);
dfs(board,i-1,j);
dfs(board,i,j+1);
dfs(board,i,j-1);
}
void solve(vector<vector<char>>& board) {
/**
找到与边缘相联通的区域,作为标记,剩下的非与边缘相连的O最后转为X
*/
if(board.empty()) return;
for(int i=0;i<board.size();i++)
{
dfs(board,i,0);
dfs(board,i,board[0].size()-1);
}
for(int j=0;j<board[0].size();j++)
{
dfs(board,0,j);
dfs(board,board.size()-1, j);
}
for(int i=0;i<board.size();i++)
for(int j=0;j<board[0].size();j++)
{
if(board[i][j]=='O')
board[i][j]='X';
else if(board[i][j]=='H')
board[i][j]='O';
}
}

5,太平洋和大西洋的水

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.
Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.
Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.
Note:
The order of returned grid coordinates does not matter.
Both m and n are less than 150.
Example:
Given the following 5x5 matrix:
Pacific ~ ~ ~ ~ ~
~ 1 2 2 3 (5)
~ 3 2 3 (4) (4)

~ 2 4 (5) 3 1
~ (6) (7) 1 4 5

~ (5) 1 1 2 4 *

*   *   *   *   * Atlantic

Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

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
29
30
31
32
33
34
35
36
37
38
39
40
void dfs(vector<vector<int>>& matrix,int i ,int j, vector<vector<int>>& flag)
{
if(i<0||i>=matrix.size()||j<0||j>=matrix[0].size()||flag[i][j])
return;
flag[i][j]=1;
if(i+1<matrix.size()&&matrix[i][j]<=matrix[i+1][j])
dfs(matrix,i+1,j,flag);
if(i-1>=0&&matrix[i][j]<=matrix[i-1][j])
dfs(matrix,i-1,j,flag);
if(j-1>=0&&matrix[i][j]<=matrix[i][j-1])
dfs(matrix,i,j-1,flag);
if(j+1<matrix[0].size()&&matrix[i][j]<=matrix[i][j+1])
dfs(matrix,i,j+1,flag);
}
vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
/**
要能流水,则从外到里是增加的
能流到外面,则从外面开始找连通到里面的区域,且是递增
两者都能流,则取交集
*/
vector<pair<int, int>> result;
if(matrix.empty()) return result;
vector<vector<int>> pflag(matrix.size(),vector<int>(matrix[0].size(),0));
vector<vector<int>> aflag(matrix.size(),vector<int>(matrix[0].size(),0));
for(int i=0;i<matrix.size();i++)
{
dfs(matrix,i,0,pflag);
dfs(matrix,i,matrix[0].size()-1,aflag);
}
for(int j=0;j<matrix[0].size();j++)
{
dfs(matrix,0,j,pflag);
dfs(matrix,matrix.size()-1,j,aflag);
}
for(int i=0;i<matrix.size();i++)
for(int j=0;j<matrix[0].size();j++)
if(pflag[i][j]&&aflag[i][j])
result.push_back(make_pair(i,j));
return result;
}

关于回溯,是dfs的一种,不同的是在dfs的时候发现不满足条件会回退遍历

6,电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例:
输入:”23”
输出:[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
说明:
尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。

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
//0 1不对应数字
vector<string> letters={" "," ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
void dfs(vector<string>& result, string digits, string temp, int curr)
{
if(curr == digits.size())
{
result.push_back(temp);
return;
}
for(int i=0;i<letters[digits[curr]-'0'].size();i++)
{
temp.push_back(letters[digits[curr]-'0'][i]);
dfs(result, digits, temp, curr+1);
temp.pop_back();
}
}
vector<string> letterCombinations(string digits) {
/**
根据数字映射遍历
*/
vector<string> result;
if(digits.empty())
return result;
string temp;
dfs(result,digits,temp,0);
return result;
}

###
ip地址空着

##

7,单词搜索

给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]
给定 word = “ABCCED”, 返回 true.
给定 word = “SEE”, 返回 true.
给定 word = “ABCB”, 返回 false.
来源: https://leetcode-cn.com/problems/word-search/description/

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
bool dfs(vector<vector<char>>& board, string word,vector<vector<int>>& flag, int i, int j, int curr)
{
if(curr == word.size())
return true;
if(i<0||i>=board.size()||j<0||j>=board[0].size()||flag[i][j]==1||board[i][j]!=word[curr])
return false;
flag[i][j] =1;
if(dfs(board,word,flag,i+1,j,curr+1)||
dfs(board,word,flag,i-1,j,curr+1)||
dfs(board,word,flag,i,j+1,curr+1)||
dfs(board,word,flag,i,j-1,curr+1))
return true;
flag[i][j] =0;
return false;
}
bool exist(vector<vector<char>>& board, string word) {
/**
典型的回溯,访问路径需要标记
*/
if(board.empty()) return false;
if(word.empty()) return true;
vector<vector<int>> flag(board.size(), vector<int>(board[0].size(), 0));
for(int i=0;i<board.size();i++)
for(int j=0;j<board[0].size();j++)
if(dfs(board, word,flag, i,j,0))
return true;
return false;
}

8,二叉树的所有路径

这种求所有路径的问题,通过dfs加回溯可以遍历到所有的路径
给定一个二叉树,返回从根节点到叶节点的所有路径。
例如,给定以下二叉树:
1
/ \
2 3
\
5
所有根到叶路径是:

[“1->2->5”, “1->3”]

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
void dfs(TreeNode* root,vector<string>& result, string path)
{
if(root==NULL)
return;
if(root->left==NULL&&root->right==NULL)
{
path+=to_string(root->val); //这里关于字符串拼接的时候遇到一些以前Java没有遇到的问题
result.push_back(path);
return;
}
path+=to_string(root->val);
path+="->";
dfs(root->left,result,path);
dfs(root->right,result,path);
path.pop_back();
}
vector<string> binaryTreePaths(TreeNode* root) {
/**
dfs加回溯可以深度遍历到所有的路径
*/
vector<string> result;
if(root==NULL)
return result;
string path;
dfs(root,result,path);
return result;
}

9,全排列

排列和组合一直都是dfs回溯的经典类型
本题是一个没有重复数字的简单版本,这里用swap版本的和一般的不用swap的回溯实现

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
    /**
void swap(int &a, int &b)
{
int temp =a;
a = b;
b= temp;
}
void dfs(vector<vector<int>>& result, vector<int> nums,int curr)
{
if(curr ==nums.size())
{
result.push_back(nums);
return;
}
for(int i= curr;i<nums.size();i++){
swap(nums[i], nums[curr]);
dfs(result,nums,curr+1);
swap(nums[i], nums[curr]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
/**
排列组合一直是dfs回溯的经典题型
题目说了是没有重复的数字进行全排列,所以这是一个不需要去重复的版本
*//*
vector<vector<int>> result;
if(nums.empty())
return result;
dfs(result,nums,0);
return result;
}
*/
void dfs(vector<vector<int>>& result, vector<int> nums,vector<int> temp,vector<int>& flag)
{
if(temp.size() ==nums.size())
{
result.push_back(temp);
return;
}
for(int i= 0;i<nums.size();i++)
{
if(flag[i])
continue;
flag[i] =1;
temp.push_back(nums[i]);
dfs(result,nums,temp,flag);
temp.pop_back();
flag[i]=0;
}
}
vector<vector<int>> permute(vector<int>& nums) {
/**
排列组合一直是dfs回溯的经典题型
*/
vector<vector<int>> result;
if(nums.empty())
return result;
vector<int> temp;
vector<int> flag(nums.size(),0);//不swap的时候需要标记位
dfs(result,nums,temp,flag);
return result;
}

10,全排列||

给定一个可包含重复数字的序列,返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
这题与上面不同之处在于原始数据可能有重复的数字
这题遇到一些小坑:
1,关于要不要引号的问题,如果是没有重复数字,加不加引号测试都没影响,
但是有重复数字的时候:
>如果是swap方法,则一定不能用第二次swap且不能要引号,且一定要排序;
>一般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
25
26
27
28
29
30
31
32
33
 /*
void swaps(int& a, int& b)//std中有swap函数
{
int temp =a;
a=b;
b=temp;
}
//
void swapdfs(vector<int> nums, vector<vector<int>>& result, int curr)//nums不要加&,这里卡了好久
{
if(curr >= nums.size())
{
result.push_back(nums);
return;
}
for(int i=curr;i<nums.size();i++)
{
if(i>curr&&nums[i]==nums[curr])
continue;
swaps(nums[i],nums[curr]);
swapdfs(nums,result,curr+1);
//swaps(nums[i],nums[curr]); 一定不能要第二次swap
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> result;
if(nums.empty())
return result;
sort(nums.begin(),nums.end());//排序不可少
swapdfs(nums,result,0);
return result;
}
*/

再看看非swap方式的

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
29
30
void swapdfs1(vector<int> nums, vector<vector<int>>& result,vector<int>& flag,vector<int> temp)
{
if(temp.size() >= nums.size())
{
result.push_back(temp);
return;
}
for(int i=0;i<nums.size();i++)
{
if(i>0&&nums[i]==nums[i-1]&&!flag[i-1])
continue;
if(flag[i])
continue;
flag[i] =1;
temp.push_back(nums[i]);
swapdfs1(nums,result,flag,temp);
temp.pop_back();
flag[i] =0;
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> result;
if(nums.empty())
return result;
sort(nums.begin(),nums.end());//排序不可少
vector<int> flag(nums.size(),0);
vector<int> temp;
swapdfs1(nums,result,flag,temp);
return result;
}

11,组合

给定两个整数 n 和 k,返回 1 … n 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
这题是简答的组合,不需要组合

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
void dfs(vector<vector<int>>& result, vector<int> temp,int curr, int n ,int k)
{
if(k==0)
{
result.push_back(temp);
return;
}
for(int i=curr;i<=n;i++)
{
temp.push_back(i);
dfs(result,temp,i+1,n,k-1);
temp.pop_back();
}
}
vector<vector<int>> combine(int n, int k) {
/**
组合的话,也是和排列一样用经典的dfs,不需要用swap之类的
*/
vector<vector<int>> result;
if(n<=0||k<=0)
return result;
vector<int> temp;
dfs(result,temp,1,n,k);
return result;
}

12,组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取
说明:
所有数字(包括 target)都是正整数。
解集不能包含重复的组合。
示例 1:
given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[[7],[2, 2, 3]]
given candidate set [2, 3, 5] and target 8,
A solution set is:
[[2,2,2,2],[2, 3, 3],[3,5]]
这里是组合内可由重复数字,因此下次dfs是从i开始不是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
29
30
void dfs(vector<int> candidates, vector<vector<int>>& result,vector<int> temp, int target, int curr)
{
if(target==0)
{
result.push_back(temp);
return;
}
if(curr>=candidates.size())
return;
for(int i=curr;i<candidates.size();i++)
{
if(target>=candidates[i])//记得判断这个,不然下面的i会死循环
{
temp.push_back(candidates[i]);
dfs(candidates,result,temp,target-candidates[i],i);
temp.pop_back();
}
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
/**
dfs回溯
*/
vector<vector<int>> result;
if(candidates.empty())
return result;
vector<int> temp;
dfs(candidates,result,temp,target,0);
return result;
}

13,组合总和||

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明:
所有数字(包括目标数)都是正整数。
解集不能包含重复的组合。
示例 1:
given candidate set [10,1,2,7,6,1,5] and target 8,
A solution set is:
[[1,7],[1, 2, 5],[2,6],[1,1,6]]

given candidate set [2,5, 2, 1,2] and target 7,
A solution set is:
[[7],[2, 2, 3]]

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
29
30
void dfs(vector<int>& candidates, vector<vector<int>>& result, vector<int> temp,int curr, int target)
{
if(target==0)
{
result.push_back(temp);
return;
}
for(int i=curr;i<candidates.size();i++)
{
if(target>=candidates[i])
{
temp.push_back(candidates[i]);
dfs(candidates,result,temp,i+1,target-candidates[i]);
temp.pop_back();
while(i+1<candidates.size()&&candidates[i]==candidates[i+1]) i++;//做递归的重复,这里用来消除重复,当然前面是得排完序的
}
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
/**
这题与组合I不同的在于这里的数字不能重复,建议可以排序下
*/
vector<vector<int>> result;
if(candidates.empty())
return result;
sort(candidates.begin(), candidates.end());
vector<int> temp;
dfs(candidates,result,temp,0,target);
return result;
}

14,组合总和III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有1 - 9的正整数,并且每种组合中不存在重复的数字。
说明:
所有数字都是正整数。
解集不能包含重复的组合。
示例 1:
输入: k=3, n=7
输出:[[1,2,4]]
输入: k=3, n=9
输出:[[1,2,6],[1,3,5],[2,3,4]]

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
void dfs(vector<vector<int>>& result, vector<int> temp, int k,int n,int curr)
{
if(k==temp.size()&&n==0)
{
result.push_back(temp);
return;
}
if(n<0)
return;
for(int i=curr;i<=9;i++)
{
temp.push_back(i);
dfs(result,temp,k,n-i,i+1);
temp.pop_back();
}
}
vector<vector<int>> combinationSum3(int k, int n) {
/**
这题和最开始的组合差不多,多了个n
*/
vector<vector<int>> result;
if(n<=0||k<=0)
return result;
vector<int> temp;
dfs(result,temp,k,n,1);
return result;
}

15,子集

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

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
void dfs(vector<int> nums, vector<vector<int>>& result,vector<int> temp,int len, int curr)
{
if(temp.size()==len)
{
result.push_back(temp);
return;
}
for(int i=curr;i<nums.size();i++)
{
temp.push_back(nums[i]);
dfs(nums,result,temp,len,i+1);
temp.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
/**
子集就是不重复的组合
*/
vector<vector<int>> result;
if(nums.empty())
return result;
vector<int> temp;
for(int i=0;i<=nums.size();i++)
dfs(nums,result,temp,i,0);
return result;
}

16,子集II

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

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
void dfs(vector<int> nums, vector<vector<int>>& result,vector<int> temp,int len, int curr)
{
if(temp.size()==len)
{
result.push_back(temp);
return;
}
for(int i=curr;i<nums.size();i++)
{
temp.push_back(nums[i]);
dfs(nums,result,temp,len,i+1);
temp.pop_back();
while(i+1<nums.size()&&nums[i]==nums[i+1]) i++;//专门去重复的,前提是排序了的
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
/**
这题和上面不同之处在于nums中是有重复的
*/
vector<vector<int>> result;
if(nums.empty())
return result;
vector<int> temp;
sort(nums.begin(), nums.end());
for(int i=0;i<=nums.size();i++)
dfs(nums,result,temp,i,0);
return result;
}

17,分割回文串

给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例:
输入: “aab”
输出:
[
[“aa”,”b”],
[“a”,”a”,”b”]
]

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
29
30
31
32
33
34
35
36
37
38
39
  vector<vector<string>> partition(string s) {
bool huiwen(string s,int left,int right)
{
while(left<right)
{
if(s[left++]!=s[right--])
return false;
}
return true;
}
void dfs(string s,vector<vector<string>>& result,vector<string> temp,int curr)
{
if(curr == s.size())
{
result.push_back(temp);
return;
}
for(int i=curr;i<s.size();i++)
{
if(huiwen(s,curr,i))
{
temp.push_back(s.substr(curr,i-curr+1));
dfs(s,result,temp,i+1);
temp.pop_back();
}
}
}
vector<vector<string>> partition(string s) {
/**
基本的遍历
*/
vector<vector<string>> result;
if(s.empty())
return result;
vector<string> temp;
dfs(s,result,temp,0);
return result;
}
}

18,解数独

编写一个程序,通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则:
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 ‘.’ 表示。
一个数独。
答案被标成红色。
Note:
给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式
来源: https://leetcode-cn.com/problems/sudoku-solver/description/

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
bool dfs(vector<vector<char>>& board,vector<vector<int>>& row,vector<vector<int>>& col,vector<vector<int>>& grid)
{
for(int i=0;i<board.size();i++)
{
for(int j=0;j<board[0].size();j++)
{
if(board[i][j]=='.')
{
for(int val =1;val<=9;val++)
{
if(!row[i][val-1]&&!col[val-1][j]&&!grid[i/3*3+j/3][val-1])
{
board[i][j] = val+'0';
row[i][val-1]=1;
col[val-1][j]=1;
grid[i/3*3+j/3][val-1]=1;
if(dfs(board,row,col,grid))
return true;
board[i][j] ='.';
row[i][val-1]=0;
col[val-1][j]=0;
grid[i/3*3+j/3][val-1]=0;
}
}
return false;
}
}
}
return true;
}
void solveSudoku(vector<vector<char>>& board) {
/**
dfs加标记位
*/
vector<vector<int>> row(board.size(),vector<int>(board[0].size(),0));
vector<vector<int>> col(board.size(),vector<int>(board[0].size(),0));
vector<vector<int>> grid(board.size(),vector<int>(board[0].size(),0));
for(int i=0;i<board.size();i++)
{
for(int j=0;j<board[0].size();j++)
{
if(board[i][j]=='.')
continue;
int val = board[i][j] - '0';
row[i][val-1]=1;
col[val-1][j]=1;
grid[i/3*3+j/3][val-1]=1;
}
}
dfs(board,row,col,grid);
}

19,n皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
bool check(vector<int>& place, int curr,int val)
{
for(int i=0;i<curr;i++)
{
if(place[i]==val||std::abs(i-curr)==std::abs(place[i]-val))
return false;
}
return true;
}
void dfs(vector<vector<string>>& result, vector<int>& place, int n,int curr)
{
if(curr ==n)
{
vector<string> temp;
for(int row =0;row<n;row++)
{
string tempStr;
for(int col =0;col<n;col++)
{
if(place[row]==col)
{
tempStr.push_back('Q');
}
else
{
tempStr.push_back('.');
}
}
temp.push_back(tempStr);
}
result.push_back(temp);
return;
}
for(int val =0;val<n;val++)
{
place[curr] = val;
if(check(place,curr,val))
dfs(result,place,n,curr+1);
place[curr] = -1;
}
}
vector<vector<string>> solveNQueens(int n) {
/**
n皇后的意思是行列都只能有一个,且对角线不能有超过两个
这里也需要对行列以及对角线进行标记
*/
vector<vector<string>> result;
if(n==0)
return result;
//vector<vector<char>> nums(n,vector<char>(n,'.'));
//vector<int> row(n,0);
// vector<int> col(n,0);
vector<int> place(n,-1);
dfs(result,place,n,0);
return result;
}