Skip to content

Latest commit

 

History

History
374 lines (285 loc) · 11.6 KB

coding.md

File metadata and controls

374 lines (285 loc) · 11.6 KB
Raw

代码逻辑

向量计算

  • 距离 = 向量 - 向量
  • 数量 = 距离 + 1
  • 间隔 = 距离 - 1

布尔代数

bool

分支逻辑

  • 并行分支：if if

  • 互斥分支：if else/break/goto/return, switch, table

    1. 列出所有条件的所有状态
    2. 为每种状态组合建立分支 $N_1 × N_2 × ... × N_n$
    3. 将逻辑相同的分支合并

循环逻辑

  1. 一般状态：每次迭代的主体逻辑
  2. 状态转移：将当前迭代状态转移到下次迭代状态，可以在选择在循环首部或尾部进行
  3. 初始状态：调整初始状态使第一次迭代正确进行
  4. 终止状态：设置终止条件来结束循环，根据状态转移在首部还是尾部，条件检测终止状态或终止状态+1
  5. 依赖检测：若迭代逻辑依赖当前迭代之前或之后状态，检测状态是否得到保证

递归步骤

  1. 一般状态：一般状态依赖子状态
  2. 基准状态：不依赖子状态，通常将条件判断放到基准逻辑以简化一般逻辑

算法思维

  • 枚举
  • 回溯：记录路径、路径染色
  • 贪心：证明局部最优解即全局最优解
  • DP：最优子结构+状态转移公式，解决有限集中最值问题(min/max/count)
  • 分治

数据结构与算法

栈

关键字：层级、递归、后进先出

队列

关键字：滑动窗口、先进先出

单调栈

关键字：单调排列、最近较大/小值

特点：以单调递减栈为例

  • 对出栈元素来说：
    • 入栈元素是其右侧最近的较大值
  • 对入栈元素来说：
    • 栈里的元素即其左侧单调排列的元素（忽略破坏单调性的元素）
    • 出栈完成后栈顶第元素即其左侧最近的较大值

单调队列

关键字：滑动窗口最值

链表

关键字：随机插删

  • 哑节点，简化边界

    反转链表时，哑节点为 nullptr

  • 双指针，一前一后

    迭代更新 prev 指针时，最好使用prev=cur; cur=cur->next_;迭代

  • 双指针，一快一慢

    每次循环 fast 先行两步，若成功则 slow 再后行一步，如此一来 slow 会在奇数时停在中点，偶数时停在较小中点

  • 双指针，间隔距离
  • 增加额外节点
  • 更改链表结构

二叉树

关键字：快速搜索、元素排序

  • 广度优先搜索(BFS)

  • 深度优先搜索(DFS)

    • 先序遍历：序列首元素为根节点

    • 后序遍历：序列尾元素为根节点

    • 中序遍历：根节点将序列分为左右两边

    • 有序遍历：最小值在最左节点，最大值在最右节点； 对于下个节点，若有右子树则为右子树最左节点，否则向上搜索直至根节点或某节点为其父节点的左子节点（父节点为下个节点）

    • 插入算法：利用引用语义传入父节点的子节点指针TreeNode*& root 从而简化递归基准为为if ( root == nullptr ) { root = new TreeNode{val}; return; }

    • 删除算法：若有两个子节点则用右子树的最左节点替换该节点，否则root = root->left ? root->left : root->right;； 若预期删除次数不多则可以使用“懒惰删除”从而提高性能

哈希表

关键字：极快速搜索、频度统计、重复值校验

二分搜索

关键字：搜索有序序列

def binary_search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] > target:
            right = mid - 1 # right 可能为负，所以不能为 uint
        else:
            left = mid + 1
    return -1

快速排序

func QuickSort(nums []int) {
    if len(nums) <= 1 {
        return
    }
    left, right := 0, len(nums) - 1
    mid := (left + right + 1) / 2
    // 选取三值的中值作为枢纽值，小值移到首部，将中值移到尾部，如上计算 mid 可使仅有两个元素时依然成立
    if nums[right] < nums[left] {
        nums[right], nums[left] = nums[left], nums[right]
    }
    if nums[mid] < nums[left] {
        nums[mid], nums[left] = nums[left], nums[mid]
    }
    if nums[mid] < nums[right] {
        nums[mid], nums[right] = nums[right], nums[mid]
    }
    i, j := left, right
    for {
        for i++; nums[i] < nums[right]; { // 尾部元素为中值，不会越界
            i++
        }
        for j--; nums[j] > nums[right]; { // 首部元素为小值，不会越界
            j++
        }
        if i >= j {
            break
        }
        nums[i], nums[j] = nums[j], nums[i]
    }
    nums[i], nums[right] = nums[right], nums[i]
    QuickSort(nums[:i])
    QuickSort(nums[i+1:])
}

归并排序

// tmp 保证长度大于等于 nums
func MergeSort(nums []int, tmp []int) {
    if len(nums) <= 1 {
        return
    }
    mid := len(nums) / 2
    MergeSort(nums[:mid], tmp)
    MergeSort(nums[mid:], tmp)
    i, j, k := 0, mid, 0
    for i < mid || j < len(nums) {
        if i == mid {
            tmp[k] = nums[j]
            j++
        } else if j == len(nums) {
            tmp[k] = nums[i]
            i++
        } else if nums[i] < nums[j] {
            tmp[k] = nums[i]
            i++
        } else {
            tmp[k] = nums[j]
            j++
        }
        k++
    }
    for i := 0; i < k; i++ {
        nums[i] = tmp[i]
    }
}

