唠唠闲话

本篇内容:位运算二叉树遍历二分查找特殊数据结构排序算法最短路以及动态规划


位运算

数环

  1. 位运算逐位进行,可等同看成数环 Z2n\mathbb{Z}_2^n (Z2\mathbb{Z}_2 直和环)上的运算

  2. Z2n\mathbb{Z}_2^n 为交换幺环,以 0 为零元, -1 为单位元(简记为 I),所有元素加法阶为 2

    位运算 数域操作
    异或运算 ^ 环上加法
    与运算 & 环上乘法
    非运算 ~ ~n 等同于 n ^ I
    或运算 | a | b = a ^ b ^ (a & b)

    或运算推导过程如下:
    a | b = ~(~a & ~b) = I ^ (I ^ a) & (I ^ b) = a ^ b ^ (a & b)

  3. 位运算左移 << 和 右移 >>

知识技巧

  1. 异或技巧

    1
    2
    3
    def singleNumber(nums: List[int]) -> int:
    from functools import reduce
    return reduce(lambda x, y: x ^ y, nums)
  2. 减一技巧

    • 减一运算将最低位 1 化为 0,并将该位置以下的 0 化为 1,例如 11|1000 -> 11|0111
    • 延伸应用:n & n - 1 将最低位 1 以上不变,以下(含)全化 0,例如 11100 -> 11000 -> 10000 -> 0
    • 问题 231. 2 的幂,判断是否 2 的幂次
    1
    2
    3
    # 当且仅当 n 为 2 的幂次时,数值化为 0
    def isPowerOfTwo(n: int) -> bool:
    return n > 0 and (n & n - 1) == 0
    1
    2
    3
    4
    5
    6
    7
    # 每次进行 `n & n-1`,二进制数中的 1 数目减一
    def hammingWeight(n: int) -> int:
    ret = 0
    while n:
    n &= n - 1
    ret += 1
    return ret
  3. 对偶地,加一技巧

    • 加一运算将最低位 0 化为 1,并将该位置以下的 1 化为 0,例如 110|011 -> 110|100
    • 延伸:n & n + 1 将最低位 0 以下的部分截断(化 0),例如 110|011 -> 11000
  4. 分治技巧:

    • 构造 01 序列 s
    • 与运算 s & n 提取 n 在序列取值 1 的位置的信息,例如 1100 & n 提取四位整数 n 的前两位
    • 位移运算 >>, << 移动结果,例如 (1100 & n) >> 2 提取 n 的前两位,并移动到个位
    • 异或运算 ^ 合并提取内容,例如 (1100 & n) >> 2 ^ ((0011 & n) << 2)n 的前两位与后两位交换
  5. 分治应用题,190. 颠倒二进制位,图片来自负雪明烛
    20220225104430

    • 利用分治思想,32=2532=2^5 位整数需互换 5 次,先理解 2,4,8 位的代码,再来看 32 位
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    b = lambda i: int(i, 2)
    def reverse_bits_2(n: int)-> int:
    """二位整数互换"""
    return n >> 1 ^ (n << 1 & b("10")) # 10

    def reverse_bits_4(n: int)-> int:
    """四位整数互换"""
    n = n >> 2 ^ (n << 2 & b("1100")) # 1100
    n = n >> 1 & b("0101") ^ (n << 1 & b("1010")) # 10 的重复
    return n

    def reverse_bits_8(n: int)-> int:
    """八位整数互换"""
    n = n >> 4 ^ (n << 4 & b("11110000")) # 11110000
    n = n >> 2 & b("00110011") ^ (n << 2 & b("11001100")) # 1100 的重复
    n = n >> 1 & b("01010101") ^ (n << 1 & b("10101010")) ## 10 的重复
    return n

    def reverseBits(n: int) -> int:
    n = n >> 16 ^ (n << 16 & 0xffff0000) # 16 个 1
    n = n >> 8 & 0x00ff00ff ^ (n << 8 & 0xff00ff00) # 8 个 1
    n = n >> 4 & 0x0f0f0f0f ^ (n << 4 & 0xf0f0f0f0) # 11110000...
    n = n >> 2 & 0x03030303 ^ (n << 2 & 0xcccccccc) # 1100...
    n = n >> 1 & 0x55555555 ^ (n << 1 & 0xaaaaaaaa) # 1010
    return n

