数组

一般数组

1. 数组的下标从 0 开始.
2. 数组的长度是数组中元素的个数.
3. 数组的长度 len 为奇数时, ⌊len/2⌋ 号单元是中间的元素; len 为偶数时, ⌊len/2⌋ 号单元是中间两个元素中的后一个.
4. 子数组: 数组中连续单元组成的数组, 类似子串的概念.
5. 前缀: 形如 [0..i] 的子数组; 后缀: 形如 [i..n-1] 的子数组.

1. 逆置. 使数组的元素倒序排列.

   # 将子数组 [0..n-1] 逆置
   # 时间 O(n), 空间 O(1)
   L.reverse(0, n):
   	cofor i = 0 to n/2-1: # 并行地
   		L.swap(i, n-1-i)
   

   L.reverse(0, n):
   	b = 0, e = n
   	while b < e:
   		L.swap(b, e)
   		++b, --e
   

2. 循环移位. 设数组是两个不相交子数组 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)
   

3. 按值删除. 删除数组中所有使得 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.unique():
	HashTable set
	for i = 0 to L.len-1:
		set.add(i)
	L.len = 0
	for val in set:
		L[L.len++] = val

1. 去重. 删除一个有序数组中值重复的元素, 使得所有元素两两不相等.

   # n = L.len; 时间 O(n), 空间 O(1)
   L.unique():
   	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
   

2. 归并. 将两个升序数组合并为一个升序数组.

   # 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++]
   

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

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

4. 偏序集的极大元 给定一些平面上的两两不同的点 (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... 从而找到所有的极大元.

5. 寻找和为给定值的两整数 给定值 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
   

6. 在两数组中寻找差为给定值的两整数 给定两数组 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
   

顺序统计量与其它

1. 下中位数 定义为一个长度为 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])
   

2. 主元素 定义为一个长度为 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
   

链表

单链表

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

1. 按值删除. 删除单链表中所有使得 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. 反向层序遍历 自下而上, 从右到左遍历二叉树.

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

2. 求二叉树高度 各给出递归和非递归的版本.

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

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

   # 使用层序遍历, 每次获取队列长度以保证严格按行遍历.
   # 空指针不可以进队列
   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
   

3. 求二叉树宽度, 即二叉树结点最多的那一层的结点数.

   # 类似上一题. 计数层序遍历
   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
   

4. 由前序序列和中序序列确定二叉树

   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
   

5. 判断二叉树是否是完全二叉树

   # 层序遍历, 将空结点一并入队.
   # 遇到第一个空结点后, 查看队列中是否还有非空结点,
   # 如果有, 说明二叉树不完全.
   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
   

6. 求二叉树的 2 度结点数

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

7. 交换二叉树的左右子树

   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
   

8. 查找前序序列的第 n 个结点

   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'
   

9. 按值删除 删除二叉树中所有使得 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)
   

10. 求所有祖先 求二叉树中某结点的所有祖先.

    # 以非递归中序 (或后序) 遍历二叉树, 每访问一个结点,
    # 栈中保存的都是它的全体祖先.
    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
    

11. 查找两结点的最近共同祖先

    # 顺序存储.
    nearest_common_ancestor1(i, j):
    	while i != j:
    		if i > j:
    			i >>= 1
    		else:
    			j >>= 1
    	return i
    

    在以父指针二叉树中查找最近共同祖先, 和单链表一样, 用错位同步法.

    # 二叉链表存储
    # 以非递归中序 (或后序) 遍历二叉树, 每访问一个结点,
    # 栈中保存的都是它的全体祖先.
    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'
    

12. 给定满二叉树的前序序列, 求后序序列

    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)
    

13. 将叶结点以 right 指针连成单链表

    # 用中序 (或前序, 后序) 遍历二叉树, 设一头结点执行连接.
    # 方法类似于中序线索化
    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
    

14. 判断二叉树相似 两棵空树相似; 空树与非空树不相似; 两棵非空二叉树相似当且仅当它们的左子树和右子树分别对应相似.

    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)
    

15. 在中序线索二叉树中寻找后序前驱

    # 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
    

16. 求带权路径长度

    # 递归算法
    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
    

17. 由表达式树求中缀表达式 不考虑运算符优先级, 统统加括号. 最外层不加括号.

    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(')')
    

树和森林

1. 森林的叶结点数

   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)
   

2. 森林的高度

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

3. 利用森林的层序序列和每个结点的度数建立森林

   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]
   

杂例

1. 求长度为奇数的最短路.

   思路: 保存并维护每个点的偶数最短路与奇数最短路.

2. 求所有 n 位回文数.

   # 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)]
   

3. [来自CDSN] Cantor 展开 (康托展开) 将 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
   

4. [来自群友 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)