堆排序

def sortArray(nums: list[int]) -> list[int]:
    left_child = lambda i: 2 * i + 1
    right_child = lambda i: 2 * i + 2
    parent = lambda i: (i - 1) // 2
    def down(i, l=len(nums)):
        while left_child(i) < l:
            j = left_child(i)
            if right_child(i) < l and nums[right_child(i)] > nums[left_child(i)]:
                j = right_child(i)
            if nums[i] > nums[j]:
                break
            nums[i], nums[j] = nums[j], nums[i]
            i = j

    # 建堆
    i = left_child(len(nums) - 1)
    while i >= 0:
        down(i)
        i -= 1
    # 排序
    j = len(nums) - 1
    while j > 0:
        nums[0], nums[j] = nums[j], nums[0]
        down(0, j)
        j -= 1
    return nums

滑动窗口

关键字：子数组、跳跃遍历、滑动窗口
细节：辅助表类型：覆盖型、叠加型、抵消型、语义型

回溯算法

关键字：路径搜索、路径染色、回溯算法
细节：注意剪枝；注意返回前是否需要清除染色或弹出路径节点：每次都弹，全都不弹，成功则不弹

动态规划

“所有的 DP 问题，本质上都是有限集中的最值问题”——闫氏 DP 分析法

将问题模型化为：求有限集 S 中满足限制条件 C 的 max/min/count 结果

  • 状态表示：写出一个函数形式如f(i, j)用来表示一个子集合的结果

    • 集合：满足某些条件的子集合，如范围限制、长度限制、数值限制
    • 结果：通常为题解如 max/min/count

  • 状态计算：写出状态表示函数的定义，即递推方程

    • 将当前集合不遗漏地划分为若干子部分求解
      • max/min 即各部分 max/min 值的 max/min（子部分划分可部分重叠）
      • count 即各部分 count 的和（子部分划分不可重叠）

  • 时间优化与空间优化：都是对代码中公式的恒等变换

逆向思维

  • 求起点的终点转为求终点的起点
  • 对多个元素进行操作，相当于对其他元素进行相对逆操作
  • 由结论出发，向所求条件逆推

位运算

  • 位与(&)：0 归零 1 取值、1 不变 0 归零
  • 位或(|)：0 不变 1 存值
  • 异或(^)：0 不变 1 取反、同归零
  • 位反(~)：~x == -x - 1
  • 消除尾 1：x &= (x - 1)

模运算

  • 同余方程
    • $(a - b) % N = 0$
    • $a \equiv b \mod N$
    • $a+c \equiv b+c \mod N$
    • $a \times d \equiv b \times d \mod N$
  • 求余方程
    • $(a + b)% N = (a% N + b% N)% N$
    • $(a \times b)% N = (a% N \times b% N)% N$
    • $(a - b)% N = (a% N - b% N + N)% N$
    • $(a \div b)% N = (a \times b^{-1})% N$
  • 求模运算
    • 截位取值（字符转数字从前往后，数字转字符串从后往前）
    • 数值回环

topK 算法

  • 动态容器求 Top K
数据结构 描述
数组 快速选择算法 O(N)
数组 插入有序数组 O(N)，随机访问 topK O(1)
链表 插入有序链表 O(N)，遍历访问 topK O(1)
红黑树 插入 O(log(N))，中序遍历获取 topK O(log(N))
最小堆 额外维护 topK 的最小堆，插入 O(log(K))，访问 topK O(1)
  • 动态容器求 No.K
数据结构 描述 条件
数组 快速选择算法 O(N) 静态
数组 插入有序数组 O(N)，随机访问中位数 O(1) 动态插入
链表 维护两个指向中间节点的指针，插入有序链表 O(N)，访问中位数 O(1) 动态插入
红黑树 每个节点维护该子树的节点数，插入 O(log(N))，访问中位数 O(log(N)) 动态插入
AVL 树 用两子树的节点数做平衡因子，插入 O(log(N))，访问中位数 O(1) 动态插入
最小堆与最大堆 使大数最小堆与小数最大堆的大小平衡，先插入小数最大堆，插入 O(log(N))，访问中位数 O(1) 动态插入

海量数据

注：重复性问题可尝试应用 bit-map

注：重复度较高时可应用 trie-tree

  • 问：找出文件 A、B 的共同数据？

    • 答：哈希取模，文件作桶，哈希统计，依序对比

  • 问：统计海量数据的频度？

    • 答：哈希取模，文件作桶，哈希统计

  • 问：对海量数据进行排序？

    • 答：分块，排序，归并

  • 问：海量数据中找出 topK？

    • 答：维护 topK 最小堆

  • 问：海量数据中找出频度 topK？

    • 答：哈希取模，文件作桶，哈希统计，维护 topK 最小堆

  • 问：海量数据中找出中位数？

    • 答：截高位，文件作桶，找出中位数所在桶，应用中位数算法

  • 问：分布式处理，海量数据分布在 N 台主机中，求 topK

    • 答：每台主机求 topK，然后汇总归并取前 K

  • 问：分布式处理，海量数据分步在 M 台主机中，求频度 topK

    • 答：哈希取模，主机作桶，哈希统计，求 topK，汇总归并取前 K