其他知识

  1. 2, 8, 16 进制的单词分别为 binary, octal, hexadecimal,在 Python 中的相关函数如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    # 十进制 -> 其他进制(字符串)
    bin(123) # '0b1111011' | 十进制 -> 二进制
    oct(123) # '0o173' | 十进制 -> 八进制
    hex(123) # '0x7b' | 十进制 -> 十六进制
    # 其他进制(字符串) -> 十进制
    int("011") # 11 | 十进制字符串 -> 十进制整数
    int("11", 3) # 4 | 三进制字符串 -> 十进制
    int("11", 2) # 3 | 二进制字符串 -> 十进制
    int("0b11", 2) == 0b11 # True | 可直接书写
  2. 数值编码,参考 CSDN

    • 计算机中,有符号整数有三种存储方式,原码,反码和补码
    • 原码:用最高位表示符号位,‘1’表示负号,‘0’表示正号,其他位存放该数的二进制的绝对值
      • 整数 0 分为 +0-0
      • 用原码做正负数的加法运算:0001 + 1001 = 1010 => 1 + (-1) = -2,出现问题
      • 原码虽然直观易懂,易于正值转换,但实现加减法的运算规则太复杂,于是反码来了
    • 反码:正数的反码还是等于原码,负数的反码就是他的原码除符号位外,按位取反
      • 比如 -3 = 1100, 0 = 0000 = 1111
      1
      2
      3 = 0(011) => -3 = 1(110) = 1100
      0 = 0(000) => -0 = 1(111) = 1111
      • 此时仍存在运算错误的问题
      1
      2
      1100 + 0001 = 1101 = -(0010) => -3 + 1 = -2
      1100 + 1001 = 1101 = -(0010) => -3 + (-6) = -2
    • 补码:负数的补码等于他的原码自右向做,第一个‘1’及其右边的‘0’保持不变,左边的各位按位取反
      • 等价刻画:正数的反码还是等于原码,负数的补码是其反码 + 1
      • 此外,正数和负数互为彼此的补码,0 的表达方式唯一
      1
      2
      3
      0110 => -(0110) = 1010
      1010 => -(1010) = 0110
      0000 => 0000
      • 补码的数学运算
      1
      2
      3
      4
      5
      6
      # -1 + 1 = 0
      1111 + 0001 = 0000 # 进位丢掉
      # -2 + 1 = -1
      1110 + 0001 = 1111
      # -1 + 2 = 1
      1111 + 0010 = 0001
    • 由补码原理,负数位移运算 >> 也是下整除
    1
    2
    3
    4
    # 负数右移,左侧补 1
    # 1101 -> 1110 => -(0011) -> -(0010) => -3 -> -2
    -3 >> 1 == -2
    -1 >> 1 == -1 # 下整除
  3. Python 位运算的优先级

    • 单目运算符 ~ 的优先级高于四则运算
    • >>, << 的优先级比 ==, !=, and, or, &, ^, | 高,比四则运算低
    1
    2
    3
    4
    5
    6
    1 == 1 << 1 # 返回 False
    2 or 1 << 2 # 返回 2,相当于 2 or 2
    (2 or 1) << 2 # 返回 8, 相当于 2 << 2
    1 + 2 << 3 # 返回 24,相当于 3 << 3
    1 & 1 << 3 # 返回 0,相当于 1 & 8
    (1 & 1) << 3 # 返回 8,相当于 1 << 3
  4. Julia 位运算的优先级

    • >>, << 的优先级比 ==, !=, &&, ||, &, ⊻, | 高,与乘法运算同级
    • 也即: 1 + 2 << 3 在 Julia 中取值为 17,在 Python 中取值为 24

二叉树遍历

宽度优先遍历

