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

阿选不出来 2023-04-19 原文

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

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

1.电话号码的字母组合

题目:

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

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

思路:

首先创建一个数字与字母相照应的对象(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
}

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

题解 JavaScript span class token leetcode 开发语言

有关【LeetCode】JavaScript题解:电话号码的字母组合|组合总和Ⅲ的更多相关文章

ruby-on-rails - 使用一系列等级计算字母等级 - 2
这里是Ruby新手。完成一些练习后碰壁了。练习:计算一系列成绩的字母等级创建一个方法get_grade来接受测试分数数组。数组中的每个分数应介于0和100之间，其中100是最大分数。计算平均分并将字母等级作为字符串返回，即“A”、“B”、“C”、“D”、“E”或“F”。我一直返回错误:avg.rb:1:syntaxerror,unexpectedtLBRACK,expecting')'defget_grade([100,90,80])^avg.rb:1:syntaxerror,unexpected')',expecting$end这是我目前所拥有的。我想坚持使用下面的方法或.join，
ruby - 匹配大写字母并用后续字母填充，直到一定的字符串长度 - 2
我有一个驼峰式字符串，例如:JustAString。我想按照以下规则形成长度为4的字符串:抓取所有大写字母；如果超过4个大写字母，只保留前4个；如果少于4个大写字母，则将最后大写字母后的字母大写并添加字母，直到长度变为4。以下是可能发生的3种情况:ThisIsMyString将产生TIMS(大写字母)；ThisIsOneVeryLongString将产生TIOV(前4个大写字母)；MyString将生成MSTR(大写字母+tr大写)。我设法用这个片段解决了前两种情况:str.scan(/[A-Z]/).first(4).join但是，我不太确定如何最好地修改上面的代码片段以处理最后一种
ruby - 正则表达式将非英文字母匹配为非单词字符 - 2
@raw_array[i]=~/[\W]/非常简单的正则表达式。当我用一些非拉丁字母(具体来说是俄语)尝试时，条件是错误的。我能用它做什么？最佳答案 @raw_array[i]=~/[\p{L}]/使用西里尔字符进行测试。引用:http://www.regular-expressions.info/unicode.html#prop 关于ruby-正则表达式将非英文字母匹配为非单词字符，我们在StackOverflow上找到一个类似的问题： https://
Python 刷Leetcode题库，顺带学英语单词（31） - 2
ValidPalindromeGivenastring,determineifitisapalindrome,consideringonlyalphanumericcharactersandignoringcases. [#125]Example:"Aman,aplan,acanal:Panama"isapalindrome."raceacar"isnotapalindrome.Haveyouconsiderthatthestringmightbeempty?Thisisagoodquestiontoaskduringaninterview.Forthepurposeofthisproblem
ruby-on-rails - 使用 javascript 更改数据方法不会更改 ajax 调用用户的什么方法？ - 2
我遇到了一个非常奇怪的问题，我很难解决。在我看来，我有一个与data-remote="true"和data-method="delete"的链接。当我单击该链接时，我可以看到对我的Rails服务器的DELETE请求。返回的JS代码会更改此链接的属性，其中包括href和data-method。再次单击此链接后，我的服务器收到了对新href的请求，但使用的是旧的data-method，即使我已将其从DELETE到POST(它仍然发送一个DELETE请求)。但是，如果我刷新页面，HTML与"new"HTML相同(随返回的JS发生变化)，但它实际上发送了正确的请求类型。这就是这个问题令我困惑的
ruby - 最多 n 的组合 - 2
给定一个数组a，什么是实现其组合直到第n的最佳方法？例如:a=%i[abc]n=2#Expected=>[[],[:a],[:b],[:c],[:a,b],[:b,:c],[:c,:a]] 最佳答案做如下:a=%w[abc]n=30.upto(n).flat_map{|i|a.combination(i).to_a}#=>[[],["a"],["b"],["c"],["a","b"],#["a","c"],["b","c"],["a","b","c"]] 关于ruby-最多n的组合，我
ruby-on-rails - 我如何告诉 Rails 如何正确地大写首字母缩写词？ - 2
我的一个模型中有一个名为sui的字段。它代表“标准用户标识符”。当该字段出现验证错误时，Rails会打印“Suiisrequired”或“Suiisalreadytaken”。如何告诉Rails'sui'.titleize是“SUI”？我查看了Inflector.human，但这并不完全正确。最佳答案在这种情况下，我使用custom_err_msg插入。安装后，您可以提供如下自定义错误消息:validates_presence_of:sui,:message=>'^SUIisrequired'当您将^放在开头时，Rails不会输
ruby - 按数字(从大到大)然后按字母(字母顺序)对对象集合进行排序 - 2
我正在构建一个小部件来显示奥运会的奖牌数。我有一个“国家”对象的集合，其中每个对象都有一个“名称”属性，以及奖牌计数的“金”、“银”、“铜”。列表应该排序:1.首先是奖牌总数2.如果奖牌相同，按类型分割(金>银>铜，即2金>1金+1银)3.如果奖牌和类型相同，则按字母顺序子排序我正在用ruby做这件事，但我想语言并不重要。我确实找到了一个解决方案，但如果感觉必须有更优雅的方法来实现它。这是我做的:使用加权奖牌总数创建一个虚拟属性。因此，如果他们有2个金牌和1个银牌，加权总数将为“3.020100”。1金1银1铜为“3.010101”由于我们希望将奖牌数排序为最高的，因此列表按降序排
ruby-on-rails - Rails 格式验证——字母数字，但不是纯数字 - 2
什么是测试格式验证的最佳方法让我们说一个用户名，使用字母数字的正则表达式，但不是纯数字？我一直在我的模型中使用以下验证validates:username,:format=>{:with=>/^[a-z0-9]+[-a-z0-9]*[a-z0-9]+$/i}数字用户名(例如“342”)通过了验证，这是我不想要的。最佳答案您想“向前看”一封信:/\A(?=.*[a-z])[a-z\d]+\Z/i 关于ruby-on-rails-Rails格式验证——字母数字，但不是纯数字，我们在Sta
ruby - Rails 组合多个 activerecord 关系 - 2
我想合并多个事件记录关系例如，apple_companies=Company.where("namelike?","%apple%")banana_companies=Company.where("namelike?","%banana%")我想结合这两个关系。不是合并，合并是apple_companies.merge(banana_companies)=>Company.where("namelike?andnamelike?","%apple%","%banana%")我要Company.where("名字像？还是名字像？","%apple%","%banana%")之后，我会写代

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