本周一共做了 7 道题，提交均通过。

哈希表

LC 1. Two Sum 两数之和

https://leetcode.com/problems/two-sum/

用哈希表记录已经遍历过的数字，边走边找补数，把两层循环压成一层循环。

var twoSum = function(nums, target) {
  const m = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (m.has(need)) return [m.get(need), i];
    m.set(nums[i], i);
  }
  return [];
};

栈

LC 20. Valid Parentheses 有效的括号

https://leetcode.com/problems/valid-parentheses/

核心是维护一个栈，遇到右括号时立刻和栈顶匹配，不合法就提前返回。

var isValid = function(s) {
  const st = [];
  const p = new Map([
    [')', '('],
    [']', '['],
    ['}', '{']
  ]);

  for (const ch of s) {
    if (p.has(ch)) {
      if (st.pop() !== p.get(ch)) return false;
    } else {
      st.push(ch);
    }
  }

  return st.length === 0;
};

链表

LC 21. Merge Two Sorted Lists 合并两个有序链表

https://leetcode.com/problems/merge-two-sorted-lists/

这题就是标准双指针合并有序链表，dummy 节点能让代码干净很多。

var mergeTwoLists = function(list1, list2) {
  const dummy = new ListNode(0);
  let tail = dummy;
  let a = list1;
  let b = list2;

  while (a && b) {
    if (a.val <= b.val) {
      tail.next = a;
      a = a.next;
    } else {
      tail.next = b;
      b = b.next;
    }
    tail = tail.next;
  }

  tail.next = a || b;
  return dummy.next;
};

线性 DP

LC 53. Maximum Subarray 最大子数组和

https://leetcode.com/problems/maximum-subarray/

Kadane 算法的关键是：当前位置的最优解，只取“自己重新开始”或“接在前面的最优后面”两种情况。

var maxSubArray = function(nums) {
  let cur = nums[0];
  let best = nums[0];

  for (let i = 1; i < nums.length; i++) {
    cur = Math.max(nums[i], cur + nums[i]);
    best = Math.max(best, cur);
  }

  return best;
};

LC 70. Climbing Stairs 爬楼梯

https://leetcode.com/problems/climbing-stairs/

本质是斐波那契数列，状态转移非常直接，空间还可以压到 O(1)。

var climbStairs = function(n) {
  let a = 1;
  let b = 1;

  for (let i = 0; i < n; i++) {
    [a, b] = [b, a + b];
  }

  return a;
};

数组

LC 121. Best Time to Buy and Sell Stock 买卖股票的最佳时机

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

一边扫描一边维护历史最低买入价，再顺手更新当前最大利润。

var maxProfit = function(prices) {
  let minPrice = prices[0];
  let ans = 0;

  for (let i = 1; i < prices.length; i++) {
    ans = Math.max(ans, prices[i] - minPrice);
    minPrice = Math.min(minPrice, prices[i]);
  }

  return ans;
};

二分搜索

LC 704. Binary Search 二分查找

https://leetcode.com/problems/binary-search/

模板题，重点是把区间定义和循环条件想清楚，避免死循环和边界错误。

var search = function(nums, target) {
  let l = 0;
  let r = nums.length - 1;

  while (l <= r) {
    const m = (l + r) >> 1;
    if (nums[m] === target) return m;
    if (nums[m] < target) l = m + 1;
    else r = m - 1;
  }

  return -1;
};