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 »
特别喜欢Vim，是Vim让我习惯了没有鼠标的日子，高效而流畅。 无奈作为一个中文用户，有输入拼音的需求。听说Emacs由ctrl键位控制，不需要频繁的切换中英文，中文状态下也可以流畅使用快捷键，于是开始学习Emacs。 刚开始不太习惯，个人感觉没有Vim流畅，不过在习惯之后，也是逐渐熟悉起来，打字也更加流畅，特别是在中文环境下。 除了有一个不太好的点是，Emacs配置不好弄，我会一点lisp，但是还是很难去搞配置。而且里面的插件都很老了，不太好用。相比之下，VS Code插件就丰富多了。特别是我最喜欢的ssh插件，这里推荐一下VSCode的ssh插件，连上之后基本上更本地开发没有什么太大的区别… More »
One of the most repeated pieces of advice throughout my career in software has been “don’t repeat yourself,” also known as the DRY principle.1 For the longest time, I took that at face value, never questioning its validity. That was until I saw actual experts write code: they copy code all the time2… More »