代码随想录算法训练营第23期day25

算法训练营第23期day25"/>

代码随想录算法训练营第23期day25

目录

一、（leetcode 216）组合总和III

剪枝

二、（leetcode 17）电话号码的字母组合

思路

一、（leetcode 216）组合总和III

力扣题目链接

状态：已AC，就是在77题的前提下，多加了一个限制，需要和为定值

• 确定递归函数参数
• 确定终止条件
• 单层搜索逻辑

class Solution {
private:vector<vector<int>> result; // 存放结果集vector<int> path; // 符合条件的结果// sum：已经收集的元素的总和，也就是path里元素的总和。// startIndex：下一层for循环搜索的起始位置。void backtracking(int targetSum, int k, int sum, int startIndex) {if (path.size() == k) {if (sum == targetSum) result.push_back(path);return; // 如果path.size() == k 但sum != targetSum 直接返回}for (int i = startIndex; i <= 9; i++) {sum += i;path.push_back(i); backtracking(targetSum, k, sum, i + 1); // 注意i+1调整startIndexsum -= i; // 回溯path.pop_back(); }}public:vector<vector<int>> combinationSum3(int k, int n) {backtracking(n, k, 0, 1);return result;}
};

剪枝

剪枝的地方可以放在递归函数开始的地方

if (sum > targetSum) { // 剪枝操作return;
}

也可以放在调用递归之前，要记得要回溯操作给做了。

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); // 注意i+1调整startIndexsum -= i; // 回溯path.pop_back(); // 回溯
}

二、（leetcode 17）电话号码的字母组合

力扣题目链接

状态：查看思路后AC，没有想到如果出现输入1 * #按键等等异常情况怎么办

思路

1. 数字和字母如何映射
2. 两个字母就两个for循环，三个字符我就三个for循环，以此类推，然后发现代码根本写不出来
3. 输入1 * #按键等等异常情况

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;string s;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);    // 递归，注意index+1，一下层要处理下一个数字了s.pop_back();                       // 回溯}}vector<string> letterCombinations(string digits) {s.clear();result.clear();if (digits.size() == 0) {return result;}backtracking(digits, 0);return result;}
};