JLUVicent

17电话号码的字母组合&216组合总和III

 
  • 2023年 03月11日
  • 0 阅读

day25

216.组合总和III

题目链接：216. 组合总和 III

解题思路：参考 视频

与组合的方法一样，使用回溯，就是有个限制条件就是sum的加入

  • 第一种方法：不加入剪枝操作，直接递归
  • 第二种方法：加入剪枝，将sum加入整个递归过程中，for循环的判断条件要注意
// 我的思路：没有加入剪枝，这块剪枝就溢出
class Solution {
public:

    vector<int> path;
    vector<vector<int>> result;
    void backtracking( int k,int n,int startIndex){
        // 终止条件
        int sum = 0;
        if( path.size() == k ){
            for ( int i = 0; i < k; i++){
                sum+= path[i];
            }
            if( sum == n ){
                result.push_back(path);
                return;
            }
        }
        // 单层逻辑
        for ( int i = startIndex; i <= 9; i++){
            path.push_back( i );
            backtracking( k , n , i + 1 );
            path.pop_back();
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        int i = 1;
        backtracking( k , n , i );
        return result;
    }
};


// 第二种
class Solution {
public:

    vector<int> path;
    vector<vector<int>> result;
    // void backtracking( int k,int n,int startIndex){
    //     // 终止条件
    //     int sum = 0;
    //     if( path.size() == k ){
    //         for ( int i = 0; i < k; i++){
    //             sum+= path[i];
    //         }
    //         if( sum == n ){
    //             result.push_back(path);
    //             return;
    //         }
    //     }
    //     // 单层逻辑
    //     for ( int i = startIndex; i <= 9; i++){
    //         path.push_back( i );
    //         backtracking( k , n , i + 1 );
    //         path.pop_back();
    //     }
    // }

    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);
            }
        }
        //单层逻辑
        for( int i = startIndex; i <= 9 - ( k - path.size()) + 1; i++){
            sum +=i;    //给sum赋值
            path.push_back(i);  //保存结果
            backtracking ( k , n, sum , i+1 );
            path.pop_back(); //回溯
            sum-=i; //回溯
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        int i = 1;
        int sum= 0 ;
        backtracking( k , n ,sum ,i );
        return result;
    }
};

17.电话号码的字母组合

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

解题思路：参考 视频

  • 用二维数组做数字到字母的映射

    const string letterMap[10] = {
    "", // 0
    "", // 1
    "abc", // 2
    "def", // 3
    "ghi", // 4
    "jkl", // 5
    "mno", // 6
    "pqrs", // 7
    "tuv", // 8
    "wxyz", // 9
};

  • 回溯法解决n个for循环的问题

17. 电话号码的字母组合

  • 定义结果数组，定义存储字符串s，之后就是回溯三部曲：确定递归函数的参数和返回值，确定终止条件，确定单层递归逻辑
class Solution {
public:

    // 定义全局变量 letterMap 数组作为哈希映射
    const string letterMap[10] = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",
    };

    // 定义全局变量存储结果
    string s;   //存储每个结果
    vector<string> result;  //存储最终结果
    void backTracking( const string digits, int index){
        // 终止条件 索引要等于数组大小，如果等于size()-1的时候下面还要继续执行
        if ( index == digits.size() ){
            result.push_back(s);    //收集结果
            return ;
        }
        // 将字符串转换为整数
        int digit = digits[index] - '0';
        // 将digit映射到letterMap中
        string letter = letterMap[digit];
        // 单层递归逻辑
        for( int i = 0; i < letter.size(); i++){
            s.push_back(letter[i]);
            backTracking( digits, index+1);
            s.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        if( digits == "") return {};
        int index = 0;
        backTracking( digits,index);
        return result;
    }
};
搜索