Leetcode 基础题

简单整理了一下 Leetcode 上 easy 题目的常见分类和解题思路，easy 的题目思路都比较简单，主要考察基础的编程能力和常见数据结构的使用。

• set/hash：常用于计数、去重
  • Contains Duplicate：set 做去重
  • Single Number：解法比较多，可以 set 计数后找 count = 1 ，或者异或运算也行
  • Intersection of Two Arrays II：word count 之后在 hash 里取 count 最小值
  • Two Sum：把 target - i 存进 hash ，这样下次遍历寻找的时候就是 O(1)
• in-place：不用额外空间的数组操作，主要是 index 相关，比如记录删除后 index 的偏差
  • Remove Duplicates from Sorted Array：inplace remove，标记 deleted count
  • Rotate Array：从 k 位开始轮转数组，等于 reverse 之后再分别 reverse 0-k 和 k+1:length-1
  • Rotate Image：顺时针旋转二维数组，reverse 后在做斜对称的反转比较方便
  • Move Zeroes：第一次遍历标记 zero count ，先把数字移到正确位置，再补零
  • Merge Sorted Array：遍历两个数组，不断把第一个数组的元素往右移，同时操作 i1 i2 坐标
• traverse：遍历计算 min/max 来获得最优解的问题可以画图辅助理解，其他很多是基础的遍历操作
  • Best Time to Buy and Sell Stock II：不限次数卖卖，所以 price 做差算出 profit ，然后 > 0 的 profit 求和即可
  • Valid Sudoku：纯粹的考察 for loop，主要在于大小九宫格的遍历，board[i//3*3+j//3][i%3*3+j%3]
• binary search
  • First Bad Version：二分查找的经典题，right = mid or left = mid + 1

• delete
  • Delete Node in a Linked List：删掉当前 node 的方法，就是把 next 赋值给 curr 然后删掉 next
  • Remove Nth Node From End of List：用一个 queue 缓存 last N
• reverse
  • Reverse Linked List：经典的双指针操作，curr.next, prev, curr = prev, curr, curr.next
• merge
  • Merge Two Sorted Lists：两个指针比大小，head 存结果，curr 做合并
• 双指针
  • Palindrome Linked List：两个指针一个跳单一个跳双，跳单的时候反转链表，跳双的是为了帮跳单的指针找到中点，然后从中点开始左右对比即可
  • Linked List Cycle：两个指针一个跳单一个跳双，跳双的比跳单的每次多跑一个节点，所以如果有环，跳得快的一定可以追上跳得慢的指针。

大部分二叉树题目都可以用递归解决，思路是找到 F 使得 f(n) = F(f(n.left), f(n.right))。在某些情况下，递归本函数并不能解决问题，需要创建一个新函数来辅助做递归。

• binary tree
  • Maximum Depth of Binary Tree：f(n) = 1 + max(f(n.left), f(n.right))
  • Symmetric Tree：注意不能直接用 isSymmetric 递归 left right，左右子树各自对称并不代表整个树对称，应该是 l-r、l.left-r.right、l.right-r.left 分别对称，需要写一个 isMirror 的辅助函数
  • Binary Tree Level Order Traversal：宽度优先遍历，用 queue 遍历即可
  • Convert Sorted Array to Binary Search Tree：找到 mid 后左右递归，返回 mid 组成的 node 即可
• binary search tree
  • Validate Binary Search Tree：可以中序遍历得到所有数，然后比较是否严格递增。也可以递归的方法解决，写一个函数 isValid(node, lower, upper) 来递归遍历，return isValid(n.left, lower, n.val) and isValid(n.right, n.val, upper) and n.val < upper and and n.val > lower

• Climbing Stairs：fn = fn-1 + fn-2 ，就是斐波那契数列，加上缓存提高效率
• Best Time to Buy and Sell Stock：遍历的过程中，缓存一下当前的最小值 min，然后计算 max_profit = max(max_profit, curr - min)
• Maximum Subarray：经典题，可以按照依次计算『以当前元素结束的子数组的和的最大值』，然后找出最大值即结果，方程是 f(n) = max(f(n-1)+n, n)。
• House Robber：和求最大子数组一样，关键都在于不求当前数的最佳解，而是求『以当前元素结束的子数组的最优解』，这个方程也是 f(n) = max(f(n-2)+n, f(n-1))。

• Number of 1 Bits：通过 n &= (n-1) 删除最后的一个 1 ，直到 n == 0
• Reverse Bits：字符串方案直接 reverse 比较简单，位运算方案就一个左移一个右移重复 32 次
• Missing Number：寻找数组中缺失的数字，利用异或 aba = b 的特性可以遍历后再和 1-n 异或一遍，这样剩下的数字就是缺失的数字

• Shuffle an Array：正常 pop+random 是 O(n^2) ，可以用 Fisher–Yates 洗牌算法优化：从 n-1到1，交换 i 和 random(i-1) 这两个元素
• Min Stack：push 的时候同步缓存一个记录当前最小值的数组
• Count Primes：挨个遍历然后判断是否是质数的方法效率很低，优化的方案是先用一个数组记录 i 位置的数是否是质数，如果当前位置是质数，那么 i2,i3... 位置的数都标记为非质数，然后再找到下一个质数重复该流程
• Power of Three：判断一个数是否是 3 的整数幂。除了暴力除之外，还有两种方案，一个是看 log(n)/log(3) 是否是整数，另一个是看 n 能否被最大的 3^i 整数，比如 1162261467 % n == 0
• Roman to Integer：用一个 hash 存一下罗马数字到整数的映射，然后遍历输入的字符串，如果 i < i+1 则减去当前数，否则加上当前数
• Valid Parentheses：栈的标准操作，是开始的括号就 push ，是结束的括号就 pop 然后比较是否是一对

参考资料：

• Top Interview Questions - Easy Collection