每个人都有自己的阅读方法，对我而言，我主要把阅读分为三种： 细读、扫读、跳读。 接下来就展开讲一讲这三种的区别和联系。 首先是细读，这是我认为对我而言收获最大的阅读方式。 还记得小时候我在图书馆抱着一本书看，把书里面的每一个意思都理解清楚，非常仔细。想的我小脑袋都要爆炸了。每次读完书出来，大脑都是发烫的，但是收获却是巨大的。 长大一点了反而没有这种阅读体验了。 或许是太急功近利、失去耐心。 因此选择了第二个阅读方式：扫读。 结论先行：这种方式效果最差，并且消耗注意力。 说一下我在进行扫读的一个场景：往往是内心知道这个东西不那么重要，但是又贪心，怕错过什么重要的东西。 但是！ 这么多年来的阅读经… More »

Z算法核心 和KMP算法类似，Z算法大核心也是那一个数组，或者叫z函数。 首先我们定义一下什么叫z数组。 一句话说：在一个字符串里面，从当前符号匹配字符串开头，能匹配到的最大长度。 举个例子： s: abcabca z: 0004001 需要注意的是z[0]=0。为什么z[3]=4?可以把从i=3这个字符串抽出来，我们比较 s: abcabca i=3 abca 可以看到从i=3开始，这个和s前缀比较最大长度就是4。 如何得到z数组 首先我们来看暴力法怎么做： vect… More »

字符串匹配是一个很常见的问题，例如从一个长的字符串：saippuakauppias，我们要匹配模式字符串pp。可以用暴力破解法，复杂度是$O(nm)$n是长字符串的长度，m是模式字符串的长度。 于是几个聪明的人发明了KMP算法。 暴力破解法的一个很大的问题就是需要一个一个比对，如果比对错了，那么下次就从下一个还是一个一个比对。这样的坏处就是没有好好利用之前已经得到的信息。KMP算法就很好的解决了这个问题，可以利用之前的信息。 $\pi$（pi）表 KMP算法最重要的一个就是$\pi$表。 什么是$\pi$表？一句话概括：预处理模式串P中… More »

Trie是一个可以快速检索字典的一种数据结构。本篇文章我们以存储英语单词，存储a-z的26个英语字母。 class TrieNode { TrieNode* children[26]; bool leaf; }; 上面， children[]： 大小为26的数组存储指针。由于我们是可以通过 字母-'a'的方式得到每一个字母的数值，因此字母可以和数组下标对应上。 leaf：标志是否是一个单词的结尾 图片来源于https://www.geeksforgeeks.org/ Trie的基本操作 Trie最主要的操作有… More »

假设有一个长度为6数组： a=[0,0,0,0,0,0] 现在想在L-R之间添加3，那么就需要每一个数迭代的添加，但是这样就太慢了。这个时候差分数组的作用就体现出来了：只需要记录两个端点的情况，然后最后统一处理就可以了。 例如L=1，R=3，循环增加得到的结果是a=[0,3,3,3,0,0]。 我们可以记录一个差分数组d[1]=3, d[4]=-3。于是d=[0,3,0,0,-3,0]，在最后得到结果的时候就是： $a[i]=a[i-1]+d[i]$ 那么$a[0]=0,a[1]=a[0]+d[1]=3,a[2]=a[1]+d[2]=3…a[4]=a[3]+d[4]=3+(-3)=0$。 可以… More »

BIT是什么？全称Binary indexed tree，或者Fenwick tree。用在区间查询和更新里面。相对于前缀和数组的一个优势在于可以动态更新数据，复杂度是$O(logn)$ 核心公式： $tree[k]= sum_q(k− p(k)+ 1,k)$ $p(k)$代表可以被k整除的最大的2的幂数。$p(k)=k&-k$。为什么？由于$k&-k$得到的是k的最低有效位，实际上k的最低有效位就是刚好能被k整除的数。因此可以快速的算$p(k)$。 这个公式的规律就是如果是奇数那么这个范围就是只有自己。 核心实现 … More »

DFS，深度优先遍历，图的一种常用的遍历方式。核心思想是从每个节点，沿着子节点一直走，走到最深，因此叫做深度优先。 常见的方式是用递归的方法实现的，但是递归有一个问题需要注意递归的深度，因此在某些情况下需要用到迭代到方式。 DFS的本质是一个栈的形式。栈是一种后进先出的数据结构，也就是说会优先处理最近添加的数据。这个和DFS的处理方法不谋而合。因此我们可以用这个栈来模拟DFS过程。 为了防止重复访问节点，因此需要一个visit数组来去重。 迭代实现cpp代码如下： # 传入一个根节点 # 我们采用邻接表的方式表示一个图。邻接表就是给定一个节点，可以找到这个节点的全部邻居。 #include &… More »

题目来自于cses: # Company Queries II 解体思路： 这是关于树问题比较典型的问题求最小公共祖先。 首先想到的应该是把两个需要查询的节点首先拉到一层，之后一层一层的网上查找。 但是这样的时间复杂度是：$O(q \times (lgn + n)$。接近$O(N^2)$时间复杂度肯定是不行的。 现在的问题就是如何去优化一层一层查找这个过程。 其实也可以用倍增法。 在把两个节点拉到同一水平之后，贪心的思想，让节点同时尽可能往上面跳跃。但是不能让他们跳到相同的点，因为相同点其实就是根节点1了。因为所有数都是可以用二进制表示的，参考[[倍增法/index|index]]。 那么可以… More »

最近关于vibe coding很火啊，针对这个问题，我结合我目前做的一些项目谈一谈我对它的看法。 其实与其说是vibe coding，不如说是分享一下近期对于ai编程辅助的一些看法。 我的一个真实的项目经历是，针对一个车辆识别的项目，我是一点这方面的知识都没有的，但是使用ai却让我逐步完成了这个项目，目前已经接近上万行python代码了。 这个过程如下： 直接指导ai的就不用说了，重点说一些踩的坑。 不要太依赖AI Google搜索看博客看开源比纯问ChatGPT效果更好。虽然现在ChatGPT搜索的能力确实很强，但是光是依赖AI对于做… More »

解释 倍增法的核心起源于每一个数字都可以使用二进制表示： 13 = 8+4+1=0b1000 + 0b0100 + 0b0001 那么我们先预处理这样的一个表，之后是不是就可以直接使用，快速得到结果呢？相比于一层层的获取的时间复杂度O(n)，倍增法的事件复杂度是O(lgn) 数据结构： up[i][j]表示在i点$2^j$跳达到后的点。 up[i][0]表示i点点直接parent 核心公式： mid = up[i][j-1] // 从i经过2^(j-1)跳到达mid up[i][j] = up[mid][j-1] //从mid经过2… More »