网站建设页面大小,网站开发合同管辖权异议,深圳公司注册电话,wordpress 标题字数Leetcode: 216 组合总和III
经过了昨天组合的题目的学习#xff0c;这道题比较简单#xff0c;套用之前的模板就可以
基本思路
终止条件#xff0c;遇到向量的个数一样#xff0c;并且sum等于n的时候终止。输入变量#xff0c;n,k#xff0c;还有起始的idx和基于当前元…Leetcode: 216 组合总和III
经过了昨天组合的题目的学习这道题比较简单套用之前的模板就可以
基本思路
终止条件遇到向量的个数一样并且sum等于n的时候终止。输入变量n,k还有起始的idx和基于当前元素之和的sum逻辑就是按照循环递归下去注意要对sum值进行回溯。
时间复杂度O(n * 2^n)
空间复杂度O(N)
class Solution {
private:vectorvectorint result;vectorint vec;void traceback(int k, int n, int idx, int sum){if(vec.size() k sum n){result.push_back(vec);return;}for(int i idx; i 9; i){vec.push_back(i);sum i;//计算当前元素之和traceback(k, n, i1, sum);//进行递归sum - i;//注意sum值的回溯vec.pop_back();}}
public:vectorvectorint combinationSum3(int k, int n) {traceback(k, n, 1, 0);return result;}
};
减枝优化
1、每个数值的取值范围为1-9与上题一样的剪枝操作。2、当所有元素之和已经大于n的时候后续就不需要进行递归了。
for (int i startIndex; i 9 - (k - path.size()) 1; i) { // 剪枝sum i; // 处理path.push_back(i); // 处理if (sum targetSum) { // 剪枝操作sum - i; // 剪枝之前先把回溯做了path.pop_back(); // 剪枝之前先把回溯做了return;}backtracking(targetSum, k, sum, i 1); // 注意i1调整startIndexsum - i; // 回溯path.pop_back(); // 回溯
}
Leetcode: 17 电话号码的字母组合
字母和数字的映射
需要先定义一个二维数组来存放映射关系。
const string letterMap[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz, // 9
};
基本思路
输入要求的digit和定义一个idx来记录目前遍历到哪个数字了。终止条件当遍历的数字和digit长度一样的时候。遍历逻辑首先要取index指向的数字并找到对应的字符集手机键盘的字符集。
class Solution {
private:const string letterMap[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz, // 9};public:vectorstring result;string str;void traceback(string digits, int idx){if(idx digits.size()){result.push_back(str);return;}int digit digits[idx] - 0; // 将idx指向的数字转为intstring letters letterMap[digit]; // 取数字对应的字符集for (int i 0; i letters.size(); i) {str.push_back(letters[i]); // 处理traceback(digits, idx 1); // 递归注意index1一下层要处理下一个数字了str.pop_back(); // 回溯}}vectorstring letterCombinations(string digits) {if (digits.size() 0) {return result;}traceback(digits, 0);return result;}
};
本题的难点主要在于1、字母表和数字的映射建立和相互转换 2、递归逻辑的梳理
