字符串排列组合（不含相同的数）
Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
通用的写法：
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> rec;
if(nums.size()<=0)
return rec;
dfs(nums,0,rec);
return rec;
}
void dfs(vector<int>& nums,int start,vector<vector<int>>& rec)
{
if(start==nums.size())
{
rec.push_back(nums);
}
else
{
for(int i=start;i<nums.size();i++)
{
swap(nums[start],nums[i]);//入栈
dfs(nums,start+1,rec);
swap(nums[start],nums[i]);//出栈
}
}
}
};
字符串排列组合（含相同的数）
class Solution {
public:
set<vector<int>> mSet;
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> rec;
if(nums.size()<=0)
return rec;
sort(nums.begin(),nums.end());
dfs(nums,0);
for(auto a:mSet)
rec.push_back(a);
//return vector<vector<int>>(mSet.begin(),mSet.end());
return rec;
}
void dfs(vector<int>& nums,int start)
{
if(start==nums.size())
{
mSet.insert(nums);
//rec.push_back(nums);
}
else
{
for(int i=start;i<nums.size();i++)
{
if(i!=start&&nums[i]==nums[i-1])
continue;
swap(nums[start],nums[i]);
dfs(nums,start+1);
swap(nums[start],nums[i]);
}
}
}
};
八皇后问题
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<int> nums;
for(int i=0;i<n;i++)
nums.push_back(i);
vector<vector<string>> rec;
if(n<=0)
return rec;
dfs(nums,0,rec);
return rec;
}
void dfs(vector<int>& nums,int start,vector<vector<string>>& rec)
{
if(start==nums.size()&&isValid(nums))
{
vector<string> temp;
for(int i=0;i<nums.size();i++)
{
string s;
for(int j=0;j<nums.size();j++)
{
if(nums[i]==j)
s += "Q";
else
s += ".";
}
temp.push_back(s);
}
rec.push_back(temp);
}
else
{
for(int i=start;i<nums.size();i++)
{
swap(nums[start],nums[i]);
dfs(nums,start+1,rec);
swap(nums[start],nums[i]);
}
}
}
bool isValid(vector<int>& nums)
{
for(int i=0;i<nums.size();i++)
for(int j=i+1;j<nums.size();j++)
{
if(abs(nums[i]-nums[j])==abs(i-j))
return false;
}
return true;
}
};
**Subsets **
Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
代码如下
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> rec;
int n = nums.size();
if(n<=0)
return rec;
vector<int> temp;
sort(nums.begin(),nums.end());
dfs(nums,0,temp,rec);
return rec;
}
void dfs(vector<int>& nums,int start,vector<int>& temp,vector<vector<int>>& rec)
{
rec.push_back(temp);
for(int i=start;i<nums.size();i++)
{
temp.push_back(nums[i]);
dfs(nums,i+1,temp,rec);
temp.pop_back();
}
}
};
Subsets II
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
代码如下：
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> rec;
int n = nums.size();
if(n<=0)
return rec;
vector<int> temp;
sort(nums.begin(),nums.end());
dfs(nums,0,temp,rec);
return rec;
}
void dfs(vector<int>& nums,int start,vector<int>& temp,vector<vector<int>>& rec)
{
rec.push_back(temp);
for(int i=start;i<nums.size();i++)
{
if(i!=start&&nums[i]==nums[i-1])
continue;
temp.push_back(nums[i]);
dfs(nums,i+1,temp,rec);
temp.pop_back();
}
}
};
**Combination Sum **
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]
代码如下：
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> rec;
vector<int> temp;
if(candidates.size()<=0||target<=0)
return rec;
sort(candidates.begin(),candidates.end());
dfs(rec,temp,candidates,0,target);
return rec;
}
void dfs(vector<vector<int>>& rec,vector<int>& temp,vector<int>& candidates,int start,int target)
{
if(target==0)
{
rec.push_back(temp);
}
else
{
for(int i=start;i<candidates.size();i++)
{
if(target>=candidates[i])
{
temp.push_back(candidates[i]);
dfs(rec,temp,candidates,i,target-candidates[i]);
temp.pop_back();
}
}
}
}
};
Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, 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]
]
代码如下：
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> rec;
vector<int> temp;
if(candidates.size()<=0||target<=0)
return rec;
sort(candidates.begin(),candidates.end());
dfs(rec,temp,candidates,0,target);
return rec;
}
void dfs(vector<vector<int>>& rec,vector<int>& temp,vector<int>& candidates,int start,int target)
{
if(target==0)
{
rec.push_back(temp);
}
else
{
for(int i=start;i<candidates.size();i++)
{
if(i!=start&&candidates[i]==candidates[i-1])
continue;
if(target>=candidates[i])
{
temp.push_back(candidates[i]);
dfs(rec,temp,candidates,i+1,target-candidates[i]);
temp.pop_back();
}
}
}
}
};
**Word Search **
Given a 2D board and a word, find if the word exists in the grid.
The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.
For example,
Given board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
代码如下：
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
int m = board.size();
int n = board[0].size();
if(m<=0||n<=0)
return false;
if(word.size()==0)
return true;
vector<vector<bool>> visited(m,vector<bool>(n,false));
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
if(dfs(board,visited,0,i,j,word))
return true;
}
return false;
}
bool dfs(vector<vector<char>>& board,vector<vector<bool>>& visited,int index,int i,int j,string word)
{
// cout<<"index:"<<index<<" "<<"word:"<<word.size()<<"<---->"<<"i:"<<i<< " "<<" j:"<<j<<endl;
if(index==word.size())
return true;
if(i<0||j<0||i>=board.size()||j>=board[0].size())
return false;
if(board[i][j]!=word[index])
return false;
if(visited[i][j])
return false;
visited[i][j] = true;
if(dfs(board,visited,index+1,i+1,j,word))
return true;
if(dfs(board,visited,index+1,i-1,j,word))
return true;
if(dfs(board,visited,index+1,i,j+1,word))
return true;
if(dfs(board,visited,index+1,i,j-1,word))
return true;
visited[i][j] = false;
return false;
}
};
**Letter Combinations of a Phone Number **
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
class Solution {
public:
vector<string> v= {"","","abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
//vector<string> ans;
void dfs(int start,string &d,string &temp,vector<string> &ans)
{
if(start==d.size())
{
ans.push_back(temp);
return;
}
for(int i=0;i<v[d[start]-'0'].size();i++) //注意i从0开始计算
{
temp.push_back(v[d[start]-'0'][i]);
dfs(start+1,d,temp,ans);
temp.pop_back();
}
}
vector<string> letterCombinations(string digits) {
vector<string> ans;
string temp;
if(digits.size()<=0)
return ans;
dfs(0,digits,temp,ans);
return ans;
}
};
**Surrounded Regions **
Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:
X X X X
X X X X
X X X X
X O X X
class Solution {
public:
void solve(vector<vector<char>>& board) {
if(board.empty())
return;
int m = board.size();
int n = board[0].size();
for(int j=0;j<n;j++)
if(board[0][j]=='O')
dfs(board,0,j);
for(int i=1;i<m;i++)
if(board[i][0]=='O')
dfs(board,i,0);
for(int j=1;j<n;j++)
if(board[m-1][j]=='O')
dfs(board,m-1,j);
for(int i=1;i<m-1;i++)
if(board[i][n-1]=='O')
dfs(board,i,n-1);
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
if(board[i][j]=='O')
board[i][j] = 'X';
else if(board[i][j]=='#')
board[i][j] = 'O';
}
return;
}
void dfs(vector<vector<char>>& board,int i,int j)
{
board[i][j] = '#';
if(i-1>=0&&board[i-1][j]=='O')
dfs(board,i-1,j);
if(i+1<board.size()&&board[i+1][j]=='O')
dfs(board,i+1,j);
if(j-1>=0&&board[i][j-1]=='O')
dfs(board,i,j-1);
if(j+1<board[0].size()&&board[i][j+1]=='O')
dfs(board,i,j+1);
//board[i][j] = 'O';
return;
}
};
