leetcode 解题

leetcode

练习说明：边读《labuladong 的算法小抄》，边用 LeetCode 题目练习。

二叉树的中序遍历（94）

题目链接

/**
 * 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
};

全排列（46）

题目链接 · 视频参考

/**
 * @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
};

N 皇后（51）

题目链接

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)
};

二分查找

题目链接

  
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))

最小覆盖子串

题目链接

  
/**
 * @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
};
  

二叉树的最小深度

题目链接

// 第一种解法递归的解法
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
};

集合的所有子集

题目链接

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

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
};