数组

一般数组

  1. 数组的下标从 0 开始.
  2. 数组的长度是数组中元素的个数.
  3. 数组的长度 len 为奇数时, ⌊len/2⌋ 号单元是中间的元素; len 为偶数时, ⌊len/2⌋ 号单元是中间两个元素中的后一个.
  4. 子数组: 数组中连续单元组成的数组, 类似子串的概念.
  5. 前缀: 形如 [0..i] 的子数组; 后缀: 形如 [i..n-1] 的子数组.
使数组的元素倒序排列 
# 将子数组 [0..n-1] 逆置
# 时间 O(n), 空间 O(1)
L.reverse1(0, n):
	b = 0, e = n
	while b < e:
		L.swap(b, e)
		++b, --e

L.reverse2(0, n):
	cofor i = 0 to n/2-1: # 并行地
		L.swap(i, n-1-i)
设数组是两个不相交子数组 A, B 的并置, 要求将数组由 AB 变为 BA. 
# 使用三次逆置, 将子数组 A = [0..i-1] 和 B = [i..n-1] 交换位置
# AB → B-1A-1 → BA
# 时间 O(n), 空间 O(1)
L.cyclic_shift(i):
	reverse(0, n)
	cobegin: # 并行地
		reverse(0, i)
		reverse(i, n)
删除数组中所有使得 f(x) == True 的值 x. 假设 f 的时空复杂度均是 O(1). 
# n = L.len; 时间 O(n), 空间 O(1)
L.remove_if1(f):
	passed = 0	# f(x) == False 的元素计数
	for i = 0 to L.len-1:
		if !f(L[i]):
			L[passed++] = L[i]
	L.len = passed

# 时间 O(n), 空间 O(1)
L.remove_if2(f):
	removed = 0	# f(x) == True 的元素计数
	for i = 0 to L.len-1:
		if f(L[i]):
			++removed
		else:
			L[i-removed] = L[i]
	L.len -= removed
逆置 循环移位 按值删除

有序数组

  1. 有序数组, 是指升序或降序的数组. 升序数组是任意相邻两个元素满足 L[i] ≤ L[i+1] 的数组. 降序数组是任意相邻两个元素满足 L[i] ≥ L[i+1] 的数组.
  2. 一般来说, 通过排序能实现的算法, 也可以通过散列或计数来实现. 例如数组无序时, 去重操作可以实现如下:
删除一个有序数组中值重复的元素, 使得所有元素两两不相等. 
# n = L.len; 时间空间均 O(n)
L.unique1():
	HashTable set
	for i = 0 to L.len-1:
		set.add(i)
	L.len = 0
	for val in set:
		L[L.len++] = val

# n = L.len; 时间 O(n), 空间 O(1)
L.unique2():
	if L.len == 0:
		return
	i = 0 # i 指向数组的*无重复元素前缀*的最后一个单元
	for j = 1 to L.len-1:
		if L[i] != L[j] and ++i != j:
			L[i] = L[j]
	L.len = i+1
将两个升序数组合并为一个升序数组. 
# m = M.len, n = N.len; 时间空间均 O(m+n)
merge(M, N):
	A = new array[M.len+N.len]
	i = j = k = 0
	while i < M.len and j < N.len:
		if M[i] <= N[j]:
			A[k++] = M[i++]
		else:
			A[k++] = N[j++]
	# 下面两个循环只有一个执行
	while i < M.len:
		A[k++] = M[i++]
	while j < N.len:
		A[k++] = N[j++]

给定一个长度为 n 的整数数组, 求数组中未出现的最小正整数.

思路：先排序, 然后顺序遍历数组, 依次在数组中查找正整数 1, 2, 3... 即可. 根据的 2, 也可以开辟一个长度为 n 的数组, 在 a[i]记录数字 i 出现的次数, 通过计数实现算法.

给定一些平面上的两两不同的点 (x[i], y[i]), 规定 (x[i], y[i]) < (x[j], y[j]) 当且仅当 x[i] < x[j] 且 y[i] < y[j]. 求极大元, 即求所有的点 (x[i], y[i]), 使得不存在其它的点满足 (x[j], y[j]) > (x[i], y[i]).

