我以为我懂了, 实际没总结我就不懂. 当然, 我以为我总结了我就应该懂了, 实际我不知道我懂没懂. ——废话大师本人 起因Leetcode 2334. 元素值大于变化阈值的子数组, 周赛这道无从下手, 根本看不出是并查集. 当然后来第一反应应该是双指针 + 单调栈(?), 但实际单调栈也没怎么看出. 总而言之, 先总结一下并查集 朴素并查集大致思想 一个森林结构支持查找与合并,...

Java自带一套 Memory Collection, C++ 没有, 了解一下内存分配与回收还是挺重要的. 毕竟旁观室友面 Java 岗, 真的是一直问这个. 基础知识 局部对象(local member), 内存在栈上, 随着作用域消失而消失回收 全局对象(static member), 内存在堆上, 随着整个程序结束而消失回收 内存分配 内存分配过程如下, 总是先分...

想到哪写到哪, 杂乱 const 修饰成员函数 一个常见的情形如下: // 声明一个 const 类, 并输出其数据 const T m1; cout << m1.data(); 一个容易令人忽视的地方在于, 成员函数 member.data 的设计会漏写 const, 从而导致类型无法转换的报错( 指针引用转为 const 指针 ) // 隐式参数 const me...

大致思想, 一颗 n 叉树, 从根结点至一个合法结点的路径所构成的字符串为该合法结点所代表的字符串. 其中 n 为树存储的字符集大小. 结点定义 就普通多叉树的结点定义, 在此基础上增加一个标记用来判断当前结点是否合法( 构成字符串 ) struct node { bool isEnd; vector<node *> child; node(int ...

还在苦恼于面试中只能写出 $O(n\sqrt{n})$ 时间复杂度的素数筛选吗, 快来接触埃氏筛吧 暴力枚举 顾名思义, 简单粗暴, 不过要是真写出一个纯暴力 $O(n^2)$, 甚至没用平方根的技巧的话, 那是真的会凉凉 int sieve(int n) { int res = 0; for(int cur = 2; cur <= n; ++cur) {...

本来是一个掌握得挺好的一个知识点的, 但最近做题做下来的感觉总是在纠结当前区间内的元素个数. 那就总结一下这个知识点, 看看能不能通过梳理各种区间情况来让这类题写得更顺畅一点. 不知道有多少人和我一样会莫名其妙纠结, 区间 [L, R] 之间有多少元素? 再举个例子, 两个确定日期之间有多少天等等类似问题. 不过这种问题其实主要就是在是否清楚了解, 你所搜索的区间开闭情况 双指针...

属实是离谱啊, 没见过这种报错的. 两个紧邻大括号会直接导致 Liquid 报错 Liquid Exception: Liquid syntax error (line 4): Variable '{ {0,1}' was not properly terminated with regexp: /\}\}/ 我服了, 上面报错信息都不能直接写上, 得用空格间隔开 你要想复现...

你要不嫌麻烦, 不怕代码量大, 面对几乎一切有关区间信息维护的问题, 你都可以用线段树解决. 毕竟, 它可以实现 $O(\log{N})$ 的区间修改, 区间查询. 上面说的区间, 当然也包括单点这个特例. 上面说的查询, 不仅包括区间和, 区间最值也行. 换言之, 只要你维护该区间的信息能够通过左右孩子结点表达, 那么这个信息都能够通过线段树维护. 大致思想 线段树通常采用堆...

借着一道我愿称之为究极 BFS 的题目总结一下 BFS, Leetcode 2258. 逃离火灾, 顺便延伸至 dijkstra BFS(宽度优先搜索) 和这道题的背景非常契合的, 火焰从开始点向四周扩散, 就是一个典型的 BFS 搜索过程. 我们每次都访问同一层(同一时刻)燃烧的点, 并将周遭可燃点推入队列以供下次访问. BFS 相较于 DFS 能够得到当前点至起始点的最短路径(包含...

Leetcode 1823. 找出游戏的获胜者, 经典约瑟夫问题, 大致意思是: “N个人围成一圈, 第一个人从1开始报数, 报M的将被杀掉, 下一个人接着从1开始报. 如此反复, 最后剩下一个, 求最后的胜利者”. 如果知道递归公式就可以在 $O(N)$ 的时间内完成计算. 队列模拟 队首出列进队尾, 重复 k - 1 次后取出队首, 时间复杂度 $O(NK)$, 要是两者乘积小于 1...