LuYaoQi's Blogs

学习小结本周跟随代码随想录继续图论相关学习，主要聚焦于从一个点到另一个点的最小距离问题，学习了 dijkstra，bellman_ford，floyd，A* 算法。 相比于此前的算法设计课，更深刻地了解了各个算法的优势和缺点，比如 dijkstra 不能应对 负权 的边，bellman_ford可能会陷入负权回路的陷阱中，A* 不擅长多源距离等。 至此，代码随想录的一刷算是完成力，嘛，明天起就得开始狠狠二刷咯。 图论 dijkstra(朴素版) 代码随想录 47. 参加科学大会（第六期模拟笔试） 题意：给一些节点和节点之间部分路径（有向），求起点到终点的最短路径是多少。 方法：其实bfs/dfs应该也行吧，dijkstra 是求一个点到其余点的最短路径距离。本质和prim差不多，但prim只要关注点之间的距离就行，而dijkstra要考虑的可就多了，每次更新最短距离不仅要看新纳入点与当前体系的距离，还要看起点到体系边缘的距离。 但是该方法不能对有负数权值的图使用，比如下面这个从节点一出发，如果按照算法，走的路线是...

学习小结本周跟随《代码随想录》继续学习关于图论的知识，主要是关于并查集以及最小生成树的两个经典算法（prim和kruskal）。 并查集的作用在于快速区分不同的类别并补充内容。prim 则是从点的角度从图中划分出最小生成树，kruskal 是划分边来种最小生成树。 图论 有向图的完全可达性 代码随想录 105. 有向图的完全可达性 问题：给一个有向图，但求中的1节点是否能到达其他节点。 方法：从 1 开始 dfs/bfs 就可以，重点在于用邻接表存储 参考代码随想录思路的解法 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include <iostream>#include <vector>#include <list>using namespace std;void dfs(const vector<list<int>> grid,...

学习小结本周跟随《代码随想录》继续学习关于图论的知识，主要是学习岛屿，也就是 bfs/dfs 的经典应用。同时还有[[字符串接龙]]这种新颖的图论题目，才知道各种字符串也能抽象为一个图。 图论 岛屿数量广搜版 代码随想录 99. 岛屿数量 直接说明区别和放代码好力，代码就是在[[岛屿数量深搜版]]的基础上做了一点更改，原本的搜索函数不断递归向深了探索，现在是用队列（栈也可，区别在于遍历顺序）来记录要遍历的区块，再按顺序处理 修改后的代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include <iostream>#include <vector>#include <queue>using namespace std;int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};void bfs(const...