思路：将所有点关于 x 按降序排序, 取第一个点 (x[0], y[0]), 由于它关于 x 是最大的, 所以它是一个极大元. 接着正向扫描数组, 寻找下一个满足 y[i1] > y[0] 的下标 i1. 可以证明 (x[i1], y[i1]) 也是一个极大元. 接下来再寻找下一个满足 y[i2] > y[i1] 的下标 i2... 从而找到所有的极大元.

给定值 val, 求 i, j (允许 i == j), 使得 L[i] + L[j] == val. 
# 先排序 (时空复杂度由排序方法决定), 再执行下面的代码
# n = L.len; 时间 O(n), 空间 O(1)
L.two_sum(val):
	i = 0, j = L.len-1
	while i <= j: # 不允许 i == j 时, 写 i < j
		if L[i] + L[j] == val:
			return i, j
		elif L[i] + L[j] < val:
			++i
		else:
			--j
	return None
给定两数组 A, B 和值 val, 求 i, j, 使得 A[i] - B[j] == val. 
# 先排序, 再执行下面的代码
two_diff(A, B, val):
	i = j = 0
	while i < A.len and j < B.len:
		if A[i] - B[j] == val:
			return i, j
		elif A[i] - B[j] < val:
			++i
		else:
			++j
	return None
去重 归并 mex 偏序集的极大元 寻找和为给定值的两整数 在两数组中寻找差为给定值的两整数

顺序统计量与其它

下中位数 定义为一个长度为 n 的升序数组中 下标为 ⌊(n-1)/2⌋ 的元素. 类似地, 上中位数定义为该数组中下标为 ⌈(n-1)/2⌉ 的元素. 例如, n == 5 时 ⌊(n-1)/2⌋ == 2, ⌈(n-1)/2⌉ == 2; 上, 下中位数都是中间的元素. n == 6 时 ⌊(n-1)/2⌋ == 2, ⌈(n-1)/2⌉ == 3. 上, 下中位数分别是中间两个元素的后一个与前一个. 已知两个长度为 n 的升序序列. 求它们合并后的升序序列的下中位数. 
# n = L1.len; 时间 O(log n), 空间 O(1)
# 设 m1, m2 是两序列 L1, L2 的下中位数.
# 如果两个序列都只有一个元素, 则较小者就是所求的下中位数.
# 如果 m1 == m2, 则 L[m1] 就是所求的下中位数;
# 如果 m1 < m2, 则舍弃 L1 中较小的一半和 L2 中较大的一半,
# 舍弃后仍保持 L1.len == L2.len;
# 如果 m1 > m2, 则舍弃 L1 中较大的一半和 L2 中较小的一半,
# 舍弃后仍保持 L1.len == L2.len.
median(L1, L2):
	if L1.len == 0:
		return None
	diff = L1.len-1
	lo1 = lo2 = 0
	hi1 = hi2 = diff
	while diff > 0:
		m1 = lo1 + diff/2
		m2 = lo2 + diff/2
		if L1[m1] == L2[m2]:
			return L1[m1]
		elif L1[m1] < L2[m2]:
			hi2 = m2
			# 元素奇数个时加 0, 否则加 1
			lo1 = m1 + diff % 2
		else:
			hi1 = m1
			lo2 = m2 + diff % 2
		diff = hi1 - lo1
	return min(L1[lo1], L2[lo2])
主元素 定义为一个长度为 n 的数组中出现次数大于 n/2 的元素. 显然主元素如果存在, 必惟一. 求给定数组的主元素. 
# n = L.len; 时间 O(n), 空间 O(1)
# 如果 candidate 是主元素, 那么数组必能分成若干段,
# 使得 candidate 是最后一段的主元素, 且前面的每一段中 candidate
# 恰好占了半数
L.marjority_number():
	if L.len == 0:
		return None
	candidate = L[0]
	count = 1
	for i = 1 to L.len-1:
		if L[i] == candidate:
			++count
		elif count > 0:
			--count
		else:
			candidate = L[i]	# 改变候选
			count = 1			# 重新计数
	# 计数 candidate 出现次数, 确认是否是主元素
	if count > 0:
		count = 0
		for i = 0 to L.len-1:
			if L[i] == candidate:
				++count
		if count > n//2:
			return candidate
	return None
下中位数 主元素

链表

单链表

若无特别说明, 总假定链表不含头结点.

