LeetCode解题记录

模板 - num

leetcode地址
标签：
解题思路
解题步骤

两数之和 - 1

leetcode地址
标签：字典
解题思路
解题步骤

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  const map = new Map()
  for (let i = 0; i < nums.length; i += 1) {
    const n = nums[i]
    const n2 = target - n
    if (map.has(n2)) {
      return [map.get(n2), i]
    } else {
      map.set(n, i)
    }
  }
};

两数相加 - 2

leetcode地址
标签：链表
解题思路
解题步骤

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
  const l3 = new ListNode(0)
  let p1 = l1
  let p2 = l2
  let p3 = l3
  let carry = 0
  while (p1 || p2) {
    const val = (p1 ? p1.val : 0) + (p2 ? p2.val : 0) + carry
    carry = Math.floor(val / 10)
    p3.next = new ListNode(val % 10)
    p1 && (p1 = p1.next)
    p2 && (p2 = p2.next)
    p3 = p3.next
  }
  carry && (p3.next = new ListNode(carry))
  return l3.next
};

无重复字符的最长子串 - 3

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  // 双指针维护滑动窗口
  let l = 0
  let res = 0
  const map = new Map()
  for (let r = 0; r < s.length; r += 1) {
    if (map.has(s[r]) && map.get(s[r]) >= l) {
      l = map.get(s[r]) + 1
    }
    res = Math.max(res, r - l + 1)
    map.set(s[r], r)
  }
  return res
};

有效的括号 - 20

leetcode地址
标签：栈
解题思路
解题步骤

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  if (s.length % 2 === 1) { return false }
  const stack = []
  const map = new Map()
  map.set('{', '}')
  map.set('[', ']')
  map.set('(', ')')
  // 方法一
  // const left = ['(', '{', '[']
  // const right = [')', '}', ']']
  // for (let i = 0; i < s.length; i += 1) {
  //   if (left.some(v => v === s[i])) {
  //     stack.push(s[i])
  //   }
  //   const index = right.findIndex(v => v === s[i])
  //   if (index > -1) {
  //     if (stack[stack.length - 1] === left[index]) {
  //       stack.pop()
  //     } else {
  //       return false
  //     }
  //   }
  // }
  // 方法二
  // for (let i = 0; i < s.length; i += 1) {
  //   const c = s[i]
  //   if (c === '(' || c === '{' || c === '[') {
  //     stack.push(c)
  //   } else {
  //     t = stack[stack.length - 1]
  //     if (
  //       (t === '(' && c === ')') ||
  //       (t === '{' && c === '}') ||
  //       (t === '[' && c === ']')
  //     ) {
  //       stack.pop()
  //     } else {
  //       return false
  //     }
  //   }
  // }
  // return stack.length === 0
  // 方法三：使用字典优化
  for (let i = 0; i < s.length; i += 1) {
    const c = s[i]
    if (map.has(c)) {
      stack.push(c)
    } else {
      t = stack[stack.length - 1]
      if (map.get(t) === c) {
        stack.pop()
      } else {
        return false
      }
    }
  }
  return stack.length === 0
};

合并两个有序链表 - 21

leetcode地址
标签：排序、归并排序
解题思路

• 与归并排序中合并两个有序数组相似

解题步骤

1. 新建一个链表，作为返回结果
2. 用指针遍历两个有序链表，并比较两个链表的当前节点，较小者先接入新链表，并将指针后移一步

3. 遍历结果，返回新链表

   /**
   * Definition for singly-linked list.
   * function ListNode(val, next) {
   *     this.val = (val===undefined ? 0 : val)
   *     this.next = (next===undefined ? null : next)
   * }
   */
   /**
   * @param {ListNode} l1
   * @param {ListNode} l2
   * @return {ListNode}
   */
   var mergeTwoLists = function(l1, l2) {
   const res = new ListNode()
   let p1 = l1
   let p2 = l2
   let p3 = res
   while (p1 && p2) {
    if (p1.val < p2.val) {
      p3.next = p1
      p1 = p1.next
    } else {
      p3.next = p2
      p2 = p2.next
    }
    p3 = p3.next
   }
   if (p1) p3.next = p1
   if (p2) p3.next = p2
   return res.next
   };