树的三种宽度遍历方式,对应三道 LeetCode 习题:144. 二叉树的前序遍历94. 二叉树的中序遍历145. 二叉树的后序遍历

  1. 先序遍历(Python)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def traversal(root: TreeNode) -> List[int]:
    if not root: return []
    ans, stack = [], [root]
    while stack:
    node = stack.pop()
    ans.append(node.val)
    if node.right:
    stack.append(node.right)
    if node.left: # 左节点优先
    stack.append(node.left)
    return ans
  2. 先序遍历 + 中序遍历(Julia)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    ## Julia 模板
    traversal(::Nothing) = Int[]
    function traversal(root::TreeNode)::Vector{Int}
    res, stack = Int[], []
    while !isempty(stack) || !isnothing(root)
    while !isnothing(root)
    push!(stack, root)
    ## preorder traversal
    root = root.left
    end
    root = pop!(stack)
    ## inorder traversal
    root = root.right
    end
    res
    end
  3. 先序遍历 + 中序遍历 + 后序遍历(Python)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    def Traversal(root: TreeNode) -> List[int]:
    if not root: return []
    res, stack, pre = [], [], None
    while root or stack:
    while root: # 访问到最左节点
    stack.append(root)
    # 先序遍历,准备访问左子树
    root = root.left
    root = stack[-1] # 到达最左节点
    if not root.right or root.right == pre: # 右节点为空或访问过
    # 后序遍历,左右子树访问完毕
    pre, root = stack.pop(), None
    else:
    # 中序遍历,准备访问右子树
    root = root.right
    return res

Morris 遍历

暂略,有需要再学习

序列构造树

递归解法比较简单,难点是迭代解法。

  1. 先序遍历 + 中序遍历,反推二叉树,问题 105

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    def buildTree(preorder: List[int], inorder: List[int]):
    root = TreeNode(preorder[0])
    stack, j, n = [root], 0, len(preorder)
    for i in range(1, n):
    node = TreeNode(preorder[i]) # 创建节点
    if stack[-1].val != inorder[j]: # 栈顶不是最左节点
    stack[-1].left = node
    stack.append(node) # 继续向左
    else: # 栈顶是最左节
    while len(stack) and inorder[j] == stack[-1].val: # 依次消除栈顶元素
    j += 1
    top = stack.pop()
    top.right = node # 合适位置向右
    stack.append(node)
    return root
  2. 后序遍历 + 中序遍历,反推二叉树,问题 106
    (暂略)

二分查找

  1. 自编模板,寻找左边界

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    def search_left_border(left, right, key):
    """搜索 key(i)==true 的左边界"""
    ## e.g. search_left_border(0, 10, lambda i:i>3) | returns 4
    while left <= right:
    mid = (left + right) >> 1
    if key(mid): # 位置正确
    right = mid - 1
    else:
    left = mid + 1
    return left
  2. 使用函数库

    1
    2
    3
    from bisect import bisect_left
    bisect_left([], 0) == 0
    bisect_left([1, 2, 2], 2) == 1

特殊数据结构