删除单链表中所有使得 f(x) == True 的值 x. 假设 f 的时空复杂度均是 O(1). 
# n = L.len; 时间 O(n), 空间 O(1)
# 用指针 p 遍历链表
L.remove_if1(f):
	Node *p = head
	if !p:
		return
	while p->next:
		if f(p->next->val):
			tmp = p->next
			p->next = tmp->next
			delete tmp
		else:
			p = p->next
按值删除

二叉树

自下而上, 从右到左遍历二叉树.

思路：设一栈. 按正常次序进行层序遍历, 结点出队后先入栈; 所有结点入栈后再依次弹出并访问.

思路1：递归

height_rec(root):
	if !root:
		return 0
	return 1+max(height_rec(root->left), height_rec(root->right))

思路2：用栈实现中序 (或后序) 遍历, 最大栈长度即为二叉树的高度. 不可用 "三位一体" 写法.

思路3：层序遍历

# 使用层序遍历, 每次获取队列长度以保证严格按行遍历.
# 空指针不可以进队列
height_nonrec(root):
	level = 0
	if root:
		queue.enqueue(root)
	while queue:
		# 如果 queue 对象没有取得长度的方法, 可设一计数变量 len
		# 随出队入队操作而变化.
		cur_len = queue.len
		loop cur_len:
			root = queue.dequeue()
			if root->left:
				queue.enqueue(root->left)
			if root->right:
				queue.enqueue(root->right)
		++level
	return level
即二叉树结点最多的那一层的结点数 
# 类似上一题. 计数层序遍历
width(root):
	max = 0
	if root:
		queue.enqueue(root)
	while queue:
		if queue.len > max:
			max = queue.len
		loop max:
			root = queue.dequeue()
			if root->left:
				queue.enqueue(root->left)
			if root->right:
				queue.enqueue(root->right)
	return max

pre[], in[] # 前序和中序序列
init_pre_in(pre_lo, pre_hi, in_lo, in_hi):
	if pre.lo <= pre.hi:
		return NULL
	root = new BinaryTreeNode(pre[pre_lo], NULL, NULL)
	i = in_lo
	while in[i] != root->val:
		++i
	left_len = i - in_lo
	right_len = in_hi - i
	if left_len > 0:
		root->left = init_pre_in(
			pre_lo+1, pre_lo+left_len, in_lo, in_lo+left_len-1)
	if right_len > 0:
		root->right = init_pre_in(
			pre_hi-right_len+1, pre_hi, in_hi-right_len+1, in_hi)
	return root

# 层序遍历, 将空结点一并入队.
# 遇到第一个空结点后, 查看队列中是否还有非空结点,
# 如果有, 说明二叉树不完全.
is_complete(root):
	if !root:
		return True
	queue.enqueue(root)
	while queue:
		root = queue.dequeue()
		if root:
			queue.enqueue(root->left)
			queue.enqueue(root->right)
		else:
			break
	while queue:
		root = queue.dequeue()
		if root:
			return False
	return True

n2(root):
	if !root:
		return 0
	return n2(root->left) + n2(root->right) +
		(root->left and root->right ? 1 : 0)

swap_left_right(root):
	if root:
		swap_left_right(root->left)
		swap_left_right(root->right)
		tmp = root->left
		root->left = root->right
		root->right = tmp

find_nth_preorder_node(root):
	cnt = 0
	stack.push(NULL)
	while root:
		++cnt
		if cnt == n:
			return root->val
		if root->right:
			stack.push(root->right)
		if root->left:
			root = root->left
		else:
			root = stack.pop()
	return 'not found'
删除二叉树中所有使得 f(x) == True 的值 x 所在的根结点的子树. 假设 f 的时空复杂度均是 O(1). 
# 按层序查找待删结点
remove_if(root, f()):
	if !root:
		return
	if f(root->val):
		remove(root) # 删除整棵树
	queue.enqueue(root)
	while queue:
		root = queue.dequeue()
		if root->left:
			if f(root->left->val):
				remove(root->left)
			else:
				queue.enqueue(root->left)
		if root->right:
			if f(root->right->val):
				remove(root->right)
			else:
				queue.enqueue(root->right)
