Leetcode 基础题

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

数组

  • set/hash:常用于计数、去重
  • 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

链表

  • delete
  • reverse
    • Reverse Linked List:经典的双指针操作,curr.next, prev, curr = prev, curr, curr.next
  • merge
  • 双指针
    • Palindrome Linked List:两个指针一个跳单一个跳双,跳单的时候反转链表,跳双的是为了帮跳单的指针找到中点,然后从中点开始左右对比即可
    • Linked List Cycle:两个指针一个跳单一个跳双,跳双的比跳单的每次多跑一个节点,所以如果有环,跳得快的一定可以追上跳得慢的指针。

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

  • binary tree
  • 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 然后比较是否是一对

参考资料: