asp做网站很少,中国搜索引擎网站排名,网站备案信息注销,济南成之运维网络科技读书笔记——labuladong算法笔记 序言计算机算法世界观计算机算法方法论二叉树遍历广度遍历BFS二叉树的前中后序遍历回溯算法动态规划算法二分搜索算法 其他算法滑动窗口双指针Union-Find算法 序言
labuladong算法笔记是一本讲解算法题求解技巧的书。本次读书笔记为2023年8月第… 读书笔记——labuladong算法笔记 序言计算机算法世界观计算机算法方法论二叉树遍历广度遍历BFS二叉树的前中后序遍历回溯算法动态规划算法二分搜索算法 其他算法滑动窗口双指针Union-Find算法 序言
labuladong算法笔记是一本讲解算法题求解技巧的书。本次读书笔记为2023年8月第1版的相关内容作者为付来东。本书是配套leetcode进行算法讲解的语言使用C和Java。本书对于提高算法结题能力的方法是将常用的算法进行抽象形成系统以为读者赋能。这个确实是一个很实用的方法论。以下从世界观到方法论逐渐深入。
计算机算法世界观
什么是计算机算法计算机算法到底如何求解问题有三种方法1、人通过自己的思辨能力指导计算机算出值计算机只作为计算器2、暴力求解人设计计算机遍历解求值域的方式以及定义解让计算机进行遍历求解3、前两者结合。
计算机算法方法论
二叉树遍历
这里的“二叉树”是泛华的概念指一切在某种状态下需要进入其子状态进行遍历的模式。
广度遍历BFS
广度遍历一般用于求解到根节点的最短距离这种算法一般空间复杂度比较大因为需要保存同一层所有“有效节点”。下面展示一下这个算法的解题模板
templatetypename judge_func
int BFS(node* start, judge_func target)
{dequenode* q; // 这个队列包含本次要弹出的节点以及其子节点q.push_back(start); // 先把起始节点放入unordered_setnode* 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(vectorint 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(vectorint 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 mid1;}else if (nums[mid] target){right mid; // 开区间如上所述中点本身是开区间边界}}return left;
}上面找到的左边界是闭边界。
其他算法
滑动窗口
滑动窗口一般用于遍历一遍就可以解决数据集子集问题。这种问题在乎的是子集的组合对子集的排列没有严格要求。滑动窗口问题框架如下
void slidingWindow(string s)
{unordered_mapchar,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;vectorint 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 (rootProotQ)return;parent[rootQ]rootP;count--;}bool connected(int p, int q){int rootP find(p);int rootQ find(q);return rootProotQ;}int find(int x){if(parent[x] ! x){parent[x] find(parent[x]);}return parent[x];}int count() const{return count;}
};