求二叉树中某结点的所有祖先. 
# 以非递归中序 (或后序) 遍历二叉树, 每访问一个结点,
# 栈中保存的都是它的全体祖先.
ancestors(root, node):
	while True:
		if root:
			stack.push(root)
			root = root->left
		elif stack:
			root = stack.pop()
			#### visit()
			if root == node:
				while stack:
					print(stack.pop()->val)
				break
			####
			root = root->right
		else:
			break

思路1：顺序存储.

nearest_common_ancestor1(i, j):
	while i != j:
		if i > j:
			i >>= 1
		else:
			j >>= 1
	return i

思路2：在父指针树中查找最近共同祖先, 和单链表一样, 用错位同步法.

思路3：二叉链表存储

# 以非递归中序 (或后序) 遍历二叉树, 每访问一个结点,
# 栈中保存的都是它的全体祖先.
nearest_common_ancestor2(root, p1, p2):
	first = True
	while True:
		if root:
			stack.push(root)
			root = root->left
		elif stack:
			root = stack.pop()
			#### visit()
			if root == p1 or root == p2:
				if first:
					stack1 = stack.copy()
					first = False
				else:
					# 使两栈长度相等
					while stack.len > stack1.len:
						stack.pop()
					while stack1.len > stack.len:
						stack1.pop()
					# 两栈长度相等时, 比较栈顶元素
					while stack.top() != stack1.top():
						stack.pop()
						stack1.pop()
					return stack.top()
			####
			root = root->right
		else:
			break
	return 'one of node p1, p2 not found'

pre[], post[]
pre2post(pre_lo, pre_hi, post_lo, post_hi):
	if pre_hi >= pre_lo:
		# 后序的最后一个结点就是前序的第一个结点
		post[post_hi] = pre[pre_lo]
		half = (pre_hi-pre_lo) >> 1
		pre2post(pre_lo+1, pre_lo+half, post_lo, post_lo+half-1)
		pre2post(pre_lo+half+1, pre_hi, post_lo+half, post_hi-1)

# 用中序 (或前序, 后序) 遍历二叉树, 设一头结点执行连接.
# 方法类似于中序线索化
BinaryTreeNode *pre

visit(root):
	if is_leaf(root):
		pre->right = root
	pre = root

thread_leaf(root):
	pre = head = new BinaryTreeNode(?, NULL, NULL)
	traverse(root, visit) # 任一遍历方法
	# 如果不需要头结点, 可以删除之
	tmp = head
	head = head->right
	delete tmp
两棵空树相似; 空树与非空树不相似; 两棵非空二叉树相似当且仅当它们的左子树和右子树分别对应相似. 
similar(root1, root2):
	if !root1 and !root2:
		return True
	if !root1 or !root2:
		return False
	return similar(root1->left, root2->left) and
			similar(root1->right, root2->right)

# p 的后序前驱是其最后一个子结点. 若 p 是叶子结点,
# 则它是某棵树的最左下叶子结点. 先找到 p 的中序前驱  s, 若 s 有左子结点,
# 则 s->left 就是 p 的后序前驱; 否则再找 s 的中序前驱,
# 直到 s 有左子结点, 或者 s 无中序前驱为止.
post_prev(root, node):
	if !node->right_thread: # 有右子结点
		return node->right
	if !node->left_thread: # 有左子结点
		return node->left
	while node->left_thread and node->left: # 有中序前驱
		node = node->left
	if !node->left_thread # 有左子结点
		return node->left
	else: # 无中序前驱
		return NULL

# 递归算法
wpl = 0
WPL(root, depth):
	if root:
		if is_leaf(root):
			wpl += root->weight * depth
		else:
			WPL(root->left, depth+1)
			WPL(root->right, depth+1)

# 又一递归算法, 注意 WPL 等于分支结点权和.
wpl = 0
weight(root):
	if !root:
		return 0
	if is_leaf(root):
		return root->weight
	w = weight(root->left) + weight(root->right)
	wpl += w
	return w

# 层序遍历
WPL_levelorder(root):
	wpl = 0
	depth = 0
	if root:
		queue.enqueue(root)
	while queue:
		cur_len = queue.len
		loop cur_len:
			root = queue.dequeue()
			if is_leaf(root):
				wpl += root->weight * depth
			if root->left:
				queue.enqueue(root->left)
			if root->right:
				queue.enqueue(root->right)
			++depth
	return wpl