合并 K 个升序链表 - 23

leetcode地址
标签：堆、最小堆、链表
解题思路

• 新链表的下一个节点一定是 k 个链表头中最小的节点
• 考虑使用最小堆

解题步骤

1. 构建最小堆，并依次把链表头插入堆中
2. 弹出堆顶接到输出链表，并将堆顶所在链表的新链表头插入堆中

3. 等堆元素全部弹出，合并工作即完成 ```javascript class MinHeap { constructor() { this.heap = [] }

   swap(i1, i2) { const temp = this.heap[i1] this.heap[i1] = this.heap[i2] this.heap[i2] = temp }

   getParentIndex(i) { return (i - 1) >> 1 }

   getLeftIndex(i) { return i * 2 + 1 }

   getRightIndex(i) { return i * 2 + 2 }

   shiftUp(index) { if (index === 0) return const parentIndex = this.getParentIndex(index)

   if (this.heap[parentIndex] && this.heap[parentIndex].val > this.heap[index].val) { this.swap(parentIndex, index) this.shiftUp(parentIndex) } }

   shiftDown(index) { const leftIndex = this.getLeftIndex(index) const rightIndex = this.getRightIndex(index)

   if (this.heap[leftIndex] && this.heap[leftIndex].val < this.heap[index].val) { this.swap(leftIndex, index) this.shiftDown(leftIndex) } if (this.heap[rightIndex] && this.heap[rightIndex].val < this.heap[index].val) { this.swap(rightIndex, index) this.shiftDown(rightIndex) } }

   // 插入方法 insert(value) { this.heap.push(value) this.shiftUp(this.heap.length - 1) }

   // 删除方法 pop() { if (this.heap.length === 1) return this.heap.pop() const top = this.heap[0] this.heap[0] = this.heap.pop() this.shiftDown(0) return top }

   // 获取堆顶 top() { return this.heap[0] }

   // 获取堆大小 size() { return this.heap.length } }

/**

• Definition for singly-linked list.
• function ListNode(val, next) {
• this.val = (val===undefined ? 0 : val)
• this.next = (next===undefined ? null : next)
• } / /*
• @param {ListNode[]} lists
• @return {ListNode} */ var mergeKLists = function(lists) { const res = new ListNode(0) const h = new MinHeap() let p = res lists.forEach(v => { v && h.insert(v) }) while(h.size()) { const n = h.pop() p.next = n p = p.next n.next && h.insert(n.next) } return res.next }; ```

接雨水 - 42

leetcode地址
标签：栈、单调栈
解题思路

• 出现高的柱子时，即右边第一个比左边大的数，才会出现坑洼，即能接到雨水
• 利用单调递减栈的思想
• 存放索引，再逐个配对，消除

解题步骤

1. 低柱子入栈，构建单调递减栈
2. 出现比栈顶大的柱子时，进行一次结算
3. 接水区域面积 = 宽 * 高
4. 其中宽（底部的左边到右边的距离）、高（左右两边更低的一遍减去底部）

   /**
   * @param {number[]} height
   * @return {number}
   */
   var trap = function(height) {
   // 单调栈
   const stack = []
   let count = 0
   for (let i = 0; i < height.length; i++) {
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      const cur = stack.pop()
      if (!stack.length) {
        break
      }
      const l = stack[stack.length - 1]
      const h = Math.min(height[l], height[i]) - height[cur]
      count += (i - l - 1) * h
    }
    stack.push(i)
   }
   return count
   };

全排列 - 46

leetcode地址
标签：回溯算法
解题思路

• 要求：1、所有排列情况；2、没有重复元素
• 有出路、有死路
• 考虑使用回溯算法

解题步骤

