leetcode 解题

leetcode

边读《labuladong的算法⼩抄》，边leetcode找几个题目练习

  1. 二叉树的中序遍历【94】 连接
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let result= []
    function _traverse(treeNode) {
        if(!treeNode) {
            return
        }
        _traverse(treeNode.left)
         result.push(treeNode.val)
        _traverse(treeNode.right)
        
    }
   _traverse(root)
    return result
};

  1. 全排列【46】 连接 (视频参考)[https://www.bilibili.com/video/BV1P5411N7Xc/?spm_id_from=333.337.search-card.all.click]

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    /**
     * @param {number[]} nums
     * @return {number[][]}
     */
    var permute = function(nums) {
        var res=[]
        let _backtack=function(nums,track) {
            // 触发结束条件
            if(track.length ==nums.length) {
                res.push([...track])  
            }
         // 遍历节点    
            for(let i=0;i<nums.length;i++) {
               if(track.includes(nums[i])) {
                   continue
               }
               
                track.push(nums[i])
                // 递归查询
                _backtack(nums,track)
                
               // 撤销选择，将该选择加入选择列表   
                track.pop()
            }
        }
      
        _backtack(nums,[])
        return res
    };

  2. N 皇后【51】 连接

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54

    function isValid(trace,row,col) {
        // 检查当前位置是否可以放置皇后
        for (let i = 0; i < row; i++) {
            if (trace[i][col] == "Q") {
                return false;
            }
        }
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (trace[i][j] == "Q") {
                return false;
            }
        }
        for (let i = row - 1, j = col + 1; i >= 0 && j < trace.length; i--, j++) {
            if (trace[i][j] == "Q") {
                return false;
            }
        }
        return true;
    }
    /**
     * @param {number} n
     * @return {string[][]}
     */
     
    var solveNQueens = function(n) {
     // 生成N*N的处理方式
     
      let result = []
      let trace = []  // 已经放置的数据
      for(let j=0;j<n;j++) {
          a= new Array(n).fill('.')
          trace.push(a)
      }
      console.log(trace)
      function backtrace (trace,row ) {
        if(row== trace.length) {
            result.push(trace.map(x=>x.join('')))
            return
        }
        for(let i=0;i<n;i++) {
            // 遍历了列
            if(!isValid(trace,row,i)) {
                continue
            }
            console.log(`遍历行${row},列${i}`)
            trace[row][i] ='Q'
            backtrace(trace,row+1)
            trace[row][i] = '.'; 
        }
        return result
      }
       return backtrace(trace,0)
    };

  3. 二分查找 连接

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    function search( nums ,  target ) {
        console.log(nums)
        
        var left =0
        var right =nums.length-1
        while(left<=right) {
            var mid =Math.floor( left+ (right-left)/2)
            if(nums[mid]==target) {
                return mid
            } 
            else if(nums[mid]<target) {
                left=mid+1
            }
            else if(nums[mid]>target) {
                right=mid-1
            }
        }
        return -1;
    }

    // 扩展到二分靠左查询
    var a = [1,4,5,6,7,7,7,7,7,7,8,10,12]
     function findI(arr,val){
        let left = 0;
        let right= arr.length-1;
        while(left<=right) {
            console.log(`范围${left},${right}`)
            let mid =Math.floor(left+(right-left)/2)
            if(a[mid]>val) {
                right=mid-1
            } else if(a[mid]==val){
               right=mid-1
            } else if(a[mid]<val) {
                left=mid+1
            }
        }
        // 找不到场景
        if (left==arr.length) return -1;
        return arr[left] == val ? left : -1;
     }
     console.log(findI(a,7))

    // 扩展到二分靠右查询
    var a = [1,4,5,6,7,7,7,7,7,7,8,10,12]
     function findI(arr,val){
        let left = 0;
        let right= arr.length-1;
        while(left<=right) {
            console.log(`范围${left},${right}`)
            let mid =Math.floor(left+(right-left)/2)
            if(a[mid]>val) {
                right=mid-1
            } else if(a[mid]==val){
               left=mid+1
            } else if(a[mid]<val) {
                left=mid+1
            }
        }
        // 找不到场景
        if (right <0) return -1;
        return arr[right] == val ? right : -1;
     }
     console.log(findI(a,7))

  4. 最小覆盖子串 连接

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    /**
     * @param {string} s1
     * @param {string} s2
     实际是右指针增加 左指针删除
     * @return {boolean}
     */
    var checkInclusion = function(s1, s2) {
    // 双指针解法
     var left=0
     var right=0
     var valid=0
     var windowStrMap={} // 记录窗口字符出现次数
     var targetStrMap ={} // 记录目标字符出现次数map
     s1.split('').forEach(x=> {
        targetStrMap[x]=targetStrMap[x]||0
        targetStrMap[x]++
     })
        var s2Arr=s2.split('')
        while(right<s2.length){
            let c =s2[right]
            
            console.log("窗口扩大right", right,targetStrMap[c])
            if(targetStrMap[c]!=undefined) {
                windowStrMap[c]=  windowStrMap[c]||0
                windowStrMap[c]++

                console.log(windowStrMap[c],"目标",targetStrMap[c] )
                if(windowStrMap[c]===targetStrMap[c]) {
                    valid++
                    console.log("校验数目增加"+valid)
                }
            }
            right++
            while((right-left)>=s1.length){
                console.log("验证数目："+ valid + "需要验证数目"+Object.keys(targetStrMap).length )
                console.log("窗口缩小前left", left)
                if(valid==Object.keys(targetStrMap).length) {
                    return true
                }
                let d= s2[left]
                left++
                console.log("窗口缩小后left", left)
                if(targetStrMap[d]!=undefined) {
                   windowStrMap[c]=  windowStrMap[c]||0
                    if(windowStrMap[d]===targetStrMap[d]) {
                        valid--
                    }
                     windowStrMap[d]--
                    
                }
            }    
        }
        return false
    };

  5. 二叉树的最小深度 连接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 第一种解法递归的解法
