目前电商平台有哪些,六年级下册数学优化设计答案,wordpress文章密码插件,设置wordpress网页私有刷题的第二十一天#xff0c;希望自己能够不断坚持下去#xff0c;迎来蜕变。#x1f600;#x1f600;#x1f600; 刷题语言#xff1a;C Day21 任务 ● 216.组合总和III ● 17.电话号码的字母组合
1 组合总和III
216.组合总和III 思路#xff1a; 在[1,2,3,4,5,6,…刷题的第二十一天希望自己能够不断坚持下去迎来蜕变。 刷题语言C Day21 任务 ● 216.组合总和III ● 17.电话号码的字母组合
1 组合总和III
216.组合总和III 思路 在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合 1确定递归函数参数返回值 返回值void 参数目标和nksum已经收集的元素的总和startIndex
vectorvectorint result;
vectorintpath;
void backtracking(int n, int k, int sum, int startIndex)2确认终止条件
if (path.size() k) {if (sum n) result.push_back(path);return;
}3单层搜索过程 path收集每次选取的元素sum来统计path里元素的总和 for (int i startIndex; i 9; i) {sum i;path.push_back(i);backtracking(n, k, sum, i 1); // 注意i1调整startIndexsum - i;// 回溯path.pop_back();// 回溯
}C
class Solution {
public:vectorvectorint result;// 存放结果集vectorint path;// 符合条件的结果void traversal(int n, int k, int sum, int startIndex) {if (path.size() k) {if (sum n) result.push_back(path);return;// 如果path.size() k 但sum ! targetSum 直接返回}for (int i startIndex; i 9; i) {sum i;// 处理path.push_back(i);// 处理traversal(n, k, sum, i 1);// 注意i1调整startIndexsum - i;// 回溯path.pop_back();// 回溯}}vectorvectorint combinationSum3(int k, int n) {traversal(n, k, 0, 1);return result;}
};剪枝优化 1已选元素总和如果已经大于n那么往后遍历就没有意义 剪枝的地方可以放在递归函数开始的地方 if (sum n) return;2for循环的范围也可以剪枝i 9 - (k - path.size()) 1
剪枝优化C
class Solution {
public:vectorvectorint result;vectorint path;void traversal(int n, int k, int sum, int startIndex) {if (sum n) return;if (path.size() k) {if (sum n) result.push_back(path);return;}for (int i startIndex; i 9 - (k - path.size()) 1; i) {sum i;path.push_back(i);traversal(n, k, sum, i 1);sum - i;path.pop_back();}}vectorvectorint combinationSum3(int k, int n) {traversal(n, k, 0, 1);return result;}
};2 电话号码的字母组合
17.电话号码的字母组合 1数字和字母如何映射 2用for循环写不出来 3输入1 * #按键等等异常情况 思路
数字和字母如何映射 使用map或者定义一个二维数组
const string[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs,// 7tuv, // 8wxyz,// 9
};回溯法来解决n个for循环的问题 1确定回溯函数参数 参数digitsindex记录遍历第几个数字
vectorstring result;
string s;
void backtracking(const string digits, int index)2确定终止条件
if (index digits.size()) {result.push_back(s);return;
}3确定单层遍历逻辑 1首先要取index指向的数字并找到对应的字符集。 2然后for循环来处理这个字符集
int digit digits[index] - 0;
string letters letterMap[digit];
for (int i 0; i letter.size(); i) {s.push_back(letters[i]);backtracking(digits, index 1);s.pop_back();
}C
class Solution {
public:const string letterMap[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs,// 7tuv, // 8wxyz // 9};string s;vectorstring result;void backtracking(const string digits, int index){if (index digits.size()) {result.push_back(s);return;}int digit digits[index] - 0;// 将index指向的数字转为intstring letters letterMap[digit];// 取数字对应的字符集for (int i 0; i letters.size(); i) {s.push_back(letters[i]);// 处理backtracking(digits, index 1); // 递归注意index1一下层要处理下一个数字s.pop_back();// 回溯}}vectorstring letterCombinations(string digits) {s.clear();result.clear();if (digits.size() 0) return result;backtracking(digits, 0);return result;}
};时间复杂度 O ( 3 m ∗ 4 n ) O(3^m * 4^n) O(3m∗4n) m 是对应四个字母的数字个数n 是对应三个字母的数字个数 空间复杂度: O ( 3 m ∗ 4 n ) O(3^m * 4^n) O(3m∗4n) 鼓励坚持二十二天的自己