1. 用递归模拟出所有情况
2. 遇到包含重复元素的情况，就回溯
3. 收集所有到达递归终点的情况，并返回

   /**
   * @param {number[]} nums
   * @return {number[][]}
   */
   var permute = function(nums) {
   const res = []
   const rec = (path) => {
    if (path.length === nums.length) {
      res.push(path)
    }
    nums.forEach(v => {
      if (path.includes(v)) return
      rec(path.concat(v))
    })
   }
   rec([])
   return res
   };

有效数字 - 65

解题思路

/**
 * @param {string} s
 * @return {boolean}
 */
var isNumber = function(s) {
  const graph = {
    0: { blank: 0, sign: 1, '.': 2, digit: 6 },
    1: { '.': 2, digit: 6 },
    2: { digit: 3 },
    3: { digit: 3, e: 4 },
    4: { digit: 5, sign: 7 },
    5: { digit: 5 },
    6: { '.': 3, e: 4, digit: 6 },
    7: { digit: 5 } 
  }
  let state = 0
  for (c of s.trim()) {
    if (c === '+' || c === '-') {
      c = 'sign'
    } else if (c >= '0' && c <= '9') {
      c = 'digit'
    } else if (c === ' ') {
      c = 'blank'
    } else if (c === 'E') {
      c = 'e'
    }
    state = graph[state][c]
    if (state === undefined) {
      return false
    }
  }
  if (state === 3 || state === 5 || state === 6) {
    return true
  }
  return false
};

爬楼梯 - 70

leetcode地址
标签：动态规划
解题思路

• 爬到第 n 阶可以在 第 n-1 阶爬 1 个台阶，或者在第 n-2 阶爬 2 个台阶
• F(n) = F(n - 1) + F(n - 2)

解题步骤

1. 定义子问题：F(n) = F(n - 1) + F(n - 2)
2. 反复执行：从 2 循环到 n，执行上述公式

   /**
   * @param {number} n
   * @return {number}
   */
   var climbStairs = function(n) {
   if (n === 1) return 1
   let dp0 = 1
   let dp1 = 1
   for (let i = 2; i <= n; i += 1) {
    const temp = dp0
    dp0 = dp1
    dp1 = dp1 + temp
   }
   return dp1
   };

   最小覆盖子串 - 76

/**
 * @param {string} s
 * @param {string} t
 * @return {string}
 */
var minWindow = function(s, t) {
  // 用双指针维护滑动窗口
  // 移动右指针，找到包含 t 的子串，再移动左指针，尽量减少包含 t 的子串长度
  let l = 0
  let r = 0
  const need = new Map()
  for (let c of t) {
    need.set(c, need.has(c) ? need.get(c) + 1 : 1)
  }
  let needType = need.size
  let res = ''
  while (r < s.length) {
    const c = s[r]
    if (need.has(c)) {
      need.set(c, need.get(c) - 1)
      if (need.get(c) === 0) { needType -= 1 }
      while (needType === 0) {
        const newRes = s.substring(l, r + 1)
        if (!res || newRes.length < res.length) { res = newRes }
        const c2 = s[l]
        if (need.has(c2)) {
          need.set(c2, need.get(c2) + 1)
          if (need.get(c2) === 1) { needType += 1 }
        }
        l += 1
      }
    }
    r += 1
  }
  return res
};

子集 - 78

leetcode地址
标签：回溯算法
解题思路

• 要求：1、所有子集；2、没有重复元素
• 有出路、有死路
• 考虑使用回溯算法

解题步骤

1. 用递归模拟出所有情况
2. 保证接的数字都是后面的数字
3. 收集所有到达递归终点的情况，并返回

   /**
   * @param {number[]} nums
   * @return {number[][]}
   */
   var subsets = function(nums) {
   const res = []
   const rec = (path, len, start) => {
    if (path.length === len) {
      res.push(path)
      return
    }
    for (let i = start; i < nums.length; i += 1) {
      rec(path.concat(nums[i]), len, i + 1)
    }
   }
   for (let i = 0; i <= nums.length; i += 1) {
    rec([], i, 0)
   }
   return res
   };

   删除排序链表中的重复元素 - 83

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
  let p = head
  while (p && p.next) {
    if (p.val === p.next.val) {
      p.next = p.next.next
    } else {
      p = p.next
    }
  }
  return head
};

