网站设计服务,html网页设计论文2000字,做网站需要学什么软件,织梦做的网站目录#xff1a;
解题及思路学习
216. 组合总和 III
找出所有相加之和为 n **的 k ****个数的组合#xff0c;且满足下列条件#xff1a;
只使用数字1到9每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次#xff0c;组合可以以任…目录
解题及思路学习
216. 组合总和 III
找出所有相加之和为 n **的 k ****个数的组合且满足下列条件
只使用数字1到9每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
示例 1:
输入:k 3,n 7
输出: [[1,2,4]]
解释:
1 2 4 7
没有其他符合的组合了。思考所有相加之和为n的k个数可以传入一个总和值。由于只能使用组合所有得使用startindex。
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(int k, int n, int startindex, int target) {if (path.size() k target 0) {result.push_back(path);return;}if (target 0) return;for (int i startindex; i 9; i) {path.push_back(i);target - i;backtracking(k, n, i 1, target);target i;path.pop_back();}}vectorvectorint combinationSum3(int k, int n) {result.clear();path.clear();backtracking(k, n, 1, n);return result;}
};上面式子中传入了四个参数只传入三个参数也可以
class Solution {
public:vectorvectorint result;vectorint path;void backtracking(int k, int n, int startindex) {if (path.size() k n 0) {result.push_back(path);return;}if (startindex 0) return;for (int i startindex; i 9; i) {path.push_back(i);backtracking(k, n - i, i 1);path.pop_back();}}vectorvectorint combinationSum3(int k, int n) {result.clear();path.clear();backtracking(k, n, 1);return result;}
};含有剪枝操作的代码
class Solution {
private:vectorvectorint result; // 存放结果集vectorint path; // 符合条件的结果void backtracking(int targetSum, int k, int sum, int startIndex) {if (sum targetSum) { // 剪枝操作return; // 如果path.size() k 但sum ! targetSum 直接返回}if (path.size() k) {if (sum targetSum) result.push_back(path);return;}for (int i startIndex; i 9 - (k - path.size()) 1; i) { // 剪枝sum i; // 处理path.push_back(i); // 处理backtracking(targetSum, k, sum, i 1); // 注意i1调整startIndexsum - i; // 回溯path.pop_back(); // 回溯}}public:vectorvectorint combinationSum3(int k, int n) {result.clear(); // 可以不加path.clear(); // 可以不加backtracking(n, k, 0, 1);return result;}
};时间复杂度: O(n * 2^n)空间复杂度: O(n)
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
!https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/11/09/200px-telephone-keypad2svg.png
示例 1
输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]思考要解决的三个问题
1、数字和字母的映射 - 使用map或者定义一个二维数组。
2、回溯遍历
3、输入1 * # 等异常情况
class Solution {
public:const string letterMap[10] {,, abc, def, ghi, jkl, mno, pqrs, tuv, wxyz};vectorstring result;string s;void backtracking(const string digits, int index) {if (index digits.size()) {result.push_back(s);return;}int digit digits[index] - 0;string letter letterMap[digit];for (int i 0; i letter.size(); i) {s.push_back(letter[i]);backtracking(digits, index 1);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)其中 m 是对应四个字母的数字个数n 是对应三个字母的数字个数空间复杂度: O(3^m * 4^n)
复盘总结
个人反思
1、回溯法中递归函数参数很难一次性确定下来一般先写逻辑需要啥参数了填什么参数。
2、这种利用二位数组下标来存放元素的方法非常值得学习。本题最主要的是如何根据元素取到对应的循环。