var minDepth = function(root) {
    if(!root) {
        return 0
    }
    if(root.left==null && root.right==null) {
        return 1
    }
    if(root.left!=null)
        return minDepth(root.left)+1;
    if(root.right!=null)
        return minDepth(root.right)+1;
    
    if(root.left!=null && root.right!=null) {
        return Math.min(minDepth(root.left),minDepth(root.right))+1;
    }
};

//第二中BFS

var minDepth = function(root) {
  // 队列里面 先放进去，
   var q=[] // 模拟一个队列
   let depth=1
   q.push(root)
   while (q.length>0) {
       // 每一次循环把下一层的树节点push进去
      let length = q.length  // 这个地方得缓存这个length  因为	unshift在不停更改数组 就因为这个bug
       for(let i=0;i<length;i++) {
           item= q.shift()
           if(item&& item.left==null &&item.right==null) {
               return depth
           } 
           if(item&&item.left) {
            q.push(item.left)
           }
           if(item&&item.right) {
             q.push(item.right)
           } 
           
       }
    depth++
   }
   return depth
};

  1. 集合的所有子集

    思考： 回溯法 画图 难的是分析可遍历的结果

    image-20230417182153239

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    var subsets = function(nums) {
     var step = [] // 临时记录选择
     var result= [] // 记录结果
     let backtrack =  function(arr,index) {
        if(index>=arr.length) {
            console.log("走不通了，到底了")
            return
        }
        for(var i=index;i<arr.length;i++) {
            console.log("进入",arr[i])
            step.push(arr[i])
            result.push([...step])
            backtrack(arr,i+1)
            console.log("离开节点",arr[i])
            step.pop()
        }
     }
     backtrack(nums,0)
     result.push([])
     return result
    };

技术
#leetcode
leetcode 解题
https://godbuttton.github.io/2023/04/11/leetcode-解题/
作者
godbutton
发布于
2023年4月11日
许可协议