刷题笔记

链表

  1. 用DummyNode简化边界情况。
  2. 双指针：左右指针，快慢指针，滑动窗口（子串问题）。

搜索问题

本质上是图的遍历问题，每个state如何遍历以找到target state的问题。如何高效遍历：

  1. DFS/Backtracking
  2. BFS

BFS

本质是在一个图中求从start到end的最短距离。

from collections import deque


def bfs(start, end):
  q = deque([start])
  # Use set to achieve O(1) time complexity.
  # Sometimes the state need to be convert to data structures
  # that can be hashed and are immutable.
  visited = set([start])
  steps = 0

  while q:
    steps += 1
    # The following line can be substitute by appending depth to the element.
    for _ in range(len(q)):
      cur = q.popleft()
      if cur == end:
        return cur

      for next_node in get_next_steps(node):
        if next_node not in visited:
          q.append(next_node)
          visited.add(cur)
  # No path from start to end.
  return None
· 面试笔记