本周一共做了 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; };