17 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
因为输入的数字的数量是不确定的,所以for循环的次数也是不确定的,这里就需要用到回溯的方法了。
一般回溯里面,递归都是深度,for循环都是宽度。注意本题的index和之前两道题的index不太一样,因为本题不是从同一个集合里面取,而是从多个集合里面取。同时for循环的起始位置是0,因为此时不存在从同一个集合里面取相同的数的问题了。
class Solution {
private:
//记录对应的关系
const string letterMap[10] = {
" ",
" ",
"abc",
"def",
"ghi",
"jkl",
"mno",
"pqrs",
"tuv",
"wxyz",
};
vector<string> result; //存放结果
string s; //存放字符串
void backtracking(string digits, int index) {
if(index == digits.size()) { //index表示的是第几个数字,数字等于数字大小就停止
result.push_back(s);
return;
}
int digit = digits[index]-'0'; //将index转换为“23”里的数字
string letters = letterMap[digit]; //根据数字在哈希表里面找字符串
for(int i = 0; i < letters.size(); i++) {
s.push_back(letters[i]); //处理
backtracking(digits,index+1); //递归
s.pop_back(); //回溯
}
}
public:
vector<string> letterCombinations(string digits) {
result.clear();
if(digits.size()==0) return result; //特殊处理以下等于0的时候
backtracking(digits, 0);
return result;
}
};
本题也可以将回溯隐含在函数中,但是不建议这么写,不直观。
// 版本二
class Solution {
private:
const string letterMap[10] = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz", // 9
};
public:
vector<string> result;
void getCombinations(const string& digits, int index, const string& s) { // 注意参数的不同
if (index == digits.size()) {
result.push_back(s);
return;
}
int digit = digits[index] - '0';
string letters = letterMap[digit];
for (int i = 0; i < letters.size(); i++) {
getCombinations(digits, index + 1, s + letters[i]); // 注意这里的不同
}
}
vector<string> letterCombinations(string digits) {
result.clear();
if (digits.size() == 0) {
return result;
}
getCombinations(digits, 0, "");
return result;
}
};
39 组合求和
给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明:
- 所有数字(包括 target)都是正整数。
- 解集不能包含重复的组合。
这道题与之前那题的不同之处在于数字是题目给的,并且可以重复,总的来说都差不多。
注意因为可以重复,所以递归函数里不用i+1而直接是i
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int startIndex) {
if(target < 0) return;
if(target == 0) {
result.push_back(path);
return;
}
for(int i = startIndex; i < candidates.size(); i++) {
path.push_back(candidates[i]);
target -= candidates[i];
backtracking(candidates, target, i); //这里不需要i+1了因为可以重复的取
target += candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
result.clear();
path.clear();
backtracking(candidates, target, 0);
return result;
}
};
这里可以进行剪枝操作,对这个数组排完序以后,如果前面的比target大了,那么后面也就不用看了:
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int startIndex) {
if(target < 0) return;
if(target == 0) {
result.push_back(path);
return;
}
for(int i = startIndex; i < candidates.size() && (target-candidates[i])>=0; i++) {
path.push_back(candidates[i]);
target -= candidates[i];
backtracking(candidates, target, i); //这里不需要i+1了因为可以重复的取
target += candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
result.clear();
path.clear();
sort(candidates.begin(), candidates.end()); // 需要排序
backtracking(candidates, target, 0);
return result;
}
};
40 组合求和II
给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明: 所有数字(包括目标数)都是正整数。解集不能包含重复的组合。
本题与上一题的不同之处就是给的数组里面有重复的元素,导致后面可能重复利用这个元素,但是还不能有重复的组合。文章来源:https://www.toymoban.com/news/detail-794886.html
这里利用一个used数组,里面存放布尔型数据,如果是1就说明这个数用过。首先对题目给的数组进行排序,去重有两种形式:树层去重和树枝去重,显而易见,我们不需要数值去重,但是需要树层去重,如果此时遍历的元素和上一个相同,并且上一个元素没有被使用过(如果使用过的话说明是树枝去重了,没有回溯的话used就不会重新被置为false),此时证明正在访问的元素是回溯以后的,并不是树枝,所以直接跳过就好了。文章来源地址https://www.toymoban.com/news/detail-794886.html
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& candidates, int target, int startIndex, vector<bool> used) {
if(target < 0) return;
if(target == 0) {
result.push_back(path);
return;
}
for(int i = startIndex; i < candidates.size()&&(target-candidates[i])>=0; i++) {
if(i>0 && candidates[i]==candidates[i-1] && used[i-1] == false) continue;
path.push_back(candidates[i]);
target -= candidates[i];
used[i] = true;
backtracking(candidates, target, i+1, used);
used[i] = false;
target += candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
result.clear();
path.clear();
vector<bool> used(candidates.size(), false);
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, used);
return result;
}
};
到了这里,关于Day28 17电话号码的字母组合 39组合求和 40组合求和II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!