Day28 17电话号码的字母组合 39组合求和 40组合求和II

这篇具有很好参考价值的文章主要介绍了Day28 17电话号码的字母组合 39组合求和 40组合求和II。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

17 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

Day28 17电话号码的字母组合 39组合求和 40组合求和II,算法

         因为输入的数字的数量是不确定的,所以for循环的次数也是不确定的,这里就需要用到回溯的方法了。Day28 17电话号码的字母组合 39组合求和 40组合求和II,算法

         一般回溯里面,递归都是深度,for循环都是宽度。注意本题的index和之前两道题的index不太一样,因为本题不是从同一个集合里面取,而是从多个集合里面取。同时for循环的起始位置是0,因为此时不存在从同一个集合里面取相同的数的问题了。

class Solution {
private:
    //记录对应的关系
    const string letterMap[10] = {
        " ",
        " ",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",
    };
    vector<string> result; //存放结果
    string s; //存放字符串
    void backtracking(string digits, int index) {
        if(index == digits.size()) { //index表示的是第几个数字,数字等于数字大小就停止
            result.push_back(s);
            return;
        }
        int digit = digits[index]-'0'; //将index转换为“23”里的数字
        string letters = letterMap[digit]; //根据数字在哈希表里面找字符串
        for(int i = 0; i < letters.size(); i++) {
            s.push_back(letters[i]); //处理
            backtracking(digits,index+1); //递归
            s.pop_back(); //回溯
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        result.clear();
        if(digits.size()==0) return result; //特殊处理以下等于0的时候
        backtracking(digits, 0);
        return result;
    }
};

        本题也可以将回溯隐含在函数中,但是不建议这么写,不直观。

// 版本二
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;
    void getCombinations(const string& digits, int index, const string& s) { // 注意参数的不同
        if (index == digits.size()) {
            result.push_back(s);
            return;
        }
        int digit = digits[index] - '0';
        string letters = letterMap[digit];
        for (int i = 0; i < letters.size(); i++) {
            getCombinations(digits, index + 1, s + letters[i]);  // 注意这里的不同
        }
    }
    vector<string> letterCombinations(string digits) {
        result.clear();
        if (digits.size() == 0) {
            return result;
        }
        getCombinations(digits, 0, "");
        return result;

    }
};

 39 组合求和

给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

  • 所有数字(包括 target)都是正整数。
  • 解集不能包含重复的组合。

 这道题与之前那题的不同之处在于数字是题目给的,并且可以重复,总的来说都差不多。

 注意因为可以重复,所以递归函数里不用i+1而直接是i

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int startIndex) {
        if(target < 0) return;
        if(target == 0) {
            result.push_back(path);
            return;
        }
        for(int i = startIndex; i < candidates.size(); i++) {
            path.push_back(candidates[i]);
            target -= candidates[i];
            backtracking(candidates, target, i); //这里不需要i+1了因为可以重复的取
            target += candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        backtracking(candidates, target, 0);
        return result;
    }
};

         这里可以进行剪枝操作,对这个数组排完序以后,如果前面的比target大了,那么后面也就不用看了:

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int startIndex) {
        if(target < 0) return;
        if(target == 0) {
            result.push_back(path);
            return;
        }
        for(int i = startIndex; i < candidates.size() && (target-candidates[i])>=0; i++) {
            path.push_back(candidates[i]);
            target -= candidates[i];
            backtracking(candidates, target, i); //这里不需要i+1了因为可以重复的取
            target += candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        sort(candidates.begin(), candidates.end()); // 需要排序
        backtracking(candidates, target, 0);
        return result;
    }
};

 40 组合求和II

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明: 所有数字(包括目标数)都是正整数。解集不能包含重复的组合。

