读书笔记——labuladong算法笔记

序言

labuladong算法笔记是一本讲解算法题求解技巧的书。本次读书笔记为2023年8月第1版的相关内容，作者为付来东。本书是配套leetcode进行算法讲解的，语言使用C++和Java。本书对于提高算法结题能力的方法是将常用的算法进行抽象，形成系统，以为读者赋能。这个确实是一个很实用的方法论。以下从世界观到方法论，逐渐深入。

计算机算法世界观

什么是计算机算法，计算机算法到底如何求解问题？有三种方法：1、人通过自己的思辨能力，指导计算机算出值，计算机只作为计算器；2、暴力求解，人设计计算机遍历解求值域的方式以及定义解，让计算机进行遍历求解；3、前两者结合。

计算机算法方法论

二叉树遍历

这里的“二叉树”是泛华的概念，指一切在某种状态下需要进入其子状态进行遍历的模式。

广度遍历BFS

广度遍历一般用于求解到根节点的最短距离，这种算法一般空间复杂度比较大，因为需要保存同一层所有“有效节点”。下面展示一下这个算法的解题模板：

template<typename judge_func>
int BFS(node* start, judge_func& target)
{deque<node*> q;		// 这个队列包含本次要弹出的节点，以及其子节点q.push_back(start);		// 先把起始节点放入unordered_set<node*> visited;	// 已经访问过的节点，二叉树不需要，遍历图时需要 int step = 0;			// 记录最小步数while (!q.empty()){size_t sz = q.size();	// 记录父亲节点的数量// 依次弹出父亲节点，并将其子节点插入到队列末尾for (int i = 0; i < sz; ++i){node* cur = q.front();q.pop_front();// 判断是不是需要的目标if (target(cur)){return step;}// 如上所述，将当前节点子节点加入队列末尾for (auto sub: cur->subnodes()){if (0 == visited.count(sub)){q.push_back(sub);visited.insert(sub);}}// 更新步数++step;}}
}

过程就是先将第一个节点插入，然后循环判断当前数组中元素数量既是当前节点数量，判断当前节点是不是需要的，如果不是就讲其子节点插入，直到队列中不再有数据为止。
优化：BFS有一种双向BFS优化。因为BFS正向遍历会随着遍历次数增加，遍历的节点数量也会增加，但是如果通过从叶子向根进行遍历加上从叶子向根遍历，那么复杂度将大大降低。

二叉树的前中后序遍历

二叉树遍历其实很简单，主要就是对当前节点的处理时机不同。首先访问当前节点的就是前序，中间访问就是中序，访问完子节点之后再访问的就是后续。框架代码如下：

void traverse(TreeNode* root)
{if (root == nullptr){return;	}// 前序位置traverse(root->left);// 中序位置traverse(root->right);// 后序位置
}

回溯算法

这个算法看上去名字很高大上，其实搞某一门学科的人就喜欢把一个简单的说法说的让人觉得“不明觉厉”。所谓回溯算法实际就是“选择->撤销->下一个选择->再撤销…"如此而已。下面给出一个回溯算法的框架伪代码：

result = []
def backtrack(路径, 选择列表):if 满足结束条件:result.add(路径)returnfor 选择 in 选择列表:做选择（设置下一个选择状态）backtrack(路径, 选择列表)撤销选择（恢复当前选择状态）

回溯算法关心的是到达目标状态的路径情况（重点）。另外，回溯算法和动态规划算法不一样的一点就是，回溯算法没有重叠子问题，没有办法通过字典来进行优化，就是纯的暴力搜索。

动态规划算法

动态规划是各个厂经常考的题目类型，难住过不少工友，当然也包含我。动态规划一般用于求极值。动态规划问题需要满足最优子问题，就是说一个问题的最优解，可以分解成为其子问题的最优解作为参数以后的最优解。子问题之间不能有相关性。动态规划有自顶而下和自底而上两种解法，由于动态规划会存在子问题，因此可以使用备忘录进行加速。解法伪代码如下：

# 自顶而下
def dp(状态1,状态2,状态3,...)：for 选择 in 所有可能选择：# 此时的状态可能由于做出的选择而改变result = 求最值(result, dp(状态1,状态2,...))return result# 自底而上
# 初始化base case
dp[0][0][...]=base case
# 进行状态转移
for 状态1 in 状态1的值域:for 状态2 in 状态2的值域:for ...dp[状态1][状态2][...] = 求最值(选择1,选择2,...)

二分搜索算法

二分搜索一般的时间复杂度是O(log(n))，所以看到要求时间是这种形式的很多都是用的二分搜索算法。二分搜索算法原理非常简单，难点在于其边界条件上。所以在写二分算法的时候要先想清楚是要用闭区间还是开区间，另外要明白“中点”这个概念是一个开区间的边界，因为在每次判断必然会判断这个点，因此如果你要用开区间，那么这个点可以直接使用，否则就需要跳过该点。二分搜索框架如下：

int binarySearch(vector<int> nums, int target)
{int left = 0;int right = nums.size() - 1;	// 闭区间，因为搜索范围肯定是包含最后一个元素的嘛while (left <= right)			// 闭区间两者相等时结束了吗？并没有啊，因为区间中还有一个元素的{int mid = left + (right-left)/2;if (nums[mid] == target){return mid;	}else if (nums[mid] < target) 	// 目标在中点右侧{left = mid + 1;				// mid已经验证过所以要+1}else if (nums[mid] > target)	// 目标在中点左侧{right = mid - 1;}}return -1;
}

二分搜索还可以扩展为在元素可重复的数组中查找左右边界，框架如下：

int left_bound(vector<int>& nums, int target)
{int left = 0;int right = nums.size();		// 右开区间while (left < right)			// 相等时区间内不存在元素，可以跳出{int mid = left + (right-left)/2;if (nums[mid]==target){right = mid;			// 重点。相等时移动右边界}else if (nums[mid]<target){left = mid+1;}else if (nums[mid] > target){right = mid;			// 开区间，如上所述，中点本身是开区间边界}}return left;
}

上面找到的左边界是闭边界。

其他算法

滑动窗口

滑动窗口一般用于遍历一遍就可以解决数据集子集问题。这种问题在乎的是子集的组合对子集的排列没有严格要求。滑动窗口问题框架如下：

void slidingWindow(string s)
{unordered_map<char,int> window;int left = 0, right = 0;while (left < right && right <  s.size()){char c = s[right];window.add(c);right++;// 窗口内数据更新while (left < right && window needs shrink){char d = s[left];window.remove(d);left++;// 窗口数据更新}}
}

双指针

双指针比较灵活，需要注意的就是你可以设计双指针的迭代方式，可以是快慢指针，也可以从起点像两边扩展的指针（对于回文子串有效）。

Union-Find算法

Union-Find算法算是比较奇特的算法了，它用于生成和查找集合中的联合域。生成过程分2步：
1、初始化：每个元素的父节点都是自己；
2、连接：将一个域的父节点的父节点指向另外一个域的父节点；
这样就可以生成一个UF了。代码如下：

class UF
{
private:int count;vector<int> parent;
public:UF(const int& n):count(n),parent(n,0){for (int i = 0; i < n; ++i){parent[i] = i;}}void union(int p, int q){int rootP = find(p);int rootQ = find(q);if (rootP==rootQ)return;parent[rootQ]==rootP;count--;}bool connected(int p, int q){int rootP = find(p);int rootQ = find(q);return rootP==rootQ;}int find(int x){if(parent[x] != x){parent[x] = find(parent[x]);}return parent[x];}int count() const{return count;}
};