二分查找
理解方法
知道范围猜价格。每次在可能的范围中猜最中间的那个数，然后根据反馈调整范围。
使用场景
有序数组中查找某一个值。
方法模板
begin, end = 0, len(nums) - 1
while begin <= end:
current = (begin + end) // 2
#...
例题
702 二分查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
class Solution:
def search(self, nums: List[int], target: int) -> int:
begin, end = 0, len(nums) - 1
while end >= begin:
current_index = (begin + end) // 2
current_num = nums[current_index]
if current_num == target:
return current_index
elif current_num < target:
begin = current_index + 1
else:
end = current_index - 1
return -1
双指针
理解方法
可以用小明、小红两人赛跑来帮助理解，分别代表两个指针。
使用场景
需要一遍遍历解决数组或者链表上的问题时常用。
方法模板
head, tail = 0,0
#...
例题
19 删除倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
#Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
target, tail = head, head
for i in range(n):
tail = tail.next
if tail == None:
head= head.next
return head
while(tail.next != None):
tail = tail.next
target = target.next
target.next = target.next.next
return head
广度（深度）优先遍历
理解方法
广度优先遍历用队列实现，深度优先遍历用栈来实现。
应用场景
广度优先遍历用来求距离非常好用。广度优先遍历还可以处理多起点，只需要一开始将所有起点都加入队列即可。
方法模板
对于树的遍历没有mark和处理顺序的要求，但是对于图的遍历尽量采用下面的模板进行处理：
q = []
went = [[Flase] * n for _ in range(m)]
# 起点处理和mark
process(start)
mark(start)
# 起点入队
q += [start]
while q:
p = q.pop(0)
for p_ in p.nearby:
if valid(p_) and not went[p_] and condition[p_]:
# 处理，mark，入队
process(p_)
mark(p_)
q += [p]
例题
994 腐烂橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
from typing import List
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
distance = [[-1] * n for _ in range(m)]
max_distance = 0
total = 0
q = []
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
q += [(i, j)]
distance[i][j] = 0
elif grid[i][j] == 1:
total += 1
while q:
x0, y0 = q.pop(0)
for x_, y_ in [(x0 + 1, y0), (x0 - 1, y0), (x0, y0 + 1), (x0, y0 - 1)]:
if 0<= x_ < m and 0<= y_ < n and distance[x_][y_] == -1 and grid[x_][y_] == 1:
total -= 1
distance[x_][y_] = distance[x0][y0] + 1
max_distance = max(max_distance, distance[x_][y_])
q += [(x_, y_)]
if total > 0:
return -1
else:
return max_distance
腐烂橘子问题是一个典型的多起点广度优先遍历问题。一开始把所有的腐烂起点加入队列即可。