本题与上一题的不同之处就是给的数组里面有重复的元素,导致后面可能重复利用这个元素,但是还不能有重复的组合。Day28 17电话号码的字母组合 39组合求和 40组合求和II,算法

         这里利用一个used数组,里面存放布尔型数据,如果是1就说明这个数用过。首先对题目给的数组进行排序,去重有两种形式:树层去重和树枝去重,显而易见,我们不需要数值去重,但是需要树层去重,如果此时遍历的元素和上一个相同,并且上一个元素没有被使用过(如果使用过的话说明是树枝去重了,没有回溯的话used就不会重新被置为false),此时证明正在访问的元素是回溯以后的,并不是树枝,所以直接跳过就好了。文章来源地址https://www.toymoban.com/news/detail-794886.html

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int startIndex, vector<bool> used) {
        if(target < 0) return;
        if(target == 0) {
            result.push_back(path);
            return;
        }
        for(int i = startIndex; i < candidates.size()&&(target-candidates[i])>=0; i++) {
            if(i>0 && candidates[i]==candidates[i-1] && used[i-1] == false) continue;
            path.push_back(candidates[i]);
            target -= candidates[i];
            used[i] = true;
            backtracking(candidates, target, i+1, used); 
            used[i] = false;
            target += candidates[i];
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        vector<bool> used(candidates.size(), false);
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, used);
        return result;
    }
};

到了这里,关于Day28 17电话号码的字母组合 39组合求和 40组合求和II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode 17. 电话号码的字母组合

             该题也是经典回溯题。 与之前做的组合有两点不同: 之前的组合题是求同一集合的组合,而本题是求不同集合的组合。 本题还需要有一个将字符串数字转换为手机号9键对应字符集的过程。         下面上代码:         如果面试中的话要注意判断异常输入的情

    2024年02月16日
    浏览(41)
  • Leetcode 17 电话号码的字母组合

    理解题意 :         给定一个仅包含数字  2-9  的字符串,返回所有它能表示的字母组合                 本质上:数字代表着一个字母集合                 数字的个数决定了递归的深度,即树的深度                 数字代表的字母组合决定了当前树的宽度

    2024年02月05日
    浏览(40)
  • 17.电话号码的字母组合(深度递归遍历解决经典老题)

    C++深度递归遍历解决\\\"电话号码的字母组合问题\\\",本题考察的比较全面,考察到 vector的使用,深度遍历以及递归的熟练度 ,希望能对铁子们有所帮助 链接:https://leetcode.cn/problems/letter-combinations-of-a-phone-number/ 如上图所示,以\\\"256\\\"为例,我们将三个字符串各个字符的排列组合展

    2023年04月13日
    浏览(41)
  • 代码随想录22| 216.组合总和III, 17.电话号码的字母组合

    题目链接/文章讲解:链接地址 视频讲解:链接地址 代码思路:回溯三部曲: 1.确定函数参数:n,k,sum,startIndex; 2.结束条件,path == k,并且如果sum==n 结束递归 3.递归回溯逻辑。 题目链接/文章讲解:链接地址 视频讲解:链接地址 代码思路:传入参数:输入的数字,第几个数字的

    2024年02月11日
    浏览(52)
  • 稀碎从零算法笔记Day45-LeetCode:电话号码的字母组合

    题型:映射、回溯算法、递归 链接:17. 电话号码的字母组合 - 力扣(LeetCode) 来源:LeetCode 给定一个仅包含数字  2-9  的字符串,返回所有它能表示的字母组合。答案可以按  任意顺序  返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例

    2024年04月11日
    浏览(39)
  • 电话号码的字母组合-算法

    按电话上数字与字母的对应关系,如2={a,b,c},3={d,e,f}等,给定一串数字如267,则求出abc,mno,qprs的所有组合,如amq,amp...cor,cos等 遍历都可以用回溯的方式尝试解决,每次遍历结束后,将上一层元素删除,满足长度,则加入到结果中      

    2024年01月22日
    浏览(40)
  • leetcode:电话号码的字母组合(详解)

    给定一个仅包含数字  2-9  的字符串,返回所有它能表示的字母组合。答案可以按  任意顺序  返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例 1: 示例 2: 示例 3: 提示: 0 = digits.length = 4 digits[i]  是范围  [\\\'2\\\', \\\'9\\\']  的一个数字。  

    2024年02月11日
    浏览(57)
  • 【leetcode C++】电话号码的字母组合

    给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。     . - 力扣(LeetCode) 这道题明显是需要互相匹配,如 字符串 “23”, 对应 “abc” 和 “def”。 这个

    2024年03月10日
    浏览(43)
  • 【算法Hot100系列】电话号码的字母组合

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年02月01日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包