当前位置：首页 > article >正文

LeetCode热题100JS（59/100）第十一天|46|78|17|39|22

article 2025/3/22 12:41:15

46. 全排列

题目链接：46. 全排列

难度：中等

刷题状态：2刷

新知识：

解题过程

思考

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]

题解分析

参考题解链接：全排列

放下1刷过程

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// var permute = function(nums) {
//     let res=[],path=[],n=nums.length
//     //used数组跟踪那些数字被用过
//     let used=new Array(n).fill(false)
//     function dfs(start,nums){
//         if(path.length==n){
//             res.push([...path])
//             return 
//         }
//         //这里要从0开始
//         for(let i=0;i<n;i++){
//             if(!used[i]){
//                 //没用过
//                 path.push(nums[i])
//                 //标记一下
//                 used[i]=true
//                 dfs(start+1,nums)
//                 path.pop()
//                 used[i]=false
//             }
//         }
//     }
//     dfs(0,nums)
//     return res
// };

var permute = function(nums) {
    let res=[],path=[],n=nums.length
    let used=new Array(n).fill(false)
    function dfs(start){
        if(path.length==n){
            res.push([...path])
            return 
        }
        for(let i=0;i<n;i++){
            if(!used[i]){
                path.push(nums[i])
                used[i]=true
                dfs(start+1)
                path.pop()
                used[i]=false
            }
        }
    }
    dfs(0)
    return res
}

手搓答案（无非废话版）

 /**
 * @param {number[]} nums 
 * @return {number[][]}  
 */
 var permute=function(nums){
    let res=[],path=[],n=nums.length
    let used=new Array(n).fill(false)
    function dfs(start){
        if(path.length==n){
            res.push([...path])
            return 
        }
        for(let i=0;i<n;i++){
            if(!used[i]){
                path.push(nums[i])
                used[i]=true
                dfs(start+1)
                path.pop()
                used[i]=false
            }
        }
    }
    dfs(0)
    return res
 }

总结

回溯类型的题

78. 子集

题目链接：78. 子集

难度：中等

刷题状态：2刷

新知识：

解题过程

思考

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

题解分析

参考题解链接：子集

放下1刷过程

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// var subsets = function(nums) {
//     let res=[]
//     let n=nums.length
//     for(let mask=0;mask<(1<<n);mask++){
//         let t=[]
//         for(let i=0;i<n;i++){
//             //使用了位运算的按位与操作&来检查mask的第i位是否为1
//             if(mask&(1<<i)){
//                 t.push(nums[i])
//             }
//         }
//         res.push(t)
//     }
//     return res
// };
var subsets = function (nums) {
    let ans = [], n = nums.length;
    generate(0, []);
    return ans;

    function generate(start, now) {
        if (start == n) { ans.push(now.concat()); return; }
        generate(start + 1, now);
        now.push(nums[start]);
        generate(start + 1, now);
        now.pop()
    }
};

手搓答案（无非废话版）

/**
 * @param {number[]} nums 
 * @return {number[][]} 
 */
 var subsets=function(nums){
    let res=[],n=nums.length
    function dfs(start,now){
        if(start==n) {
            res.push([...now])
            return 
        }
        dfs(start+1,now)
        now.push(nums[start])
        dfs(start+1,now)
        now.pop()
    }
    dfs(0,[])
    return res
 }

总结

从大到小存

17. 电话号码的字母组合

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

难度：中等

刷题状态：2刷

新知识：

解题过程

思考

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

没思路，看答案

题解分析

参考题解链接：电话号码的字母组合

放下1刷过程

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    if(!digits) return []
    let len=digits.length
    let map=['','',"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    let res=[]
    let path=[]
    function backTrace(idx){
        if(idx==len){
            if(path.length){
                // console.log('path',path)
                res.push(path.join(''))
            }
            return 
        }
        for(let ch of map[digits[idx]]){
            path.push(ch)
            backTrace(idx+1)
            path.pop()
        }
    }
    backTrace(0)
    // console.log('res',res)
    return res
};

手搓答案（无非废话版）

/**
 * @param {string} digits
 * @return {string[]}
 */

 var letterCombinations=function(digits){
    let map=['','',"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    let res=[],path=[],n=digits.length
    function dfs(start){
        if(start==n){
            if(path.length) res.push(path.join(''))
            return 
        }
        for(let char of map[digits[start]]){
            path.push(char)
            dfs(start+1)
            path.pop()
        }
    }
    dfs(0)

    return res
 }

总结

回溯类型的题

39. 组合总和

题目链接：39. 组合总和

难度：中等

刷题状态：2刷

新知识：

解题过程

思考

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

题解分析

参考题解链接：组合总和

放下1刷过程

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    let res=[], path=[]
    function dfs(start,sum,can,target){
        if(sum==target){
            res.push([...path])
            return 
        }
        if(sum>target) return 
        for(let i=start;i<can.length;i++){
            path.push(can[i])
            dfs(i,sum+can[i],can,target)
            path.pop()
        }
    }
    dfs(0,0,candidates,target)
    return res
};

手搓答案（无非废话版）

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */

 var combinationSum=function(candidates,target){
    let res=[],path=[],n=candidates.length
    function dfs(start,sum){
        if(sum==target){
            res.push([...path])
            return
        }
        if(sum>target) return 
        for(let i=start;i<n;i++){
            path.push(candidates[i])
            dfs(i,sum+candidates[i])
            path.pop()
        }
    }
    dfs(0,0)
    return res
 }

总结

注意回溯里面的dfs(i,)这里传进去的是i，可以有重复的数字，如果不能有重复的数字就是i+1

22. 括号生成

题目链接：22. 括号生成

难度：中等

刷题状态：2刷

新知识：

解题过程

思考

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

题解分析

参考题解链接：括号生成

放下1刷过程

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    let res=[]
//left是'('个数，right是')'个数
    function backtrack(s,left,right){
        if(s.length==n*2){
            res.push(s)
            return 
        }
        if(left<n){
            backtrack(s+"(",left+1,right)
        }
        if(right<left){
            backtrack(s+")",left,right+1)
        }
    }
    backtrack('',0,0)
    return res
};

手搓答案（无非废话版）

/**
 * @param {number} n
 * @return {number[]}
 */
 var generateParenthesis=function(n){
    let res=[],s=''
    function dfs(s,left,right){
        if(s.length==n*2){
            res.push(s)
            return 
        }
        if(left<n) dfs(s+'(',left+1,right)
        if(right<left) dfs(s+')',left,right+1)
    }
    dfs(s,0,0)
    return res
 }