二叉树的中序遍历 - 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) {
  const res = []
  // 递归版
  // const rec = (n) => {
  //   if (!n) return
  //   rec(n.left)
  //   res.push(n.val)
  //   rec(n.right)
  // }
  // rec(root)
  // 迭代算法，使用栈
  const stack = []
  let p = root
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    res.push(n.val)
    p = n.right
  }
  return res  
};

相同的树 - 100

leetcode地址
标签：二叉树、分而治之
解题思路

• 两个树：根节点的值相同，左子树相同，右子树相同
• 符合“分、解、合”，考虑分而治之

解题步骤

1. 分：获取两个树的左子树合右子树
2. 解：递归判断两个树的左子树是否相同，右子树是否相同
3. 合：将上述结果合并，如果根节点的值也相同，树就相同

   /**
   * 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} p
   * @param {TreeNode} q
   * @return {boolean}
   */
   var isSameTree = function(p, q) {
   if (!p && !q) return true
   if (p && q && p.val === q.val &&
    isSameTree(p.left, q.left) && 
    isSameTree(p.right, q.right)
   ) {
    return true
   }
   return false
   };

   对称二叉树 - 101

   leetcode地址
   标签：二叉树、分而治之
   解题思路

• 转换为：左右子树是否镜像
• 分解为：树1的左子树和树2的右子树是否镜像，树1的右子树和树2的左子树是否镜像
• 符合“分、解、合”

解题步骤

1. 分：获取两个树的左子树合右子树
2. 解：递归判断树1的左子树和树2的右子树是否镜像，树1的右子树和树2的左子树是否镜像
3. 合：将上述结果合并，如果根节点的值也相同，两个树就镜像

   /**
   * 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 {boolean}
   */
   var isSymmetric = function(root) {
   if (!root) return true
   const isMirror = (l, r) => {
    if (!l && !r) return true
    if (l && r && l.val === r.val &&
      isMirror(l.left, r.right) &&
      isMirror(l.right, r.left)
    ) {
      return true
    }
    return false
   }
   return isMirror(root.left, root.right)
   };

   二叉树的层序遍历 - 102

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
  // 广度优先遍历
  // 方法一
  // if (!root) return []
  // const q = [[root, 0]]
  // let res = []
  // while (q.length) {
  //   const [n, level] = q.shift()
  //   if (!res[level]) {
  //     res.push([n.val])
  //   } else {
  //     res[level].push(n.val)
  //   }
  //   n.left && q.push([n.left, level + 1])
  //   n.right && q.push([n.right, level + 1])
  // }
  // return res
  // 方法二
  if (!root) return []
  const q = [root]
  let res = []
  while (q.length) {
    let len = q.length
    res.push([])
    while(len--) {
      const n = q.shift()
      res[res.length - 1].push(n.val)
      n.left && q.push(n.left)
      n.right && q.push(n.right)
    }
  }
  return res
};

二叉树的最大深度 - 104

/**
 * 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 maxDepth = function(root) {
  // 深度优先遍历
  let res = 0
  const dfs = (n, l) => {
    if (!n) return
    (!n.left && !n.right) && (res = Math.max(res, l))
    dfs(n.left, l + 1)
    dfs(n.right, l + 1)
  }
  dfs(root, 1)
  return res
};

二叉树的最小深度 - 111

/**
 * 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 minDepth = function(root) {
  // 广度优先遍历
  if (!root) return 0
  const q = [[root, 1]]
  while (q.length) {
    const [n, l] = q.shift()
    if (!n.left && !n.right) {
      return l
    }
    n.left && q.push([n.left, l + 1])
    n.right && q.push([n.right, l + 1])
  }
};

路径总和 - 112

/**
 * 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
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
  // 深度优先遍历
  if (!root) return false
  let res = false
  const dfs = (n, s) => {
    if (!n.left && !n.right && s === targetSum) {
      res = true
    }
    n.left && dfs(n.left, s + n.left.val)
    n.right && dfs(n.right, s + n.right.val)
  }
  dfs(root, root.val)
  return res
};

买卖股票的最佳时机 - 122

leetcode地址
标签：贪心算法
解题思路

• 前提：上帝视角，知道未来的价格
• 局部最优：见好就收，见差就不动，不做任何长远打算

解题步骤

1. 新建一个变量，用来统计总利润
2. 遍历价格数组，如果当前价格比昨天高，就在昨天买，今天卖，否则就不交易

3. 遍历结束后，返回总利润

   /**
   * @param {number[]} prices
   * @return {number}
   */
   var maxProfit = function(prices) {
   let profit = 0
   for (let i = 1; i < prices.length; i += 1) {
    if (prices[i] > prices[i - 1]) {
      profit += prices[i] - prices[i - 1]
    }
   }
   return profit
   };

   克隆图 - 133

   leetcode地址
   标签：图、深度/广度优先遍历
   解题思路

