- 博客(50)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 如何用VSCode和Clangd与Clang-Format插件高效阅读Linux内核源码及写驱动
在写驱动时，对内核方法和对象的提示非常全和准确。
2024-03-23 02:11:38
958
原创 2023-05-05 背包问题
有N件物品和一个容量为V的背包，第i件物品的体积是v[i]、价值是w[i]，，求将哪些物品放入背包可以使得价值总和最大。这里的w是weight即权重的意思这是最基础的背包问题，"01"就是指每种物品要么选要么不选，我们定义状态fij表示从前i件物品中选出容量为j的背包能获得的最大价值状态定义，根据第i个物品选还是不选，分成两种情况fijfi−1j−vi]]wifijfi−1j取两者的较大值即为最终的最大价值fijmaxfi−1j−。
2023-05-05 20:34:43
886
原创 2023-05-04 线性DP_力扣练习
线性动态规划的主要特点是状态的推导是按照问题规模 i 从小到大依次推过去的，较大规模的问题的解依赖较小规模的问题的解。这里问题规模为 i 的含义是考虑前 i 个元素 [0…i] 时问题的解。dp [ n ] : = [ 0. . n ] 上问题的解从以上状态定义和状态转移可以看出，大规模问题的状态只与较小规模的问题有关，而问题规模完全用一个变量 i 表示，i 的大小表示了问题规模的大小，因此从小到大推 i 直至推到 n，就得到了大规模问题的解，这就是线性动态规划的过程。
2023-05-04 23:48:25
511
原创 2023-05-03 线性模型与区间DP
接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为12。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。如果有四个行李，重量从小到大分别是a、b、c、d，显然(a, b)和(c, d)的分组最优，因此2k个行李一定是先从小到大排序，然后依次取两个配对。因为是n个物品中选2k个，然后分成k组，直接DP不好找状态，需要先挖掘题目的性质，考虑选出了2k个行李后如何分组可以最小化疲惫度之和。
2023-05-03 22:13:41
505
原创 2023-04-26 力扣LeetCode上的DP动态规划问题分类汇总
所有线性递推关系都可以用矩阵快速幂做，可以O(logN)，最典型是斐波那契数列。计数型DP都可以以组合数学的方法写出组合数，然后dp求组合数。本质是 dfs + 记忆化，用在状态的转移方向不确定的情况。策梅洛定理，SG 定理，minimax。
2023-04-26 23:00:05
648
原创 2023-04-24 算法面试中常见的贪心算法问题
假设你想给小朋友们饼干。每个小朋友最多能够给一块儿饼干。每个小朋友都有一个“贪心指数”，称为g(i)，g(i)表示的是这名小朋友需要的饼干大小的最小值。同时，每个饼干都有一个大小值s(i)。如果s(j) >= g(i)，我们将饼干j分给小朋友i后，小朋友就会很开心。给定数组s和g，问如何分配饼干，能更让最多的小朋友开心。如 g = [1, 2, 3], s = [1, 1]，结果为1如 g = [1, 2], s = [1, 2, 3]，结果为2代码见。
2023-04-24 23:28:38
480
2
原创 2023-04-23 算法面试中常见的动态规划问题
将原问题拆解成若干子问题，同时保存子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案。简单说：自下而上地，先解决最小子问题，然后最小子问题不断向上推，最终解决完整的问题体会其中自下而上地解决问题的思路，有点类似数学归纳法你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
2023-04-23 21:42:55
648
原创 2023-04-19 算法面试中常见的递归和回溯问题
我们在路上走着，前面是一个多岔路口，因为我们并不知道应该走哪条路，所以我们需要尝试。尝试的过程就是一个函数。,这里是floodfill的四连通分量问题，可以用DFS解决，在递归回退时记得要把相关状态重置下。和46、47差不多，简单适配下即可,通过变化索引的方式去遍历子数组要比新建一个子数组效率高很多。和39类似，就是把i换成i+1，然后再添加到result前判重一下即可。遍历每个点，DFS找到既能到达太平洋又能到达大西洋的点加入到结果中即可。用基于递归的回溯法解决组合问题。图中的i是下面的r，
2023-04-19 23:48:32
430
原创 2023-04-17 算法面试中常见的树和递归问题
257.二叉树的所有路径给定一个二叉树，返回所有从根节点到叶子节点的路径。说明: 叶子节点是指没有子节点的节点。示例:输入:1/ \2 35输出: ["1->2->5", "1->3"]解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3} // 获取并拼接左子树字符串 List < String > listL = binaryTreePaths(root . left);i ++) {
2023-04-17 23:08:41
132
原创 2023-04-16 算法面试中常见的栈和队列问题
本节类似问题：150、71##2 栈和递归的关系，以二叉树的前、中、后序遍历为例(图的深度优先遍历DFS原理是一样的)参考的6.6和6.7##3 使用栈模拟递归递归实际是一种系统栈调用##4 队列的典型应用：二叉树的层序遍历以及图的BFS可以记住第几层的BFS不用记住第几层的BFS此外还有107、103、199相比102实际就加了这一行相比102实际只加了下面几行，用于偶数行逆序当到达本层最后一个元素时才加到list中。
2023-04-16 23:31:33
660
原创 2023-04-15 算法面试中常见的链表问题
本章的两个基础类如下链表的节点类。toString()在debug时实时查看链表很有用链表的显示工具类。create用于从数据创建链表，show用于把head作为头结点的链表表示成一个字符串的形式。
2023-04-15 23:27:37
401
原创 2023-04-14 算法面试中常见的查找表问题
执行用时 :14 ms, 在所有 Java 提交中击败了81.61%的用户；下面的实现行用时 :13 ms, 在所有 Java 提交中击败了66.68%的用户；,转化为Two Sum的问题，但是注意这里的TwoSum可能不止有唯一解。解题思路：把C+D的组合放入查找表中，通过查找A+B是否等于-(C+D)在上一节的基础上加一个判断即可：在大小为k的窗口中找值差不大于t的即可。第2种解法：把遍历过程前面的元素作为查找表，顺便还能保证顺序。，相似的思路，只是不用维护窗口了。基于HashMap的实现。
2023-04-14 22:50:24
644
原创 2023-04-12 面试中常见的数组题目
88 Merge Sorted Array：给定两个有序整型数组nums1, nums2，将nums2的元素归并到nums1中。j]，计算其和sum，验证sum >= s，时间复杂度O(n^3)解题思路：维护一个大小为k的最小堆，遍历一遍数组，最后的最小堆堆顶元素就是第k大的元素。不算调整窗口长度来看窗口数组是否满足条件，过程中记录窗口数组的长度，不断取最小值。，l和r均在数组范围内，不断调整l和r使得区间内的元素满足题目要求。核心思想：用于求解符合条件的连续子数组问题，方法是维护一个范围。
2023-04-12 21:54:13
436
原创 2023-04-11 无向图的匹配问题
下面的增广路径是指首尾都是非匹配点的路径，和上一章残量图中的增广路径不同1.在二分图中2.从左侧的一个非匹配点出发3.从右向左的边，永远走匹配边4.匹配边和非匹配边交替出现(称为交替路5.终止与另外一个非匹配点(即增广路径首尾都是非匹配点交替路和增广路径的区别：增广路径是起始点都是非匹配点的交替路。增广路径一定是交替路，但交替路不一定是增广路径6.有增广路径，意味着最大匹配数可以加17.遍历完左侧所有尚未匹配的点，即找到最大匹配。
2023-04-11 23:14:03
836
原创 2023-04-10 网络流和最大流问题
算法时间复杂度Edmonds-Karp算法O(VE^2)Dinic算法O(VE^2)MPM算法O(V^3)
2023-04-10 23:26:09
869
原创 2023-04-09 有向图及相关算法
定义：在一个有向图中，对所有的节点进行排序，要求没有一个节点指向它前面的节点，最终的排序结果就是拓扑排序价值：当现实中存在图状约束时，要你给出一个约束下可行的图遍历方便，这个时候拓扑排序就用上了~比如选课、选旅游路线等floodfill最小生成树桥和割点二分图检测。
2023-04-09 23:41:18
1895
原创 2023-04-08 无向有权图之最短路径问题
初始化distances[start]=0，其余distance值为+∞对所有的边进行第1次松弛操作,则求出了到所有点经过的边数最多为1的最短路对所有的边进行第2次松弛操作,则求出了到所有点经过的边数最多为2的最短路对所有的边进行第3次松弛操作,则求出了到所有点经过的边数最多为3的最短路对所有的边进行第v-1次松弛操作,则求出了到所有点经过的边数最多为v-1的最短路如果对所有边再进行一次松弛操作，还能更新最小路径的值数组distances，则说明图中包含负权环。
2023-04-08 23:27:52
1534
原创 2023-04-07 无向有权图之最小生成树问题
用n-1条边把含有n个顶点的图连接起来就形成了图的生成树,一个图一般都有很多个不同的生成树在有权图中，不同的n-1条边形成的不同生成树其权总和一般也就不同，权值总和最小的就叫最小生成树带权图最小生成树问题切分定理Kruskal求最小生成树Prim求最小生成树。
2023-04-07 23:29:27
2089
原创 2023-04-04 哈密尔顿问题和路径压缩
从一个点出发，沿着边走，经过每个顶点恰好一次，之后再回到出发点，过程中经过的路径就叫哈密尔顿路径关键是如下两个特点回到出发点经过每个顶点，并且每个顶点只能经过一次。
2023-04-04 23:31:01
1472
原创 2023-04-02 桥和割点以及图的遍历树
对于无向图，如果删除了一个顶点(顶点邻边也删除)，整个图的联通分量个数也变化，则这个点成为割点(Cut Points 或 Articulation Points)比如下图，删除定点3或5，图都会从1个联通分量变成2个联通分量。生活中比如连接两个班级的是班长，一个班长生病，两个班级就无法联谊了，即变成两个各自为战的群体了。
2023-04-02 23:15:40
406
原创 2023-03-31 图的广度优先遍历
下面图的x就是指存储遍历点的容器类型，当是Stack时就是深度优先遍历，当是Queue时就是广度优先遍历，其实也可以是其他的容器类型，比如是个随机弹出的容器类型，那么遍历就相当于是随机遍历了，这个思想在刘老师的《看地见的算法 7个经典应用诠释算法精髓》里有应用到。返回最短路径经过的点和最短路径的值，实际就是加了一个distance数组，记录了BFS过程中经过的点到起点source的距离(无权图默认边长是1，经过一条边加1即可)。代码的图示如下，左侧是DFS的单源路径问题，右侧是BFS的单源路径问题。
2023-03-30 21:43:55
184
原创 2023-03-30 图的深度优先遍历的应用
顶点可以分成不相交的两部分图的每条边的两个端点隶属于划分出地两部分中的一部分下面图里左边的二分图实际等效于右边的图，只是我们把连线调整了下下面是二分图的定义记录更多信息递归函数dfs()返回值联通分量ccid无路径问题(单源路径)pre有，是否遍历到了target点环检测hasCycle有，是否找到环二分图检测有，是否是二分图。
2023-03-29 23:52:47
374
原创 2023-03-27 哈希表
上面代码中的int[26] freq就是一个哈希表，每个字符都和一个索引相对应，查找的时间复杂度都是O(1)把具体的数据类型转换成唯一的索引的函数就叫哈希函数，我们其实要实现所有数据类型的通用哈希函数还是很麻烦地，关键问题是哈希冲突。
2023-03-26 23:26:06
44
原创 2023-03-26 红黑树
对于完全随机的数据，普通的二分搜索树很好用。但是对于较有序的数据容易蜕化成链表，性能就会大大降低。对于查询(contains)较多的情况，平衡的BST即AVL树很好用。但是旋转次数比较多，会影响插入节点(add)的性能。对于插入(add)较多的情况，保持绝对黑平衡的红黑树很好用。但是红黑树牺牲了平衡性(2logn的高度)，所以会影响查询(contains)的性能。红黑树的统计性能更优：即从数学角度上看，综合增删改查所有的操作，红黑树是平均性能最好的。
2023-03-25 21:17:48
56
原创 2023-03-25 AVL平衡树
对任意一个节点，其左子树和右子树的高度差不能超过1平衡二叉树的高度和节点数量之间的关系也是O(logn)的平衡二叉树某个节点的高度值=max(左子树高度值，右子树高度值)+ 1。+1时因为父亲节点比子节点高一层。叶子节点的高度值认为是1，左右子树为空高度认为是0。在下图中用黑色表示平衡二叉树某个节点的平衡因子=左子树高度-右子树高度值，子树为空平衡因子认为是0在下图中用蓝色表示加入新节点后，沿着新节点的插入的置向上维护平衡性进行旋转的时机是在add中当更新节点高度和平衡因子后。
2023-03-24 23:18:14
139
原创 2023-03-21 Trie字典树
也称字典树Digital Tree；前缀树Prefix TreeTrie是一个多叉树，通常只用来处理字符串前面几章我们一直在用的都是二叉树。
2023-03-21 21:58:11
39
原创 2023-03-20 线段树也称区间树
对于有一类问题，我们关系地是线段(即区间)操作含义使用数组实现使用线段树实现更新更新区间中一个元素或者一个区间的值O(n)O(logn)查询查询一个区间[i, j]中的最大值、最小值或区间数字和O(n)O(logn)显然我们应该用线段树来解决问题。
2023-03-20 23:20:19
81
原创 2023-03-19 堆和优先队列
PriorityQueue实际上是一个堆（不指定Comparator时默认为最小堆），通过传入自定义的Comparator函数可以实现最大堆//小顶堆，默认容量为11 PriorityQueue < Integer > maxHeap = new PriorityQueue < Integer >(11 , new Comparator < Integer >() {//大顶堆，容量11 @Override public int compare(Integer i1 , Integer i2) {
2023-03-19 22:43:48
63
原创 2023-03-17 C语言深度解析(1):编译的详细过程
我们这里虽然介绍的是c程序的编译过程，但是实际上所有编译型语言的编译过程，大致是类似的。
2023-03-17 22:04:03
62
原创 2023-03-14 二分搜索树BST
第1步访问节点的顺序在相对于2和3的位置决定了是前、中、后序遍历的哪一种/*** 遍历以node作为根节点的二分搜索树// 递归终止条件 if(node == null) {// 遍历到null节点就返回上一层递归 return;} // 递归组成逻辑 // 1.访问当前节点。需要存储时可以放到list中 System . out . print(node . e + " ");// 2.遍历左子树 preOrder(node . left);
2023-03-14 22:33:35
195
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人