学习小结本周跟随《代码随想录》学习关于单调栈的知识，同时开启图论。 单调栈通过保持一个栈从栈顶到栈底的递增或是递减序列，来解决找一个元素左/右的“第一个”更大/更小元素。 图论则是初窥dfs的门路，虽然道理一年前早在算法课学过考过，但现在也得复习才能捡回来。 单调栈 每日温度 代码随想录 739. 每日温度 - 力扣（LeetCode） 题意：给一个整数数组，求每个数字右侧比该数字更大的间距 方法：暴力解法就是O(n^2)的遍历。更高效率的方法是使用单调栈，所谓的单调栈就是从栈顶到栈底递增或递减的，如此排列，就能方便找任意元素的左右第一个更大更小的元素。 比如本题是找右边更大的，那么遍历数组时，遇到更小或相等的元素就直接入栈，而遇到更大的元素就弹栈，直到触底或碰到大元素再入栈，其中弹栈的元素就能记录本元素的下标与当时元素下标之差。 参考代码随想录思路的解法 12345678910111213141516171819202122232425class Solution {public: vector<int>...

学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学习子序列相关内容，其中的编辑距离在网络搜索引擎的期末考试见过。但通过本次学习，逐渐感受到在算法，或者说计算机的世界中，很多事情往往会通过抽象来变得简洁从而易于处理。 动态规划 最长重复子数组 代码随想录 718. 最长重复子数组 - 力扣（LeetCode） 题意：给两个数组，问两个数组中最长重复的子数组长度是什么 方法：用二维dp，dp[i][j] 代表第一个数组 i-1 为尾部和第二个数组 j-1 处为尾部，最长重复子数组长度。递推公式，当 num1[i-1]==num2[j-1]，即可 dp[i][j] = dp[i-1][j-1]+1;初始化，都为0遍历顺序，无所谓，不过从前向后就可举例…… 参考代码随想录思路的解法： 1234567891011121314151617181920class Solution {public: int findLength(vector<int>& nums1,...

学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学习完买卖股票相关内容，并初步探索子序列的部分。 买卖股票的题有明显的状态转换，但子序列就没那么明显。 动态规划 买卖股票的最佳时机II 代码随想录 122. 买卖股票的最佳时机 II - 力扣（LeetCode） 题意，在[[买卖股票的最佳时机]]的基础上，要求可以多次购买股票，但同一时段只能持有一支股票，也就是再卖出上一支股票前，不允许购入下一支股票。 方法，与[[买卖股票的最佳时机]]的差别，在于考虑购入当前股票时，是在上一支股票考虑购入和卖出的两个情况中取最大，并非直接取历史最便宜股票和当前股票对比。 参考代码随想录思路解法 123456789101112131415161718class Solution {public: int maxProfit(vector<int>& prices) { // dp[i][0] 考虑第i支股票时，考虑买入的情况；dp[i][1] 考虑第i支股票时，卖出的情况 int len =...

学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，本周主要学会了完全背包的应用，多重背包的理论，打劫打家劫舍问题，和股票买卖问题的入门版。认识到了所存储的状态并不只有 整数 这一种形式，还能有多个整数并成的 vector 作为状态使用。 不得不说，动态规划十分的灵活，一百道题入门还不是说说而已啊。 动态规划 完全平方数 代码随想录 279. 完全平方数 - 力扣（LeetCode） 题意，给一个整数 n，求其被完全平方数组成的最小个数。 方法，就是[[零钱兑换II]]的变体，给的零钱变成了自己找小于 n 的完全平方数，背包容量为 n dp[j] 含义为 在背包容量为 j 的情况下，完全平方数的最小组合 递推公式，dp[i]=min(dp[i],dp[i-j*j]+1)，也就是要么保持不变，要么就在已有的组合上加一 初始化，dp[0]=0,这是为了递推公式才这么初始化，也能理解，完全平方数不算...

学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，不过周五和周日两门考试太重了，浅做两题，接下来非考试周就继续至少一天一道罢。 本周两道题是完全背包求排列数的应用题和完全背包求 组合/排列 的最小组合数，要记得组合与排列的区别在于背包空间和物品的遍历先后顺序，先遍历物品就不会出现物品乱序填背包的情况，所以是求组合数；而先遍历背包空间，使得同一个空间能有相同物品按不同顺序摆放，则是求排列数。 动态规划 爬楼梯（进阶版） 代码随想录 57. 爬楼梯（第八期模拟笔试） 题意，给 n 个台阶，和一起最多能迈 m 个台阶，问有多少不同方法可爬顶端 方法，由于同一步子可迈多次，故为完全背包问题，而且求的是排列数，与[[组合总和IV]]类似 陆爻齐的解法 123456789101112131415161718192021222324#include <iostream>#include <vector>using namespace std;int main() { int n, m; while(cin...

学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，主要是完全背包的入门，体会其与 01 背包的不同与关联。 下周两门考试，教务脑子真是进了水，搞这么紧干嘛。 动态规划 完全背包理论 代码随想录 52. 携带研究材料（第七期模拟笔试） 题目，与 [[01背包理论]]的差别在于一个物品可携带多次，求最大价值 方法， dp[j]，在遍历物品时，截止到空间为 j，可装入的最大价值 递推公式，dp[j]=max(dp[j],dp[j-weigh[i]]+val[i]) 初始化，全 0 遍历方向，重点，这是与 01 背包区别最大的地方，01 的滚动数组强调倒序遍历就是为了避免重复，在完全背包中，恰恰需要正序从而利用重复装入物品 举例，…… 参考代码随想录思路的解法 12345678910111213141516171819202122232425262728#include <iostream>#include <vector>using namespace std;int main() { int n, v; ...

学习小结本周跟随《代码随想录》继续推进动态规划的相关学习，由于期末月的到来，以及题目难度的增加，暂且将动态规划的学习进度放慢一点。下面继续巩固五步法。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 只能感叹，这动态规划真是一百道题才入门啊。 动态规划 分割等和子集 代码随想录 416. 分割等和子集 - 力扣（LeetCode） 题意，给一个数组，返回判断该数组是否能平分为和相等的两部分 方法，直觉上，可以用回溯遍历树，找到那个子节点，但复杂度太高。本题其实就是 01 背包的应用，nums[i] 本身，是物品，重量，以及价值。数组能否平分和的本质，就是平分和的大小的背包能否被刚好装满，也就是下标与值相等。 参考代码随想录思路的代码 1234567891011121314151617class Solution {public: bool canPartition(vector<int>& nums) { int sum =...

学习小结本周跟随《代码随想录》开始学习动态规划的相关题目，从基础的斐波那契数到爬楼梯，再到 01 背包问题，慢慢熟悉动态规划的五步法。《代码随想录》还提醒，调试重点是检查递推公式是否举例，检查打印 dp 数组是否和自己设想一致。 分析 dp 数组及其下标含义 确定递推公式 确定 dp 数组初始化 确定遍历顺序 举例分析 dp 数组是否如所想迭代 此外除了寻常的二维数组动态规划，也尝试做滚动数组的练习。 动态规划 斐波那契数 题意，给一个数字 n，求斐波那契数中的第 n 个数 方法，虽然就算不看代码随想录也能轻易写出，但简单题的重点在于熟悉套路方法，下面按五步分析 确定 dp 数组及其下标含义，这里的 dp[i] 代表斐波那契数中的第 i 个数 确认递推公式，题目给出 dp[i]=dp[i-1]+dp[i-2] dp 数组初始化，题目也给出dp[0]=0;dp[1]=1; 确定遍历顺序，从递推公式可见，就是从前向后（0-n）遍历 举例推导 dp 公式，0 1 1 2 3 5 8 13 21 …… 陆爻齐的解 1234567891011121314class...

学习小结本周跟随《代码随想录》学习回溯的剩余题目，如八皇后，全排列等问题，当初看上去可怕的题目，在回溯的套路下，显得也没那么难，重点在于理解整个回溯的树遍历过程。 通常回溯部分的函数无返回值，但当回溯只求全树唯一一个解时，比如[[全排列]][[解数独]]，可将回溯函数返回值设为 bool 类型，在一个叶子为 true，层层上传，避免无用遍历。 回溯 组合总和II 代码随想录 40. 组合总和 II - 力扣（LeetCode） 题意，与[[组合总和III]]类似，但待选数组内出现重复元素，且结果的组合不能重复 方法，重点是分清两种去重，一种是同一树支的去重（纵向），一种是同一树层的去重（横向），两者都可以通过用 used 数组实现，前者要求 used 中同值点不可同时 true 才能加入结果，后者要求同值点必须 true 该点才能加入结果；换句话，used 中 ture 的点说明在同一树支（路径）上 参考代码随想录思路的解法123456789101112131415161718192021222324252627282930313233343536373839class...

学习小结本周跟随《代码随想录》学习二叉树和二叉搜索树的相关题目，还在递归中主要学习了关于组合的一部分题目。 回溯，用代码随想录中的一句话概括：- for 循环横向遍历，递归纵向遍历，回溯调整结果集。 二叉树 二叉搜索树的最小绝对差 代码随想录 530. 二叉搜索树的最小绝对差 - 力扣（LeetCode） 题意，找二叉搜索树中任意两个节点两值之差的最小值 方法，由于二叉搜索树的本质是有序数组，按中序遍历比较相邻节点之差 陆爻齐的解法 与代码随想录思路相近1234567891011121314151617181920212223242526272829303132/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * ...

试题一 数据流图 数据流图 英文名 DFD 本质上就是描述数据流动的图 {:height 283, :width 512} 问题一 问图中的实体是什么 E1…… 方法：对着子图和说明找 问题二 问图中的数据是什么 D1…… 方法：对着子图和说明找 如果是问数据存储，在没有找到对应名字时，可以自拟符合名称 问题三 补充数据流，看分值，可能一分一条或两分一条 方法： 父图子图平衡logseq.order-list-type:: number对比父图和子图的数据流 加工既有输入数据流也有输出数据流logseq.order-list-type:: number 根据说明检查子图logseq.order-list-type:: number 问题四 拓展题，随缘得分 有问父图与子图的平衡，也就是数据流的属性、名字相同，数量相同，若父图有一条对应子图多条数据流，则也算平衡 试题二 数据库设计 基础知识 父实体与子实体 属性简单了解，比较少考{:height 338, :width 518} 联系分别是1对1，1对多，多对多多对多对多 1对多对多 关系模式 ...

数据结构与算法 由于时间不太充足，最后这部分就不看视频了，有什么不在原本知识库内的点就直接记录就好 哈夫曼树 只有度为 0 和度为 2 的节点 度 2 的点比度 0 的点少一个 森林转二叉树 首先，每个树分别转为二叉树，每层兄弟连，父节点只连第一个大儿子节点；然后第二课树做第一个树右节点，第三树做第二树右子树，以此类推 排序算法 哈希表 装填因子越小，冲突可能性越小 操作系统 与 [[软考_数据结构与算法]] 类似，都是补充，没时间全学 磁盘调度 移臂调度 先来先服务，就是先序位序考前的位置，随时改方向 最短寻道时间优先，优先找最近的，随时改方向 电梯调度，先向一边方向扫完在向另一边扫 单向扫描，电梯，但向一边扫完只会从另一边重新同方向再扫

网络设备 物理层互连设备 中继器、集线器（一种特殊多路中继器，可检测发送冲突） 数据链路层互连设备 网桥、交换机（多端口网桥） 网络层互连设备 路由器 应用层互连设备 网关 广播域和冲突域 在对应层能否划分 协议簇 ICMP属于网络层协议，用 IP 传送报文（差错报文） {:height 236, :width 412} 所有带T的除了TFTP其他都是TCP，所有不带T的除了POP3其他都是UDP​ 默认情况，FTP 服务器控制端口21，上传文件端口20 TCP 和 UDP 都是建立在 IP 协议上的 SNMP 是应用层协议，基于 UDP Telnet 是不太安全的远程登录协议（应用层），基于 TCP ICMP IP ARP RARP 都是网络层的 网络层协议 IP 提供服务通常是 无连接 和 不可靠 的 无连接：没确定目标系统做好接收数据准备就发送数据与此相对就是面向连接的传输 不可靠，目的系统不对成功接收分组确认 差错检测、流量控制、拥塞控制授权给其它各类协议 传输层协议...