4. 拷贝所有的节点

5. 拷贝所有的边

解题步骤

1. 深度或广度优先遍历所有节点
2. 拷贝所有的节点，并存储
3. 将拷贝的节点，按原图的连接方式连接 ```javascript /**
   • // Definition for a Node.
   • function Node(val, neighbors) {
   • this.val = val === undefined ? 0 : val;
   • this.neighbors = neighbors === undefined ? [] : neighbors;
   • }; */

/**

• @param {Node} node

• @return {Node} */ var cloneGraph = function(node) { if (!node) return

  const visited = new Map() // 深度优先遍历 // const dfs = (n) => { // const nCopy = new Node(n.val) // visited.set(n, nCopy); // (n.neighbors || []).forEach(ne => { // if (!visited.has(ne)) { // dfs(ne) // } // nCopy.neighbors.push(visited.get(ne)) // }) // } // dfs(node)

  // 广度优先遍历 const q = [node] visited.set(node, new Node(node.val)) while (q.length) { const n = q.shift(); (n.neighbors || []).forEach(ne => {

   if (!visited.has(ne)) {
     q.push(ne)
     visited.set(ne, new Node(ne.val))
   }
   visited.get(n).neighbors.push(visited.get(ne))

  }) }

  return visited.get(node) }; ```

  环形链表 - 141

  leetcode地址
  标签：链表、双指针
  解题思路

1. 双指针遍历
2. 一前一后，快的每次前进两格，慢的每次前进一格，若存在环，则两个指针会相遇，否则遍历结束 ```javascript /**
   • Definition for singly-linked list.
   • function ListNode(val) {
   • this.val = val;
   • this.next = null;
   • } */

/**

• @param {ListNode} head

• @return {boolean} */ var hasCycle = function(head) { // 双指针解法 let p1 = head let p2 = head

  while (p1 && p2 && p2.next) { p1 = p1.next p2 = p2.next.next if (p1 === p2) { return true } } return false }; ```

打家劫舍 - 198

leetcode地址
标签：动态规划
解题思路

• f(k) = 从前 k 个房屋中能偷窃到的最大数额
• Ak = 第 k 个房屋的钱数
• f(k) = max(f(k - 2) + Ak, f(k - 1))

解题步骤

1. 定义子问题：max(f(k - 2) + Ak, f(k - 1))

2. 反复执行：从 2 循环到 n，执行上述公式

   /**
   * @param {number[]} nums
   * @return {number}
   */
   var rob = function(nums) {
   if (nums.length === 0) return 0
   let dp0 = 0
   let dp1 = nums[0]
   for (let i = 1; i < nums.length; i += 1) {
    const temp = dp0
    dp0 = dp1
    dp1 = Math.max(temp + nums[i], dp1)
   }
   return dp1
   };

反转链表 - 206

leetcode地址
标签：链表、双指针、递归
解题思路
1、双指针

• 双指针 cur、pre 一前一后遍历
• 将 pre 指向 cur 实现局部交换，再各自向后移动一位

2、递归

• 逐个递归遍历至链表尾
• 此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。
• 同时让当前结点的 next 指针指向 NULL ，从而实现从链表尾部开始的局部反转

