leetcode 套路

leetcode 套路.md

array -> contiguous subarray with max(f(arr))

套路 - 2 max

从左往右扫，维护 2 个 max,

• 一个是 max(sub(arr[0:n]))
• 一个是 max(sub(arr[0:n], including arr[n]))

for n in arr:
  max_with_n = better([n], prev_best_with_n + [n])
  max_overall = better(prev_best, max_with_n)
return max_overall

例子：要求 max sum of subarray leetcode #53

套路 - prefix array

原理：

arr[a:b] = arr[:b] - arr[:a]

适用： f 是线性可加的，比如 sum

例子：要求 count of subarray with sum = k leetcode #560

套路 - 2 ptrs

当你要找倒数 i 个 node, 或者中间一半/三分之一/fraction 的node, 可以用 2ptrs

例子：rotate list, 需要找倒数 i 个node

leetcode #61

2 arrs

套路 - think in matrix, cartisan prod of arrs, do some searching

diff? max substring?

leetcode #718

no extra space

位运算

leetcode #136

扩展(太难，见到我就投了） leetcode #137

用输入输出参数存储需要的数据

以无损形式存（输入数据有 range, 你 out of range 就可以存更多信息）

例子：输入数据是正数，你把 nums[i] 取反，这样扫描到了第 i 个数的时候，你可以拿到本来的参数（再取反），也知道 i 在之前被标记了

hint: 如果输入数据的 range(nums) == len(nums), 意味着可能可以用 nums 做本身的 id hash

leetcode 442. Find All Duplicates in an Array

例子：某种奇怪的 xor

有损形式

例子：单次 pass, 扫过的空间都用过没用了，可以用来存信息

图：邻接矩阵与沿着边走路

• 对邻接矩阵 A, A[i][j] 表示是否有 i->j 的边，或者说 i->j 的长度为 1 的路线条数。
• (A^2)[i][j] 表示 i->j 的长度为 2 的路线条数。
• (A^3)[i][j] 表示 i->j 的长度为 3 的路线条数。
• trace(A^3) / 6 表示 i->i 的长度为 3 的路线条数 / 6 = 图中的三角形个数。

Reason about range: 线段树

pattern: 如果给定 List[(Interval, some_val)], 想要 query about aggr(f(val) for val in interval), 并要求可以 online 添加 interval, 可以用线段树。需要 aggr 有结合律。

例子	interval	val	f	aggr
给定 List[int], 求 f(i,j) = sum(List[i:j])	[i,i]	arr[i]	sum (实际没有 overlapping 所以无所谓了）	sum
给定 List[int], 求 f(i,j) = min(List[i:j])	[i,i]	arr[i]	sum (实际没有 overlapping 所以无所谓了）	min
给定 List[Interval], 求 max overlapping depth, 甚至 max overlapping interval	Interval	1	sum	max

https://leetcode.com/tag/segment-tree/

Sampling

1. Shuffle an array: Fisher-Yates algorithm

for i in reversed(range(len(arr))):
  r = rand_int_in(range(i+1))
  swap(arr[i], arr[r])

This is unbiased, forall i. forall node. P(node -> position i) = 1/n

Proof by induction. Assume arr[:n] is already shuffled, now extend to arr[:n+1]. We uniformly take i from range(n+1) and swap arr[i] and arr[n]. Provable that

• P( each node go to n ) = 1/n.
• P( old arr[n] go to any i ) = 1/n.

QED.

2. Randomly take an element from stream: reservoir sampling

a = sample already taken from first n elements
there are 1/(n+1) chance take the new element, n/(n+1) chance keep the old (a)

Proof by induction as exercise.