CSGrandeur's Thinking

Cogito Ergo Sum

倍增与稀疏表(ST表)

倍增思想的核心在于通过预处理每个状态的跳跃步长(如2的幂次),将线性时间的操作优化为对数时间。其关键在于构建一个跳跃表,每个位置存储跳跃不同\(2^k\)步后的结果。对于多次跳跃问题,将总步数分解为若干2的幂次之和,逐次跳跃即可高效求解。

阅读全文 »

分块

字面意思,把数据分成一块一块去处理。

比如数据存在一段一段连续的相同值时,把相同的值看作一个的"块",从而快速跳过。

比如把要经常批量处理的数据分成一个一个的块,在批量处理时,整个被覆盖的块做整体处理,没整个覆盖的再挨个处理。

阅读全文 »

单调队列

单调队列是一种特殊的队列结构,通过维护队列元素的单调性(递增或递减),可以在O(1)时间内得到一段区间内的最值。

阅读全文 »

单调栈

栈内元素保持单调递增或单调递减的顺序,常用于解决"寻找最近的比当前元素大/小的元素"这类问题。

阅读全文 »

双指针(尺取)

通过两个(或多个)移动的标记,高效地探索或处理数据结构中的连续部分,以简化问题并加快求解速度,通常称为双指针、尺取或滑动窗口等。

阅读全文 »

离散化

离散化是一种将无限空间中的有限个体映射到有限空间中的方法,常用于处理数据范围很大但实际数据量较小的问题。

阅读全文 »

三分

三分是一种用于求解单峰/单谷函数极值的搜索算法,通过每次将区间分成三份并比较两个分点的函数值来缩小搜索范围。

阅读全文 »

二分答案

在线性表章节已了解二分查找的基本原理,当一个问题的答案具有单调性时——即随着答案的增大或减小,判定条件的结果也呈现单调变化,比如答案越大条件越容易满足,或者答案越小条件越容易满足,可以通过二分查找,在过程中根据判定条件是否满足来调整二分的方向逼近解的过程。

阅读全文 »

贪心

贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择,从而希望导致结果是最好或最优的算法策略。

阅读全文 »

前缀和、差分

前缀和与差分作为互补技术,分别通过预处理和逆运算高效处理数组的区间查询与批量修改问题。

阅读全文 »
0%