【每日刷题】Day125
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 17. 电话号码的字母组合 - 力扣（LeetCode）
2. LCR 080. 组合 - 力扣（LeetCode）
1. 17. 电话号码的字母组合 - 力扣（LeetCode）
//思路：深搜+回溯。
//一张图理解：
class Solution {
public:
vector<string> ans;
string tmp;
void _letterCombinations(string& digits,vector<string>& flag,int level = 0)
{
if(tmp.size()==digits.size())
{
ans.push_back(tmp);
return;
}
for(int i = 0;i<flag[digits[level]-'0'].size();i++)
{
tmp.push_back(flag[digits[level]-'0'][i]);
_letterCombinations(digits,flag,level+1);
tmp.pop_back();
}
}
vector<string> letterCombinations(string digits)
{
if(digits=="") return ans;
vector<string> flag = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
_letterCombinations(digits,flag);
return ans;
}
};
2. LCR 080. 组合 - 力扣（LeetCode）
//思路：深搜+回溯
//一张图理解
class Solution {
public:
vector<vector<int>> ans;
vector<int> tmp;
bool check[21];
void _combine(vector<int>& arr,int k)
{
if(tmp.size()==k)
{
ans.push_back(tmp);
return;
}
for(int i = 0;i<arr.size();i++)
{
if(check[i]) continue;
tmp.push_back(arr[i]);
for(int j = i;j>=0;j--) check[j] = true;//防止重复
_combine(arr,k);
tmp.pop_back();
for(int m = i;m>=0;m--) check[m] = false;
}
}
vector<vector<int>> combine(int n, int k)
{
vector<int> arr;
for(int i = 1;i<=n;i++) arr.push_back(i);
_combine(arr,k);
return ans;
}
};
