算法

发表于 2021-08-21 更新于 2024-06-07 分类于计算机理论阅读次数：

…

参考

动态规划

动态规划问题的一般形式就是求最值，例如：最长递增子序列呀，最小编辑距离等。求解动态规划的核心问题是穷举。

动态规划三要素：

重叠子问题：需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
最优子结构：子问题间必须互相独立。
状态转移方程：最困难部分，思路：明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。

备忘录：一般使用数组，也可以使用哈希表。
DP table：采用自底向上的方法，去除递归，改为循环。
进一步优化：采用自底向上方法，还可以节省空间，去除不再需要的历史状态。

时间复杂度计算：子问题总数 * 每个子问题的时间

解题思路

首先确定子问题以及子问题是否相互独立。
列出状态转义方程。
1. 确定状态：原问题和子问题中变换的变量。
2. 确定dp函数：被递归调用的函数（自变量，因变量）。
3. 确定选择状态的条件
4. 明确最小子问题base case
解除重复子问题
1. 使用备忘录
2. 使用dp table，定义dp数组（自变量，因变量）

最优子结构：并不是动态规划问题专有的。也就是说，很多问题其实都具有最优子结构，只是其中大部分不具有重叠子问题。

如果问题中没有最优子结构，那么久改造它，让它有。找最优子结构的过程，其实就是证明状态转移方程正确性的过程，方程符合最优子结构就可以写暴力解了，写出暴力解就可以看出有没有重叠子问题了，有则优化，无则 OK。

回溯

解决一个回溯问题，实际上就是一个决策树的遍历过程。不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

路径：也就是已经做出的选择。
选择列表：也就是你当前可以做的选择。
结束条件：也就是到达决策树底层，无法再做选择的条件。

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

二分查找

二分查找：思路很简单，细节是魔鬼。
为了能够清晰展示所有细节，尽量用else if而不是else

int binarySearch(int[] nums, int target) {
    int left = 0, right = ...;

    while(...) {
        // 这样是为了防止数值过大导致溢出
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            ...
        } else if (nums[mid] < target) {
            left = ...
        } else if (nums[mid] > target) {
            right = ...
        }
    }
    return ...;
}

一般的查找一个数（没有重复元素）

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意，是最后一个元素的索引，用的是闭区间 [x, y]

    while(left <= right) { // right = nums.length - 1 所有用 <=
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    // 跳出循环的条件 left == right + 1
    return -1;
}

A: while(left < right) 的终止条件是 left == right，这时候区间[x, x]被漏掉，要在最后单独判断该区间。否则就用while(left <= right)作为终止条件。

B: left = mid + 1，right = mid - 1，由于mid已经被搜索过了，因此在新的区间中去掉mid。

寻找左侧边界的二分搜索

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意，用了左闭右开区间 [x, y)

    while (left < right) { // 注意，结束条件是 [x, x)
        int mid = (left + right) / 2;
        if (nums[mid] == target) { // 当找到target时，不会立即退出，而是继续缩小搜索范围
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意，由于左闭右开区间，取左半区间时已经消除mid了
        }
    }
    return left; // 结果含义：比target小的数有几个

    // 因此也可以是
    // target 比所有数都大
    if (left == nums.length) return -1;
    // 类似之前算法的处理方式
    return nums[left] == target ? left : -1;
}

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    // 如果使用了闭区间，那么在得到结果区间[x, x]后，不会返回，而是计算了一次 right = mid - 1 变成了[x, x-1]
    // 由于 while 的退出条件是 left == right + 1，当 target 比 nums 中所有元素都大时，会存在索引越界
    // 检查出界情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

双指针

unordered_map 就是哈希表（字典），它的一个方法 count(key) 相当于 containsKey(key) 可以判断键 key 是否存在。可以使用方括号访问键对应的值 map[key]。需要注意的是，如果该 key 不存在，C++ 会自动创建这个 key，并把 map[key] 赋值为 0。

滑动窗口：

初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。
不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求。
我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求。
重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

总结：先移动右指针找到可行解，再移动左指针优化可行解。最后找到所有优化的可行解。

int left = 0, right = 0;

while (right < s.size()) {
    // window 滑动窗口，采用哈希表，用于判断是否含有某字符
    window.add(s[right]);
    right++;

    while (valid) {
        window.remove(s[left]);
        left++;
    }
}