前缀树

  1. 简单说,就是根据输入的字符信息,构造多叉树,比如输入单词 "sea","sells","she"(图片来自 huwt
    20220325175450

  2. 树本身不存储信息,每次检查单词时,根据能否切换分支进行判断,具体问题可以添加结尾标记 isend = true 等信息。

  3. 相关 LeetCode 问题:前缀树 208最长前缀 720

  4. 习题 720,给出单词列表中,逐步添加得到的最长单词(Julia 代码)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    function longest_common_word!(words::Vector{String})::String
    root, res = Dict{Char, Dict}(), ""
    for word in sort!(words, by=length)
    node, n = root, length(word)
    for (i, c) in enumerate(word)
    if haskey(node, c)
    node = node[c]
    elseif i == n
    node[c] = Dict{Char, Dict}() ## add new child
    res = word
    else
    break
    end
    end
    end
    res
    end

线段树

线段树的三个关键步骤,对应 LeetCode 习题 307,计算可变数据的区间和

  • 构造线段树
  • 更新线段树
  • 查找区间信息
  1. 构造线段树

    • 将数据视为叶子节点
    • 根节点与左右子节点的索引关系为 k -> (2 * k, 2 * k + 1)
    • 根节点为左右子节点之和 nums[i] = nums[2 * i] + nums[2 * i + 1]
      Python 代码
    1
    2
    3
    4
    5
    6
    7
    class SegmentTree:
    def __init__(self, nums: List[int]):
    self.n = n = len(nums)
    self.tree = tree = [0] * n + nums # 线段树 ST 长度为2n
    for i in range(n-1, 0, -1): # [1, n-1] 倒序添加,子节点之和
    # ST[2i] 和 ST[2i+1] 分别为 ST[i] 的左右子节点
    tree[i] = tree[i << 1] + tree[i << 1 | 1]
  2. 更新索引信息,从叶子节点逐步往回

    1
    2
    3
    4
    5
    6
    7
    def update(self, index: int, val: int) -> None:
    index += self.n # nums下标转换到 ST 下标
    delta = val - self.tree[index] # 变更值
    while index: # 自下而上进行更新
    self.tree[index] += delta
    index >>= 1
    return
  3. 获取区间和

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    def sumRange(self, left: int, right: int) -> int:
    # nums下标转换到 ST 下标
    left += self.n
    right += self.n
    res = 0
    while left <= right:
    if left & 1: # 奇数,右子节点
    res += self.tree[left]
    left += 1
    left >>= 1
    if right & 1 == 0: # 左子节点
    res += self.tree[right]
    right -= 1
    right >>= 1
    return res
  4. 原理说明,leftright 同步跳动,规则如下:

    • left 出现在左节点时,直接回退父节点
    • left 出现在右节点时,由于父节点也包含了左节点的结果,不能直接回退,而是记录当前数值,并跳到相邻父节点,如下图
      2022-03-26_11-06-26
    • right 的规则与 left 相反,同理讨论
    • rightleft 相遇时,记录当前数值并跳出循环,如下图
      2022-03-26_11-13-29
    • rightleft 交错时,直接跳出循环,参看下图
      2022-03-26_11-13-38
    • 讨论不仅对节点数目非 2n2^n 的情形也适用,只是叶子节点会分布在两层,比如 10个节点的情形
      2022-03-26_11-17-25

排序算法

快速排序

  1. 主函数

    1
    2
    3
    4
    5
    def quick_sort(nums, left, right):
    if right <= left: return nums # 至少两个元素
    p = partition(nums, left, right)
    quick_sort(nums, p + 1, right) # 排序右边部分
    quick_sort(nums, left, p - 1) # 排序左边部分
  2. 双边扫描,左指针数值保持严格小,右指针保持不小于

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    def partition(nums, left, right):
    i, j, num = left, right - 1, nums[right] # 左右指针和中间值
    while i <= j:
    if nums[i] < num: # 左指针前进
    i += 1
    elif nums[j] >= num: # 右指针后退
    j -= 1
    else: # 交换
    nums[i], nums[j] = nums[j], nums[i]
    i, j = i + 1, j - 1
    nums[right], nums[i] = nums[i], nums[right]
    return i
  3. 单边扫描,一个指针扫描,一个指针记录大于目标值的最左位置

    1
    2
    3
    4
    5
    6
    7
    8
    def partition(nums, left, right):
    p1, num = left, nums[right] # 记录位置的指针 p1
    for p2 in range(left, right): # 扫描区间 [left, right-1]
    if nums[p2] < num: # 小于目标值,交换到左侧
    nums[p1], nums[p2] = nums[p2], nums[p1]
    p1 += 1
    nums[p1], nums[right] = nums[right], nums[p1] # 最后交换目标值
    return p1

归并排序

  1. 代码模板

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    def merge_sort(arr):
    n = len(arr)
    if n <= 1: return arr
    mid = n >> 1
    lpart = merge_sort(arr[:mid])
    rpart = merge_sort(arr[mid:])
    return merge(lpart, rpart)

    def merge(lpart, rpart):
    tmp, i, j, nl, nr = [], 0, 0, len(lpart), len(rpart)
    while i < nl or j < nr:
    if j == nr or i < nl and lpart[i] <= rpart[j]:
    tmp.append(lpart[i])
    i += 1
    else:
    tmp.append(rpart[j])
    j += 1
    return tmp

    merge_sort(nums)
  2. 相关 LeetCode 问题:

堆排序

小顶堆模板

1
2
3
from heapq import heapify, heappop, heappush, nsmallest, nlargest
heapify(nums)
nsmallest(1, nums)

最短路

堆优化的 Dijkstra 模板

1
2
3
4
5
6
7
8
9
10
11
12
13
def dijkstra(arrows, src, dist):
"""arrows 为字典类型"""
queue = [(0, src)]
dist[src] = 0
while len(queue):
cost, node = heappop(queue)
if cost > dist[node]:continue
for new, weight in arrows[node].items():
weight += cost
if weight < dist[new]:
dist[new] = weight
heappush(queue, (weight, new))
return

动态规划

01背包

暂略