不考虑运算符优先级, 统统加括号. 最外层不加括号. 
inorder_expr(root):
	if root:
		if if_leaf(root):
			print(root->val)
		else:
			do_inorder_expr(root->left)
			print(root->val)
			do_inorder_expr(root->right)

do_inorder_expr(root):
	if root:
		if is_leaf(root):
			print(root->val)
		else:
			print('(')
			inorder_expr(root->left)
			print(root->val)
			inorder_expr(root->right)
			print(')')
反向层序遍历 求二叉树高度 求二叉树宽度 由前序序列和中序序列确定二叉树 判断二叉树是否是完全二叉树 求二叉树的 2 度结点数 交换二叉树的左右子树 查找前序序列的第 n 个结点 按值删除 求所有祖先 查找两结点的最近共同祖先 给定满二叉树的前序序列, 求后序序列 将叶结点以 right 指针连成单链表 判断二叉树相似 在中序线索二叉树中寻找后序前驱 求带权路径长度 由表达式树求中缀表达式

树和森林

count_leaves(root):
	if !root:
		return 0
	elif !root->first_child:
		return 1 + count_leaves(root->next_sibling)
	return count_leaves(root->first_child)
		+ count_leaves(root->next_sibling)

height(root):
	if !root:
		return 0
	return max(1+height(root->first_child),
		height(root->next_sibling))

init_levelorder_deg(val[], deg[], n):
	nodes = new TreeNode[n](val[i], NULL, NULL)
	j = 0
	for i = 0 to n-1:
		d = deg[i]
		if d--:
			nodes[i]->first_child = nodes[++j]
			while d--:
				nodes[j]->next_sibling = nodes[j+1]
				++j
	return nodes[0]
来自群友的变态图论问题: 有向图中有 4 个节点, 女节点入度小于等于2, 出度为0; 男节点入度为 0, 出度为1; futa节点入度小于等于 2, 出度小于等于1; 男娘节点入度小于等于 1, 出度小于等于1. 要求不存在孤立点, 这样的图有多少个? 假如区分 2 个洞, 这样的图又有多少个? 
# 没有区分两个洞时, 答案是 12, 区分时答案是 40
import numpy as np

count = 0
for n in range(2**16):
    bits = [int(d) for d in format(n, 'b').rjust(16, '0')]
    a = np.array(bits).reshape((4, 4))
    # 不可自指
    if any(a[i][i] == 1 for i in range(4)):
        continue
    row_sum = a.sum(axis=0) # 出度
    col_sum = a.sum(axis=1) # 入度
    # 无孤立点
    if any(row_sum[i] == 0 and col_sum[i] == 0 for i in range(4)):
        continue
    # 女节点
    if col_sum[0] > 2 or row_sum[0] > 0:
        continue
    # 男节点
    if col_sum[1] > 0 or row_sum[1] != 1:
        continue
    # futa 节点
    if col_sum[2] > 2 or row_sum[2] > 1:
        continue
    # 男娘节点
    if col_sum[3] > 1 or row_sum[3] > 1:
        continue
    #print(a)
    add = 1
    # 区分女节点的两个洞
    if col_sum[0] > 1:
        add *= 2
    # 区分 futa 节点的两个洞
    if col_sum[2] > 1:
        add *= 2
    count += add

print(count)
森林的叶结点数 森林的高度 利用森林的层序序列和每个结点的度数建立森林 本子问题

杂例

思路: 保存并维护每个点的偶数最短路与奇数最短路. 
# palindromes(n, 1) 返回 n 位的回文数
def palindromes(n, start):
    if n == 1:
        return [i for i in range(10)]
    if n == 2:
        return [11*i for i in range(start, 10)]
    return [i*10**(n-1) + 10*k + i for i in range(start, 10) for k in palindromes(n-2, 0)]