快慢指针：
判定链表中是否含有环：如果有环，那么快指针总会碰到慢指针。

boolean hasCycle(ListNode head) {
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;

        if (fast == slow) return true;
    }
    return false;
}

找到环：当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。

ListNode detectCycle(ListNode head) {
    // 判断有环
    ListNode fast, slow;
    fast = slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow) break;
    }
    // 上面的代码类似 hasCycle 函数
    slow = head;
    while (slow != fast) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow;
}

找链表中点；
找链表倒数第K个元素。

左右指针：一般初始化为 left = 0, right = nums.length - 1 。
二分查找；
两数之和；
反转数组；
滑动窗口。

排序

排序应该考虑数据的特点：

一般情况下：快排
包含大量重复元素：三路快排
近乎有序：插入排序
有限范围：计数排序
稳定排序：归并排序
内存不足：外排序
无法随机存取：归并排序

面试准备

准备的主要内容：

梳理项目
- 项目经历
- 遇到的实际问题
遇到过的难以解决的BUG
面向对象与设计模式
网络、安全、内存、并发等问题
系统规模，系统设计，承载量

个人经历，结合项目：

遇到的最大的挑战
犯过的错误
经历的失败
最享受的工作内容
遇到冲突的解决方法
做过的与众不同的事

做好问面试官的问题：

小组的运行模式
项目的后续规划
产品中的某个问题如何解决的
为什么选择这个技术和标准
我在这个小组中有机会深入学习某个技术吗

低概率算法面试题：

红黑树
B-Tree
斐波那契堆
计算几何
数论
FFT

常见算法面试题：

排序算法
数据结构的实现：堆，二叉树，图
数据结构的使用：链表，栈，队列，哈希表，图，Trie，并查集
算法：深度优先，广度优先，二分查找，递归
基本思想：递归，分治，回溯，贪心，动态规划

算法复杂度

一秒内各个复杂度能力：

n^2 - 10^4
n - 10^8
nlogn - 10^7

对数器

使用最不容易出错的方法实现一个程序，再用这个程序测试自己的算法。

数组

BFPRT

KMP

位运算

异或：满足交换律。

找到一个数组中一个出现奇数次的数：偶数个数异或为零。

取int最右侧的1：N & ((~N) + 1)，

有两个数（a，b）出现奇数次，其他都是偶数次：所有数异或，相对于 a 异或 b 且结果不为 0，取结果int最右侧的 1。例如是第x位，那么a和b的第x位一定不同。此时可以按照第八位不同来将数组划分成两半。各自找出组内唯一的奇数次数。

大小写转化

转小写 ('a' | ' ') = 'a', ('A' | ' ') = 'a'
转大写 ('a' & '_') = 'A', ('A' & '_') = 'A'
大小写呼唤 ('a' ^ '_') = 'A', ('A' ^ '_') = 'a'

并查集

链表

快慢指针：

找中点（上中点，下中点），中点上一个点：先处理头节点，不足3个节点的情况。

判断链表回文：

栈：所有元素入栈，然后取出一个元素，与链表元素比对，直到完成所有比对。
修改链表后半个方向

划分为元素左边小，中间等，右边大：考虑换头。

利用数组
划分为3个区，每个区存储2个边界，再把链表放入3个区中，最后串联所有区。

复制链表：链表上每个节点还有额外指针指向其他元素

使用哈希表，旧节点与新节点一一映射。

判断链表是否相交，可能存在环

判断环，得到环的第一个节点。
- 使用 Set，存储内存地址。
- 快慢指针，相遇后，快指针从头开始，每次一步，直到再相遇。
如果都无环，一定是 Y 结构
使用 Set
记录两个链表长度，先判断他们最后节点是同一个节点，如果是，则一定相交。长链表先走，走到长度一致的位置开始，然后两链表一起走，一定会同时走到相交节点。
如果有环，一个无环，则一定不相交
两个都有环：不相交，相交且有相同的入环节点，相交且入环节点不同。
相交且有相同的入环节点：与 Y 结构解法类似
相交且入环节点不同、不相交：判断一个环上是否同时存在两个入环节点。

约瑟夫环问题

循环链表

二叉树

非递归遍历：