解题步骤

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  // 双指针
  let pre = head
  let cur = null
  while (pre) {
    const tmp = pre.next
    pre.next = cur
    cur = pre
    pre = tmp
  }
  return cur
  // 递归
  if (head === null || head.next === null) return head
  const next = head.next
  const reverseNode = reverseList(next)
  next.next = head
  head.next = null
  return reverseNode
};

数组中的第 K 个最大元素 - 215

leetcode地址
标签：堆、最小堆
解题思路

1. 看到 “第 K 个最大元素”
2. 考虑使用最小堆

解题步骤

1. 构建一个最小堆，依次把数组的值插入堆中
2. 当堆的容量超过 K，删除堆顶

3. 插入结束后，堆顶即是第 K 个最大元素 ```javascript class MinHeap { constructor() { this.heap = [] }

   swap(i1, i2) { const temp = this.heap[i1] this.heap[i1] = this.heap[i2] this.heap[i2] = temp }

   getParentIndex(i) { return (i - 1) >> 1 }

   getLeftIndex(i) { return i * 2 + 1 }

   getRightIndex(i) { return i * 2 + 2 }

   shiftUp(index) { if (index === 0) return const parentIndex = this.getParentIndex(index) if (this.heap[parentIndex] > this.heap[index]) { this.swap(parentIndex, index) this.shiftUp(parentIndex) } }

   shiftDown(index) { const leftIndex = this.getLeftIndex(index) const rightIndex = this.getRightIndex(index)

   if (this.heap[leftIndex] < this.heap[index]) { this.swap(leftIndex, index) this.shiftDown(leftIndex) } if (this.heap[rightIndex] < this.heap[index]) { this.swap(rightIndex, index) this.shiftDown(rightIndex ) } }

   // 插入方法 insert(value) { this.heap.push(value) this.shiftUp(this.heap.length - 1) }

   // 删除方法 pop() { this.heap[0] = this.heap.pop() this.shiftDown(0) }

   // 获取堆顶 top() { return this.heap[0] }

   // 获取堆大小 size() { return this.heap.length } }

/**

• @param {number[]} nums
• @param {number} k

• @return {number} */ var findKthLargest = function(nums, k) { // 使用 sort // return nums.sort((a, b) => a - b)[nums.length - k]

  // 使用最小堆 const h = new MinHeap() nums.forEach(v => { h.insert(v) if (h.size() > k) { h.pop() } }) return h.top() }; ```

翻转二叉树 - 226

leetcode地址
标签：二叉树、分而治之
解题思路

• 先翻转左右子树，再将子树换个位置
• 符合“分、解、合”，即分而治之的特性

解题步骤

1. 分：获取左右子树
2. 解：递归地翻转左右子树
3. 合：将翻转后的左右子树，换个位置放到根节点上

   /**
   * 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 {TreeNode}
   */
   var invertTree = function(root) {
   if (!root) return null
   return {
    val: root.val,
    left: invertTree(root.right),
    right: invertTree(root.left)
   }
   };

   删除链表中的节点 - 237

   leetcode地址
   标签：链表
   解题思路
   解题步骤

   /**
   * Definition for singly-linked list.
   * function ListNode(val) {
   *     this.val = val;
   *     this.next = null;
   * }
   */
   /**
   * @param {ListNode} node
   * @return {void} Do not return anything, modify node in-place instead.
   */
   var deleteNode = function(node) {
   node.val = node.next.val
   node.next = node.next.next
   };

反转字符串 - 344

leetcode地址
标签：字符串、双指针
解题思路

• 通过左右两个指针 left、right 分别从数组首尾向中间遍历，并交换

  /**
  * @param {character[]} s
  * @return {void} Do not return anything, modify s in-place instead.
  */
  var reverseString = function(s) {
  const len = s.length
  if (len <= 1) return s
  let left = 0
  let right = len - 1
  while (left < right) {
    const temp = s[left]
    s[left] = s[right]
    s[right] = temp
    left += 1
    right -= 1
  }
  return s
  };

前 K 个高频元素 - 347

leetcode地址
标签：堆、最小堆
解题思路

