还在苦恼于面试中只能写出 $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...

Leetcode 937. 重新排列日志文件, 一个简单题但是可以好好品一下 STL sort 里的 Comparison Function 题目很简单, 照着模拟即可, 主要考点就是让你写一个自定义比较函数. 对于 Comparison Function, 我总是很迷惑, 什么时候该写小于, 什么时候该写大于, 什么时候该总是返回 true, 而这又意味着什么. class Solut...

一切动态规划问题, 都是有穷自动机 ——Jebearssica 通常而言, 做动态规划都涉及求最值, 一般的解题思路有自上而下递归和自底向上动规. 按照人类思路自上而下递归比较好写, 写出来之后用哈希表剪枝防止重复递归之后的时间复杂度就和动态规划相当了. 再将整个递归函数封装, 转变思路自底向上即可转换成动态规划. 按照正常的思路, 动态规划的解法都可以递归实现, 因此主问题的...

起因, Leetcode里的587.安装栅栏, 第二次遇到凸包问题了, 不会就学, 老碰见很烦 基本概念 凸多边形: 所有内角大小都在 $[0, \pi]$ 范围内的多边形 凸包(Convex Hull): 在平面上能包含所有给定点的最小凸多边形叫做凸包 向量积判断点在直线哪一侧: 右手螺旋定则, 直线方向向量与直线上任意一点与判断点向量的积, 为正则在左侧, 为零则在线上...

vscode里面有个 markdown lint 的插件, 用来 format markdown 挺方便好看的, 还支持自定义规则. 那么就想一想能不能移植到 GitHub action 上自动化. 如果只是自己写的话, 直接在本地 vscode 里自定义规则就行了, 如下 { "markdownlint.config": { "MD004": false, ...