什么网站做新产品代理,龙岗网站建设设计服务,wordpress做排行榜单,怎么介绍自己做的电影网站216.组合总和III 题目链接#xff1a;组合总和III 题目描述#xff1a;找出所有相加之和为 n **的 k ****个数的组合#xff0c;且满足下列条件#xff1a; 只使用数字1到9每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次#xff0c… 216.组合总和III 题目链接组合总和III 题目描述找出所有相加之和为 n **的 k ****个数的组合且满足下列条件 只使用数字1到9每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。 解题思想
本题就是在[1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合。
本题k相当于树的深度9因为整个集合就是9个数就是树的宽度。
例如 k 2n 4的话就是在集合[1,2,3,4,5,6,7,8,9]中求 k个数 2, n和 4的组合。
选取过程如图
class Solution {
public:vectorvectorint combinationSum3(int k, int n) {int sum 0;backtracking(k, n, sum, 1);return result;}private:vectorvectorint result;vectorint path;void backtracking(int k, int n, int sum, int startIndex) {if (path.size() k) {if (sum n)result.push_back(path);return;}for (int i startIndex; i 9; i) {path.push_back(i);sum i;backtracking(k, n, sum, i 1);path.pop_back();sum - i;}}
};剪枝优化
已选元素总和如果已经大于n了那么往后遍历就没有意义了直接剪掉。for循环的范围也可以剪枝i 9 - (k - path.size()) 1就可以了。k-path.size()为还需要的元素个数后面的元素个数不足了。
class Solution {
public:vectorvectorint combinationSum3(int k, int n) {int sum 0;backtracking(k, n, sum, 1);return result;}private:vectorvectorint result;vectorint path;void backtracking(int k, int n, 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) {path.push_back(i);sum i;backtracking(k, n, sum, i 1);path.pop_back();sum - i;}}
};17.电话号码的字母组合 题目链接电话号码的字母组合 题目描述给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 !https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/11/09/200px-telephone-keypad2svg.png 解题思想
理解本题后要解决如下三个问题 数字和字母如何映射 可以使用map或者定义一个二维数组例如string letterMap[10] 两个字母就两个for循环三个字符我就三个for循环以此类推然后发现代码根本写不出来 例如输入“23”抽象为树形结构如图所示 图中可以看出遍历的深度就是输入23的长度而叶子节点就是我们要收集的结果输出[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]。 输入1 * #按键等等异常情况
class Solution {
public:vectorstring letterCombinations(string digits) {if (!digits.empty())backtracking(digits, 0);return result;}private:string path;vectorstring result;void backtracking(const string digits, int index) {if (index digits.size()) {result.push_back(path);return;}string letter letterMap[digits[index] - 0];for (int i 0; i letter.size(); i) {path.push_back(letter[i]);backtracking(digits, index 1);path.pop_back();}}const string letterMap[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz, // 9};
};时间复杂度: O(3^m * 4^n)其中 m 是对应四个字母的数字个数n 是对应三个字母的数字个数空间复杂度: O(3^m * 4^n)
