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