JavaScript笔试刷题小结（二）

继续整理最近的刷题记录

1. 剑指Offer 39. 数组中出现次数过半的数字

书中提到了两种复杂度均为O(n)的解法：
1）基于Partition函数：
如果这个数字存在，那它必然是数组排序后的中位数，基于随机快排中的Partition的思想对数组进行操作，如果选中的数字index = n/2，恰好它是中位数；index>n/2,中位数在其左边；index<n/2,中位数在其右边
cc觉得js可以如此简单粗暴：

var majorityElement = function(nums){
  nums.sort()
  return nums[Math.floor(nums.length/2)]
}

2）根据数组特点：
如果该数字存在，则它的次数绝对比其他元素多;
遍历数组，同时统计当前元素的次数，出现相同元素+1，出现其他元素-1，最后返回times>0的元素，即为所求数字

var marjorityElement = function(nums){
  let res = nums[0]
  let times = 1
  for(let i = 1; i < nums.length; ++i){
    if(times === 0){
      res = nums[i]
      times = 1
    }else if(nums[i] === res){
      times ++
    }else{
      times --
    }
  }
  return res
}

2. 剑指Offer 59-Ⅱ. 队列中的最大值

这个题目，要不是出现在每日挑战，我真的不会做，出题人思路清奇？尤其是看了评论区发现大家都看不懂，得~~~没有技术含量，尤其对于js和python来说

var MaxQueue = function() {
    this.arr = []
};

/**
 * @return {number}
 */
MaxQueue.prototype.max_value = function() {
    return (this.arr.length > 0) ? Math.max(...this.arr) : -1
};

/** 
 * @param {number} value
 * @return {void}
 */
MaxQueue.prototype.push_back = function(value) {
  if(value !== null){
    this.arr.push(value)
  }
};

/**
 * @return {number}
 */
MaxQueue.prototype.pop_front = function() {
    if(this.arr.length > 0)
      return this.arr.shift()
    return -1
};

3. 剑指Offer 42. 连续子数组的最大和

使用动态规划计算，当前位置处的最大和等于上一个位置上的最大和与与最大和加当前位置值之和中的较大值，状态转移方程式：

var maxSubArray = function(nums) {
    let res = nums[0]
    let maxSum = 0
    nums.map((item) =>{
        maxSum = Math.max(maxSum + item, item)
        res = Math.max(maxSum, res)
    })
    return res
};

4. 剑指Offer 40. 最小的k个函数

对于js和python来说，这道题调包当然非常简单，截取排序数组的前k个即可

1）直接排序做法（简单、直观、时间O(n*logN) ---- 空间O(logN)）：

var getLeastNumbers = function(arr, k){
  return arr.sort((a,b) => a-b).slice(0,k)
}

但是实际上，我们获取前k个数字的时候，并不需要对整个数组进行排序，尤其是在 k << length 的情况下，是非常消耗性能的

2） 使用最大堆（手动写堆略复杂、时间O(K) ---- 空间O(n*logK)）

整体的算法流程：

• 创建大小为k的最大堆
• 将数组的前k个元素放入堆中
• 从下标k继续开始依次遍历数组的剩余元素
  （如果元素小于堆顶元素，那么取出堆顶元素，将当前元素入堆；如果元素大于/等于堆顶元素，不做操作）

function swap(arr, i, j){
  [arr[i], arr[j]] = [arr[j], arr[i]]
}
class maxHeap{
  constructor(arr = []){
    this.container == []
    if(Array.isArray(arr)){
      arr.forEach(this.insert.bind(this))
    }
  }

  insert(data){
    const {container} = this
    container.push(data)
    let index = container.length - 1
    while(index){
      let parent = Math.floor((index-1)/2)
      if(container[index] <= container[parent]){
        break
      }
      swap(container, index, parent)
      index = parent
    }
  }
  extract(){
    const { container } = this
    if(!container.length){
      return null
    }
    swap(container, 0, container.length-1)
    const res = container.pop()
    const length = container.length
    let index = 0
    let exchange = index * 2 + 1
    while(exchange < length){
      let right = index * 2 + 2
      if(right < length && container[right] > container[exchange]){
        exchange = right
      }
      if(container[exchange] <= container[index]){
        break
      }
      swap(container, exchange, index)
      index = exchange
      exchange = index * 2 + 1
    }
    return res
  }
  top(){
    if(this.container.length){
      return this.container[0]
    }
    return null
  }
}
var getLeastNumbers = function(arr, k){
  const length =  arr.length
  if(k >= length){
    return arr
  }
  const heap = new MaxHeap(arr.slice(0,k))
  for(let i = k; i < length; ++i){
    if(hash.top() > arr[i]){
      heap.extract()
      heap.insert(arr[i])
    }
  }
  return heap.container
}

3）基于快速排序的Partition（时间O(N) ---- 空间O(N)）：

