【LeetCode】JavaScript题解:电话号码的字母组合|组合总和Ⅲ

秒速五厘米 2024-03-25 10:03 21阅读 0赞

#### 【LeetCode】JavaScript题解:电话号码的字母组合|组合总和Ⅲ ####

*   *  1.电话号码的字母组合
     *  2.组合总和Ⅲ

### 1.电话号码的字母组合 ###

**题目:**

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

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

![在这里插入图片描述][37b0ba100f544ded86c07ce7566f19ed.png_pic_center]

**思路:**

首先创建一个数字与字母相照应的对象(list)

其次这道题我用到了递归思想，

递归函数的第一个参数表示 当前的字母排列（即每一次遍历电话号码所得到的字符串）

*  该参数初始值为空，每次取一个电话号码，就从list对象中获得与该号码对应的所有字母，从中取一个拼接到当前参数字符串末尾，继续处理下一位号码，直到处理完所有电话号码。

第二个参数表示 还未遍历的电话号码

**代码部分：**

var letterCombinations = function(digits) {
        
        let newarr = []
    
        const list = {
        
            "2":['a','b','c'],
            "3":['d','e','f'],
            "4":['g','h','i'],
            "5":['j','k','l'],
            "6":['m','n','o'],
            "7":['p','q','r','s'],
            "8":['t','u','v'],
            "9":['w','x','y','z']
        }
    
        if (digits === '') return newarr
        
        const backtrack = (str,next_d)=>{
        
            if(next_d.length === 0){
        
                newarr.push(str)
            }else{
        
                for(i in list[next_d[0]]){
        
                    let letter = list[next_d[0]][i]
                    backtrack(str+letter,next_d.substring(1))
                }
            }
        }
    
        backtrack('',digits)
    
        return newarr
    
    };

### 2.组合总和Ⅲ ###

**题目要求：**

找出所有相加之和为 `n` 的 `k` 个数的组合，且满足下列条件：

*  只使用数字1到9
 *  每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

**思路：**

*  > 组合可以以任何顺序返回，即 `[1,2,3]` `[2,1,3]` 只需要返回其中一种即可。

首先我们需要定义一个变量 `arr_2`表示所有可能的有效组合的集合数组，定义一个变量 `arr` 表示可能的有效组合。

因为 1<n<9 ，我们可能会想到用for循环1到9，需要 `k`个数就嵌套`k`层循环，每层循环都循环1-9，找出所有相加为n的可能组合，由于k的不确定性，很难使用嵌套for循环求出结果，这个时候就需要用到递归了。

*  又因为返回的数字组合元素不分次序，在递归体中，如果每次都从范围1-9中取出一个数字，便会出现许多元素相同，排序不同的数组，为了防止这种情况的发生，就需要定义一个变量 `startindex`，在初次递归时，startindex的值为1，数字可取的范围为1-9即startindex-9,假设取出值为i 那么下次递归中startindex的值为i+1，每次可取范围的最小值都是上一次取值结果的+1，避免取出相同的数字也避免了所求的可能的数字组合中元素相同，排序不同的情况。

在递归函数中，每取出一个数字，就记录到 `arr`的数组中，直到剩下最后一个数字要取时，此时求出当前数字队列总和与所需总和n的差值，如果差值介于\[startindex,9\]之间就把差值加入arr队列，并记录到 `arr_2`数组中。

第一个参数n表示 当前数字组合的总和与所需总和的差值

第二个参数k表示 当前数字组合还需的数字个数

第三个参数 startindex表示数字所取范围的最小值

> 注：在每一轮的递归之后都要arr.pop弹出最后一个数值，为下一次循环做准备。

**代码部分：**

combinationSum3_1 = (k,n)=>{
        
        let arr_2=[] //二维数组
        let arr=[] //一维数组
        numback = (n,k,startindex)=>{
        
            if(k==1){
        
                if(n>=startindex && n<=9){
        
                    arr_2.push([...arr,n])
                }
            }else{
        
                for(let i = startindex; i <= 9; i++){
        
                    arr.push(i)
                    numback(n-i,k-1,i+1)
                    arr.pop()
                }
            }
        }
        numback(n,k,1)
        return arr_2
    }

注:有错误的地方可以在评论区留言,我会虚心改正的

[37b0ba100f544ded86c07ce7566f19ed.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c938fc99585f4e48b33d0640ccea5ce0.png