定制网站建设基础步骤,江苏省城乡建设局网站,网站设计一般包括哪几个部分,二级域名做网站好不好目录 组合总和III思路解题方法复杂度Code 电话号码的字母组合思路解题方法复杂度Code 总结 组合总和III
链接: 组合总和III
找出所有相加之和为 n 的 k 个数的组合#xff0c;且满足下列条件#xff1a;
只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列… 目录 组合总和III思路解题方法复杂度Code 电话号码的字母组合思路解题方法复杂度Code 总结 组合总和III
链接: 组合总和III
找出所有相加之和为 n 的 k 个数的组合且满足下列条件
只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次组合可以以任何顺序返回。
示例 1:
输入: k 3, n 7 输出: [[1,2,4]] 解释: 1 2 4 7 没有其他符合的组合了。 示例 2:
输入: k 3, n 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 解释: 1 2 6 9 1 3 5 9 2 3 4 9 没有其他符合的组合了。 示例 3:
输入: k 4, n 1 输出: [] 解释: 不存在有效的组合。 在[1,9]范围内使用4个不同的数字我们可以得到的最小和是1234 10因为10 1没有有效的组合。
思路
可以用子集枚举的方法来做这道题。即原序列中有 999 个数每个数都有两种状态「被选择到子集中」和「不被选择到子集中」所以状态的总数为 292^92 9 。我们用一个 999 位二进制数 mask\rm maskmask 来记录当前所有位置的状态从第到高第 iii 位为 000 表示 iii 不被选择到子集中为 111 表示 iii 被选择到子集中。当我们按顺序枚举 [0,29−1][0, 2^9 - 1][0,2 9 −1] 中的所有整数的时候就可以不重不漏地把每个状态枚举到对于一个状态 mask\rm maskmask我们可以用位运算的方法得到对应的子集序列然后再判断是否满足上面的两个条件如果满足就记录答案。
解题方法
看代码即可
复杂度
时间复杂度O(n * 2^n)空间复杂度O(n)
Code
class Solution {
public:vectorint temp;vectorvectorint ans;bool check(int mask, int k, int n) {temp.clear();for (int i 0; i 9; i) {if ((1 i) mask) {temp.push_back(i 1);}}return temp.size() k accumulate(temp.begin(), temp.end(), 0) n; }vectorvectorint combinationSum3(int k, int n) {for (int mask 0; mask (1 9); mask) {if (check(mask, k, n)) {ans.emplace_back(temp);}}return ans;}
};电话号码的字母组合
链接: 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
示例 1
输入digits “23” 输出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”] 示例 2
输入digits “” 输出[] 示例 3
输入digits “2” 输出[“a”,“b”,“c”]
思路
从示例上来说输入23最直接的想法就是两层for循环遍历了吧正好把组合的情况都输出了。
如果输入233呢那么就三层for循环如果2333呢就四层for循环… 得使用回溯算法。
解题方法
使用哈希表存储每个数字对应的所有可能的字母然后进行回溯操作。
回溯过程中维护一个字符串表示已有的字母排列如果未遍历完电话号码的所有数字则已有的字母排列是不完整的。该字符串初始为空。每次取电话号码的一位数字从哈希表中获得该数字对应的所有可能的字母并将其中的一个字母插入到已有的字母排列后面然后继续处理电话号码的后一位数字直到处理完电话号码中的所有数字即得到一个完整的字母排列。然后进行回退操作遍历其余的字母排列。
回溯算法用于寻找所有的可行解如果发现一个解不可行则会舍弃不可行的解。在这道题中由于每个数字对应的每个字母都可能进入字母组合因此不存在不可行的解直接穷举所有的解即可。
复杂度
时间复杂度O(3^m * 4^n)其中 m 是对应四个字母的数字个数n 是对应三个字母的数字个数空间复杂度O(3^m * 4^n)
Code
class Solution {
private:const string letterMap[10] {, // 0, // 1abc, // 2def, // 3ghi, // 4jkl, // 5mno, // 6pqrs, // 7tuv, // 8wxyz, // 9};
public: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; // 将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;}
};总结
两题都比较难得先看对应的视频讲解在写会好很多参考文档:链接: .组合总和III链接: 电话号码的字母组合
