代码随想录算法训练营第二十五天 | 216.组合总和III、17.电话号码的字母组合

发布时间:2024年01月21日

题目链接:leetcode 17.电话号码的字母组合

文章讲解:代码随想录 17.电话号码的字母组合讲解

视频讲解:还得用回溯算法!| LeetCode:17.电话号码的字母组合

思路和解法

题目:
找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:

只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。
想法:
感觉最近刷题质量细下降了,花的时间也不够多,确实自己写了一遍代码,但是总会写出bug,自己还查不出来,需要gpt协助。后面每天的题目必须都自己写熟练,多思考。另外bug总出在小细节上,尤其是一些C++语法的使用上。

今天这道题目,第一个错误就是剪枝条件一开始加错了,所以递归回溯一开始还是不要想着剪枝。第二个bug是终止条件想复杂了,其实就判断path的长度以及是否满足想要的东西就行了,其他情况怎么递归都无所谓,因为不会加入result。剪枝确实还是不要太好想。而且剪枝似乎有很多可以优化的地方,不能全部都想全,只能把最显而易见的剪枝考虑到,否则可能判断的太多反而不好吧。

class Solution {
public:
    vector<int> path;
    vector<vector<int>> result;
    //记录路径之和
    int sum;
    //递归函数
    void backTracking(int k, int n, int startIndex) {
        if (path.size() == k && sum == n) {
            result.push_back(path);
            return ;
        }
        //递归处理
        for (int i = startIndex; i <= 9; i++) {
            //剪枝条件
            if (n - sum < i) {
                break;
            }
            path.push_back(i);
            sum += i;
            backTracking(k, n, i + 1);
            sum -= i;
            path.pop_back();
        }
        return ;
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backTracking(k, n, 1);
        return result;
    }
};

题目链接:leetcode 216.组合总和III

文章讲解:代码随想录 216.组合总和III讲解

视频讲解:和组合问题有啥区别?回溯算法如何剪枝?| LeetCode:216.组合总和III

思路和解法

题目:
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
想法:
感觉最近刷题质量细下降了,花的时间也不够多,确实自己写了一遍代码,但是总会写出bug,自己还查不出来,需要gpt协助。后面每天的题目必须都自己写熟练,多思考。另外bug总出在小细节上,尤其是一些C++语法的使用上。

今天这道题目,第一个错误就是剪枝条件一开始加错了,所以递归回溯一开始还是不要想着剪枝。第二个bug是终止条件想复杂了,其实就判断path的长度以及是否满足想要的东西就行了,其他情况怎么递归都无所谓,因为不会加入result。剪枝确实还是不要太好想。而且剪枝似乎有很多可以优化的地方,不能全部都想全。

class Solution {
public:
    //表格
    const string letterMap[10] = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    string path;
    vector<string> result;
    //递归函数
    void backTrack(string digits, int index) {
        //终止条件
        if (path.size() == digits.size()) {
            result.push_back(path);
            return ;
        }
        //递归处理过程
        string s = letterMap[digits[index] - '0'];
        for (int i = 0; i < s.size(); i++) {
            path.push_back(s[i]);
            backTrack(digits, index + 1);
            path.pop_back();
        }
        return ;
    }

    vector<string> letterCombinations(string digits) {
        path.clear();
        result.clear();
        if (digits.size() == 0) {
            return result;
        }
        backTrack(digits, 0);
        return result;
    }
};
文章来源:https://blog.csdn.net/Tong_1024_/article/details/135726531
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。