1. 看到 “前 K 个元素”
2. 考虑使用最小堆

解题步骤

1. 构建一个最小堆，依次把数组的值插入堆中
2. 当堆的容量超过 K，删除堆顶

3. 插入结束后，当前的堆即是前 K 个高频元素 ```javascript class MinHeap { constructor() { this.heap = [] }

   swap(i1, i2) { const temp = this.heap[i1] this.heap[i1] = this.heap[i2] this.heap[i2] = temp }

   getParentIndex(i) { return (i - 1) >> 1 }

   getLeftIndex(i) { return i * 2 + 1 }

   getRightIndex(i) { return i * 2 + 2 }

   shiftUp(index) { if (index === 0) return const parentIndex = this.getParentIndex(index)

   if (this.heap[parentIndex] && this.heap[parentIndex].value > this.heap[index].value) { this.swap(parentIndex, index) this.shiftUp(parentIndex) } }

   shiftDown(index) { const leftIndex = this.getLeftIndex(index) const rightIndex = this.getRightIndex(index)

   if (this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value) { this.swap(leftIndex, index) this.shiftDown(leftIndex) } if (this.heap[rightIndex] && this.heap[rightIndex].value < this.heap[index].value) { this.swap(rightIndex, index) this.shiftDown(rightIndex) } }

   // 插入方法 insert(value) { this.heap.push(value) this.shiftUp(this.heap.length - 1) }

   // 删除方法 pop() { this.heap[0] = this.heap.pop() this.shiftDown(0) }

   // 获取堆顶 top() { return this.heap[0] }

   // 获取堆大小 size() { return this.heap.length } }

/**

• @param {number[]} nums
• @param {number} k

• @return {number[]} */ var topKFrequent = function(nums, k) { const map = new Map() nums.forEach(v => { map.set(v, map.has(v) ? map.get(v) + 1 : 1) }) // 使用 sort // const list = […map].sort((a, b) => b[1] - a[1]) // return list.slice(0, k).map(v => v[0])

  // 使用最小堆 const h = new MinHeap() map.forEach((value, key) => { h.insert({ value, key }) if (h.size() > k) { h.pop() } }) return h.heap.map(v => v.key) }; ```

两个数组的交集 - 349

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
  // 使用集合
  // return [...new Set(nums1)].filter(v => nums2.includes(v))
  // 使用字典
  const map = new Map()
  nums1.forEach(v => {
    map.set(v, true)
  })
  const res = []
  nums2.forEach(v => {
    if (map.get(v)) {
      res.push(v)
      map.delete(v)
    }
  })
  return res
};

猜数字大小 - 374

leetcode地址
标签：搜索、二分搜索

/** 
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return                 -1 if num is lower than the guess number
 *                         1 if num is higher than the guess number
 *                       otherwise return 0
 * var guess = function(num) {}
 */
/**
 * @param {number} n
 * @return {number}
 */
var guessNumber = function(n) {
  let begin = 1
  let end = n
  while (begin <= end) {
    const mid = Math.floor((begin + end) / 2)
    if (guess(mid) === 0) {
      return mid
    } else if (guess(mid) === -1) {
      end = mid - 1
    } else if (guess(mid) === 1) {
      begin = mid + 1
    }
  }
};

太平洋大西洋水流问题 - 417

标签：图、邻接矩阵、深度优先遍历

解题思路

1. 把矩阵相像成图
2. 从海岸线逆流而上遍历图，所到之处就是可以留到某个大洋的坐标

解题步骤

