leetCode 17.电话号码的字母组合
思路:首先将每个数字所对应的字母找出来,然后依次枚举每个答案
23——“abc”,”def”
在初始的时候,状态为0
1.先将一个数字所对应的字母放进状态1中,也就即a,b,c(更新答案);
2.枚举到第二个数字的时候,在枚举这个数字能用的字母时,再在状态1中插入第二个数字的代表字母
也就即ad,bd,cd;ae,be,ce;af,bf,cf——状态2
之后类似的往后枚举
class Solution {
public:
string nums[8]={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
vector<string> letterCombinations(string digits) {
vector<string> state(1,"");
if(digits.empty())return vector<string>();
for(auto c:digits)
{
vector<string> now;
for(auto x:nums[c-'2'])
for(auto t:state)
now.push_back(t+x);
state=now;
}
return state;
}
};
leetCode 79. 单词搜索
思路:首先找到第一个相同的字符,然后深搜去找
技巧:四个方向的枚举以及dfs的参数变化
class Solution {
public:
int n,m;
int dx[4]={1,-1,0,0},dy[4]={0,0,-1,1};
bool exist(vector<vector<char>>& board, string word) {
n = board.size(), m = board[0].size();
if(board.empty()||board[0].empty())return false;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(dfs(board,i,j,word,0))return true;
return false;
}
bool dfs(vector<vector<char>>& board,int x,int y,string& word,int u)
{
if(board[x][y]!=word[u])return false;
if(u==word.size()-1)return true;
board[x][y]='.';
for(int i=0;i<4;i++)
{
int a=dx[i]+x,b=dy[i]+y;
if(a>=0&&a<n&&b>=0&&b<m)
{
if(dfs(board,a,b,word,u+1))return true;
}
}
board[x][y]=word[u];
return false;
}
};
leeoCode 46. 全排列
思路:算法基础课
class Solution {
public:
vector<vector<int>>res;
vector<int>path;
int n;
bool st[20];
vector<vector<int>> permute(vector<int>& nums) {
n=nums.size();
dfs(nums,0);
return res;
}
void dfs(vector<int>& nums,int u)
{
if(u==n)
{
res.push_back(path);
return ;
}
for(int i=0;i<n;i++)
if(!st[i])
{
st[i]=true;
path.push_back(nums[i]);
dfs(nums,u+1);
st[i]=false;
path.pop_back();
}
}
};
leetCode 47. 全排列 II(含有重复元素)
1.通过枚举每个数的位置
2.枚举每个数放或者不放
思路:将重复的元素放在一起,然后枚举——通过排序,可以将相同的元素放在一起
class Solution {
public:
bool st[20];
int n;
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(),nums.end());
n = nums.size();
dfs(nums,0);
return res;
}
void dfs(vector<int>& nums,int u)
{
if(u==n)
{
res.push_back(path);
return ;
}
for(int i=0;i<n;i++)
if(!st[i])
{
st[i]=true;
path.push_back(nums[i]);
dfs(nums,u+1);
st[i]=false;
path.pop_back();
while(i+1<n&&nums[i+1]==nums[i])i++;
//找到不重复的元素
}
}
};