[来自CDSN] 将 1 到 n 的全排列按字典序列出, 比如 1 到 4 的全排列是: 
1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
...
4 3 2 1
问题: 给定一个排列, 求它在列表中的第几位. 反之, 给定它在列表中的位次, 求这个排列. 
# 对于一个排列, 如 2 4 1 3, 它是以 2 开头的, 所以前面还有以 1 开头的 3! 个排列,
# 故 num += 6. 再看它的后三位是由 {4, 1, 3} 的排列组成的,
# 前面还有以 1 开头和以 3 开头的 2 * 2! = 4 个排列, 故 num += 4.
# 再看它的后两位是由 {1, 3} 的排列组成的, 1 已经是最小的数字,
# 前面没有其它排列, 故 num += 0. 最后由于列表的位次是从 1 开始的, 因此再给 num 加 1,
# 得到 num = 6 + 4 + 1 = 11.
def perm2num(arr):
    n = len(arr)
    num = 0
    perms = 1
    for i in range(n-2, -1, -1):
        num += sum(perms for j in range(i+1, n) if arr[j] < arr[i])
        perms *= n - i # perms = (n-i)! 是 arr[i+1:n] 的排列数
    return num + 1

def num2perm(n, num):
    arr = []
    candidate = [i+1 for i in range(n)] # 待插入的数
    perms = math.factorial(n)
    for i in range(n):
        perms //= n-i
        index = (num - 1) // perms
        num -= index * perms
        arr.append(candidate.pop(index))
    return arr
[来自群友 Eyelids] 给定 `n`, `S` 是全体 `n` 维 01 向量的子集，满足 `S` 中任两个元素的距离 `≥3`，`|S|` 的最大值是？ （距离就是两个向量相减后非零分量的个数） 
# 答案：https://oeis.org/A054243
# 这题本质是计算距离 = 3 的汉明码序列 https://oeis.org/A075926

buf = []
best = 0

def dist(a, b):
    res = 0
    n = a ^ b
    while n:
        res += 1
        n &= n - 1 # 消去最右边的一个 1
    return res

def dfs(n):
    global best
    if len(buf) > best:
        best = len(buf)
    for i in range(0, n):
        if all(dist(i, j) >= 3 for j in buf):
            buf.append(i)
            dfs(n)
            return

def search(n):
    global best
    best = 0
    buf.clear()
    buf.append(0)
    dfs(n)
    print(best, buf)

def check_answer(l):
    print([dist(a, b) for a in l for b in l if a != b])


search(2**7)
5个人过河，他们分别是妈妈、爸爸、哥哥、妹妹、路人。 妈妈是魅魔单独与男性时会对男性进行侵犯； 爸爸是鬼父单独与妹妹时会进行性行为； 哥哥是德国骨科与妹妹单独时会进行性行为； 妹妹也是德国骨科单独跟哥哥时会进行性行为，但妹妹身体弱不能开船； 路人是基佬单独与哥哥时会进行侵犯； 只有一艘船，每次只能坐两个人，船不会自己回来，过去就要有人开回来； 如何在不发生任何性行为的情况下，5个人成功到对面？ 
danger = [0b11000, 0b10100, 0b10001, 0b01010, 0b00110, 0b00101]
available_moves = [0b10000, 0b01000, 0b00100, 0b00001, 0b10010, 0b01100, 0b01001, 0b00011]
all_people = 0b11111
people = all_people
max_len = 7

def explain(v):
    buf = []
    if v & 0b10000:
        buf.append('妈妈')
    if v & 0b01000:
        buf.append('爸爸')
    if v & 0b00100:
        buf.append('哥哥')
    if v & 0b00010:
        buf.append('妹妹')
    if v & 0b00001:
        buf.append('路人')
    return ','.join(buf)

def solution():
    global people
    people = all_people
    moves = []
    def dfs(depth):
        global people
        if depth > max_len:
            return
        if people == 0:
            return print([explain(v) for v in moves])
        for move in available_moves:
            if len(moves) > 0 and move == moves[-1]:
                continue
            boat_here = len(moves) % 2 == 0
            if boat_here and (people & move == move):
                people ^= move
                if (people not in danger) and (all_people ^ people not in danger):
                    moves.append(move)
                    dfs(depth + 1)
                    moves.pop()
                people ^= move
            if not boat_here and ((all_people ^ people) & move == move):
                people ^= move
                if (people not in danger) and (all_people ^ people not in danger):
                    moves.append(move)
                    dfs(depth + 1)
                    moves.pop()
                people ^= move
    dfs(0)

solution()
求长度为奇数的最短路 求所有 n 位回文数 Cantor 展开 Hamming 距离 过河问题