先序遍历：弹出就打印，先压入右，再压入左。
中序遍历：先压缩左边界所有节点，之后弹出一个节点打印，来到它的右树，再压入其所有左边界。
后序遍历：不严格方式，先序遍历的逆序，用栈收集元素。严格方式，要借用辅助指针。h指针表示上一个处理的节点，c指针表示当前处理的节点，然后判断c的左右两个还是是否右h，根据情况判断处理子树还是处理栈中元素。
按层遍历：使用队列。查看一行是否遍历结束，使用标志变量。

序列化、反序列化：遇到空节点也要输出。

先序遍历
层序遍历

打印一颗二叉树：

补成满二叉树打印
设计树的输出顺序：右-头-左，然后按行输出

中序找后继节点

右树上最左结点，或祖先是左子树的结点

判断平衡树

使用二叉树：考虑左右子树需要为自己提供的信息

返回整棵树的最大距离

左树的最大距离 + 右树的最大距离，或左(右)树自己的最大距离

找出二叉树中的最大搜索二叉树

左(右)树自己的最大搜索二叉树，或包含自己的最大搜索二叉树
- 获取子树的：最大值，最小值，是否是搜索二叉树，包含的搜索二叉树大小

判断满二叉树：

2^L - 1 <= H

判断完全二叉树：

宽度优先遍历，有右子树但无左子树则不是，都有则继续，只有左或没有子树，则后续都必须是叶子结点。

找两个结点的公共祖先

利用 Set ，并用 Map 记录子父关系
自己是目标结点，目标结点在左子树，或右子树，或不存在。

贪心算法：证明有效的方法是举反例

排序：不一定有传递性，贪心算法的排序需要传递性

线段树：区间中增删改查，算法复杂度是 log N

数组先补成 2^N 长度，再以此构建一个满二叉树
每个结点设计标记：lazy，change，update 标记

图算法

遍历

宽度优先遍历
- 考虑环的问题：标记法，数组或 Set
深度优先遍历

拓扑排序

队列：每次入度为零的点加入
数组：排序结果

最小生成树

堆：存放边

最短路径

Dijkstra

动态规划

一共4种模型。

打印字符串的子序列

暴力递归，参数包括：字符串，当前的字符序号，之前所形成的答案（叶节点用），当前使用的路径。叶结点处理路径结果。
去重后只求个数，动态规划

打印字符串的全排列

暴力递归：str[i]之后的所有字符都有机会到str[i]位置，之前的都是定好的。

从左往右尝试模型：

111可以转化为AAA或KA
0-1背包：不变量，货物的重量，价值，包裹的大小；变量，选择了哪些货物，已经存放了多少重量（或剩余的空间）；因变量，总价值

范围上尝试模型

数值不同的纸牌排成一条线，玩家A和玩家B依次拿走纸牌，且每次只能拿最左或最右的纸牌。如果A先拿，则获胜者的分数是多少。需要参数：数组，范围的左右边界。
- base case - 如果范围内只有一个纸牌，则直接返回这个纸牌
- 要么选左边的牌，要么选右面的牌，选完后变后手。
- 站在先手的角度考虑，求先手的函数要max，求后手的函数要min

多样本位置全对应的尝试模型

寻找业务限制的尝试模型

经典问题

N 皇后问题
- 优化：位运算，斜线限制使用位移

动态规划的解法：先暴力写法，再改记忆化搜索算法，再改经典动态规划（可不改）。如果状态出现枚举行为，则改经典动态规划后会继续优化（利用状态转移做优化）。看一个格子依赖谁，每次依赖多少，就可以压缩到多少。

记忆化搜索：键要包括变量，值要设定初始值。

特殊问题：

取石子问题，合并石子问题，四边形不等式。
摆放广告牌问题。
斜率优化
初始值设置

预处理

前缀和
前缀树
排序

其他问题

海盗分金币问题：分析设定，从小依次递推

欧拉信封问题：找递推公式 F(n) = (n-1) * (f(n-2) + f(n-1)), 初值 0, 1, 2

动态规划

回溯

二分查找

双指针

排序

面试准备

算法复杂度

对数器

数组

BFPRT

KMP

位运算

并查集

链表

二叉树

图算法

动态规划

预处理

其他问题

NP 完全问题