1. 新建两个矩阵，分别存可流向太平洋和大西洋的坐标
2. 分别对4条海岸线上节点进行深度优先遍历，过程填充以上两个矩阵
3. 遍历两个矩阵，找到同时可流向太平洋和大西洋的坐标

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var pacificAtlantic = function(matrix) {
  if (!matrix || !matrix[0]) return []
  const m = matrix.length
  const n = matrix[0].length
  const flow1 = Array.from({ length: m }, () => new Array(n).fill(false)) // 太平洋
  const flow2 = Array.from({ length: m }, () => new Array(n).fill(false)) // 大西洋
  const dfs = (r, c, flow) => {
    flow[r][c] = true;
    [[r - 1, c], [r + 1, c], [r, c -1], [r, c + 1]].forEach(([nr, nc]) => {
      if (
        // 保证在矩阵中
        nr >= 0 && nr < m &&
        nc >= 0 && nc < n &&
        // 防止死循环
        !flow[nr][nc] &&
        // 保证逆流而上
        matrix[nr][nc] >= matrix[r][c]
      ) {
        dfs(nr, nc, flow)
      }
    })
  }
  // 从海岸线往上遍历
  for (let r = 0; r < m; r += 1) {
    dfs(r, 0, flow1)
    dfs(r, n - 1, flow2)
  }
  for (let c = 0; c < n; c += 1) {
    dfs(0, c, flow1)
    dfs(m - 1, c, flow2)
  }
  // 找出俩矩阵同为 true 的值
  const res = []
  for (let r = 0; r < m; r += 1) {
    for (let c = 0; c < n; c += 1) {
      if (flow1[r][c] && flow2[r][c]) res.push([r, c])
    }
  }
  return res
};

分饼干 - 455

leetcode地址
标签：贪心算法
解题思路

• 局部最优：既能满足孩子，还能消耗最少
• 先将 “较小的饼干” 分给 “胃口最小” 的孩子

解题步骤

1. 对饼干数组和胃口数组升序排序
2. 遍历饼干数组，找到能满足第一个孩子的饼干

3. 然后继续遍历饼干数组，找到满足第二、三、……、n 个孩子的饼干

   /**
   * @param {number[]} g
   * @param {number[]} s
   * @return {number}
   */
   var findContentChildren = function(g, s) {
   g.sort((a, b) => a - b)
   s.sort((a, b) => a - b)
   let i = 0
   s.forEach(v => {
    if (v >= g[i]) {
      i += 1
    }
   })
   return i
   };

   斐波那契数 - 509

   leetcode地址
   标签：数组、动态规划
   解题思路
   解题步骤

   /**
   * @param {number} n
   * @return {number}
   */
   var fib = function(n) {
   if (n < 2) return n
   let dp0 = 0
   let dp1 = 1
   for (let i = 2; i <= n; i += 1) {
    const temp = dp1
    dp1 = dp1 + dp0
    dp0 = temp
   }
   return dp1
   // 便于理解写法
   // let dp = [0, 1]
   // for (let i = 2; i <= n; i += 1) {
   //   dp[i] = dp[i - 1] + dp[i - 2]
   // }
   // return dp[n]
   };

有效的括号字符串 - 678

leetcode地址
标签：栈、双栈
解题思路

• 左括号、星号各建立一个栈**
• 遇到左括号和星号入栈，遇到右括号依次和左括号、星号做比较
• 最后再判断是否星号都在左括号右侧

**

/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function(s) {
  const stackLeft = [] 
  const stackStar = []
  for (let i = 0; i < s.length; i += 1) {
    if (s[i] === '(') {
      stackLeft.push(i) // 存储索引
    } else if (s[i] === '*') {
      stackStar.push(i) // 存储索引
    } else {
      if (stackLeft.length) {
        stackLeft.pop()
        continue
      } else {}
      if (stackStar.length) {
        stackStar.pop()
        continue
      }
      return false
    }
  }
  if (stackLeft.length > stackStar.length) return false
  // 判断是否 * 都在 ( 的右边
  while (stackLeft.length) {
    const lTop = stackLeft.pop()
    const sTop = stackStar.pop()
    if (lTop > sTop) return false
  }
  return true
};

计算最近请求次数 - 933

leetcode地址
标签：队列
解题思路
解题步骤

var RecentCounter = function() {
  this.q = []
};
/** 
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
  this.q.push(t)
  while (this.q[0] < t - 3000) {
    this.q.shift()
  }
  return this.q.length
};
/**
 * Your RecentCounter object will be instantiated and called as such:
 * var obj = new RecentCounter()
 * var param_1 = obj.ping(t)
 */