描述自己做的网站,wordpress图片文字排版,做网站的 需要续费维护费吗,二进制可以做网站是吗组合总和III
216. 组合总和 III - 力扣#xff08;LeetCode#xff09; 思路和昨日的组合题类似#xff0c;但注意对回溯算法中#xff0c;收获时的条件需要写对#xff0c;path的长度要为k的同时#xff0c;path中元素总和要为n。
class Solution {
public:vector…组合总和III
216. 组合总和 III - 力扣LeetCode 思路和昨日的组合题类似但注意对回溯算法中收获时的条件需要写对path的长度要为k的同时path中元素总和要为n。
class Solution {
public:vectorint path;vectorvectorint paths;int sum 0; // 维护当前路径的和void backtracking(int k, int n, int startindex) {if (path.size() k sum n) {paths.push_back(path);return;}for (int i startindex; i 9; i) {path.push_back(i);sum i; // 更新路径和backtracking(k, n, i 1);sum - i; // 回溯时恢复路径和path.pop_back();}}vectorvectorint combinationSum3(int k, int n) {backtracking(k, n, 1);return paths;}
};算法的时间复杂度在最差的情况需我们需要生成所有C(9,n)个组合并且对于每个组合都需要进行k层递归因此时间复杂度为O(C(9,n)*n)。
空间复杂度考虑递归栈递归栈的最大深度为n每个组合需要n个元素的存储空间隐形空间复杂度是O(n)。
电话号码的字母组合
17. 电话号码的字母组合 - 力扣LeetCode
首先考虑使用一个哈希表来存储数值这里用数值方便些之后用 i - 0可以将char转换为整形与字符的映射关系。
具体参考代码随想录 (programmercarl.com)
回溯三步法
1.确定回溯函数参数我们每次回溯返回的值都会存放在一个path字符串中并存在一个paths数组存放所有的组合结果中我们用全局变量表示此外我们还需要一个变量index来指示现在遍历的位置。
2.确认终止条件。当index与需要遍历的字符长度相同时就将值存入path中并返回。
3.单层遍历逻辑我们需要知道在当前index下的umap存储的字符串大小然后对这个字符串中的字符进行递归遍历。之后对下一个字符进行处理因为本题是求不同集合间的组合。
整体代码
class Solution {
public:vectorstring paths; // 用于存储所有可能的字母组合string path; // 用于存储当前的字母组合unordered_mapint, vectorchar umap; // 创建一个映射表将数字映射到对应的字母Solution() {umap[2] {a, b, c}; // 数字2对应的字母umap[3] {d, e, f}; // 数字3对应的字母umap[4] {g, h, i}; // 数字4对应的字母umap[5] {j, k, l}; // 数字5对应的字母umap[6] {m, n, o}; // 数字6对应的字母umap[7] {p, q, r, s}; // 数字7对应的字母umap[8] {t, u, v}; // 数字8对应的字母umap[9] {w, x, y, z}; // 数字9对应的字母}void backtracking(const string digits, int index) {// 如果当前组合的长度等于输入数字的长度将当前组合添加到结果中if (index digits.size()) {paths.push_back(path);return;}// 将当前处理的数字转换为对应的映射表中的字母int digit digits[index] - 0; // 遍历映射表中的字母进行回溯for (int i 0; i umap[digit].size(); i) {path.push_back(umap[digit][i]); // 添加字母到当前组合backtracking(digits, index 1); // 处理下一个数字path.pop_back();}}vectorstring letterCombinations(string digits) {//输入为空直接返回空的结果if (digits.empty()) {return paths;}backtracking(digits, 0);return paths;}
};算法的时间复杂度参考在最坏情况下每个数字对应最多4个字母若输入数字的长度为n则最坏情况下时间复杂度为O(4^n)因为每一步都有4种选择。代码随想录上是将3个字母和4个字母都区分了出来所以是O(3^m*4^n)
空间复杂度由两部分组成一是递归的栈空间二是存储结果的空间栈空间最坏情况下与输入数字长度n成正比O(n)。存储空间取决于可能的组合数量最坏情况下为O(4^n)总的空间复杂度为Om4^n。