可以使用快速排序中的Partition,把元素arr[0]放入排序后的正确位置，并且返回这个位置index。算法流程如下：

• 如果index = k, 说明第k个元素已经放在正确位置，返回前k个
• 如果index > k,前k个元素在[left, index-1]之间，缩小查找范围，继续查找
• 如果index < k,前k个元素在[index+1,right]之间，缩小查找范围，继续查找

function partition(arr, start, end){
  const k = arr[start]
  let left = start + 1
  let right = end
  while(1){
    while(left <= end && arr[left] <= k) ++ left
    while(right >= start && arr[right] >= k) -- right

    if(left >= right){
      break
    }
    [arr[right], arr[start]] = [arr[start], arr[right]]
    return right
  }
}
var getLeastNumbers = function(arr, k){
  const length = arr.length
  if(k >= length) return arr
  let left = 0
  let right = length - 1
  let index = partition(arr, left, right)
  while(index !== k){
    if(index < k){
      left = index + 1
    }else if(index > k){
      right = index - 1
    }
    index = partition(arr, left, right)
  }
  return arr.slice(0,k)
}

相比之下，更推荐第三种Partition的解法，手写堆太复杂了

5. Leetcode 93. 复原IP地址

思路：使用基于递归的DFS方法，去掉不符合的情况，每次从字符串开始位置截掉长度为1，2，3之后剩下的子串，用于递归
关于这个题，求助了Z同学，开始思路有点乱然后茅塞顿开
定义递归函数很重要，思路就是每次切完当前的串之后，继续切后面的串，所以在递归函数中，我把变量设置为剩下的串，

var restoreIpAddresses = function(s){
  let res = []
  // 首先判断s长度是否满足ip，标准IP地址的长度范围4~12 (0.0.0.0 ~ 255.255.255.255)
  if(s.length < 4 || s.length > 12)   return res
   // cur表示当前未划分的字符串，pre表示前面已经划分好的（加上.的），counts表示已经划分的段数（pre中.的个数）
  function divideIpAddress(cur, pre, counts){
    if(counts === 3){
	  // 如果已经到了第三段了，只需要检查剩下的串
	  if(cur.length <= 3 && parseInt(cur.slice(0,3)) < 256 ){
	    if(cur.length >= 2 && cur.charAt(0)==='0'){
	      return //说明第四段里面首位是0，绝对不可能再划分了，剪枝
	    }
	    // 否则，将当前剩余的字符串加入到分段队列，ip分段成功
	    let item = pre.concat(cur)
	    res.push(item)
	  }
   }
   if(counts < 3){
     // 划分长度为1的作为一段
     let item = pre.concat(cur.slice(0,1)).concat('.')
     divideIpAddress(cur.slice(1), item, counts+1)
     if(cur.charAt(0) !== '0'){
       // 首位不是0的情况下，划分长度为2的作为一段
       item = pre.concat(cur.slice(0,2)).concat('.')
       divideIpAddress(cur.slice(2), item, counts+1)
       if(parseInt(cur.slice(0,3)) < 256){
         // 首位不是0且数值小于256的情况下，划分长度为3的作为一段
         item = pre.concat(cur.slice(0,3)).concat('.')
         divideIpAddress(cur.slice(3), item, counts+1)
       }
     }
   }
  }
  divideIpAddress(s, "", 0)
  return res
}

tips: 1）注意开头是0的情况 2）提前添加长度的判断（标准ip长度在4~12）

6. Leetcode 121.买卖股票的最佳时机

思路：遍历一遍数组，记录今天之前的最低价格，和今天卖出的利润，更新最大利润，时间复杂度O(n),空间复杂度O（1）

var maxProfit = function(prices) {    
  let minP = prices[0]    
  let maxP = 0    
  prices.map((item)=>{        
    maxP = item - minP > maxP? item - minP : maxP        
    if(item < minP){            
      minP = item        
    }    
  })    
  if(maxP > 0){        
    return maxP    
  }    
  return 0
};

7. Leetcode 543.二叉树的直径

思路：遍历树，比较每个节点的左右子树的高度之和，记录最大的长度为树的直径(最初cc只考虑了根节点，导致忽略了最长直径不一定过根节点，虽然题目没有指明，但是一定要考虑到）

var diameterOfBinaryTree = function(root){
  let diameter = 0
  const getMaxDepth = node =>{
    if(!node){
      return -1
    }
    let left = getMaxDepth(node.left)
    let right = getMaxDepth(node.right)
    diameter = Math.max(diameter,left+right+2) // 更新最大值
    return Math.max(left,right)+1 // 返回当前节点下的最大深度
  }
}

8. Leetcode 112.路径总和

思路：总之，递归大法好

var hasPathSum = function(root, sum) {
    if(root === null){
        return false
    }
     if(root.left === null && root.right === null){
        if(root.val === sum){
            return true
        }
        return false
    }
    return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val)
};