摘要: 倍增法原理、代码模板、例题与应用场景
【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings
$1 倍增法算法思想
在递推状态的时候,只递推状态空间中 2 的幂次,当需要求其它位置的时候,利用以下性质,可以用此前求过的 2 的幂次上的状态现算出来:
1 | 任意整数可以表示成若干个 2 的幂次的和 |
这种算法称为倍增法。倍增法与二进制划分结合可以降低很多问题的时间和空间复杂度,例如快速幂,倍增优化DP。
模型问题1
长度为 N 的数列 A[0..N−1],处理在线 Q 个查询:每次给定一个整数 T,求最大的 k 使得 A 中前 k 个数的和 k−1∑i=0A[i]≤T,其中 0≤T≤N−1∑i=0A[i]。
算法1
每次询问都对 k 进行 O(N) 的枚举,总 O(NQ)。
算法2
预处理前缀和 S[i] := A[0..i-1]
,每次查询,二分 k,通过比较 S[k]
和 T 的关系调整 K 的上下界。总 O(N+QlogN)。
算法3:倍增法
1 | p = 1, k = 0, sum = 0 |
模型问题2
这是一个交互问题。
您有一个升序整数数组,其长度未知。您没有访问数组的权限,但是可以使用 ArrayReader 接口访问它。你可以调用 ArrayReader.get(i)
:
返回数组第ith个索引(0-indexed)处的值(即 secret[i]
),或者如果 i 超出了数组的边界,则返回 231−1
你也会得到一个整数 target。
如果存在 secret[k] == target
,请返回索引 k 的值;否则返回 -1
你必须写一个时间复杂度为 O(logn) 的算法。
提示:
1 | 1 <= secret.length <= 1e4 |
示例 1:
输入: secret = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 存在在 nums 中,下标为 4示例 2:
输入: secret = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不在数组中所以返回 -1
算法:倍增法
由于数组有序,可以考虑二分的方法。但这里数组的长度未知,二分的算法不好实现。但可以通过倍增法处理。
从数组最左边 A[0]
往右走,每一步走 step,也就是上一步访问 A[i]
,走一步之后访问 A[i+step]
。初始时 step = 1
。
假设当前访问了 i 位置的数据 A[i]
,并且 A[i] < target
,此时我们考虑下一个数据 A[i + step]
,
- 如果当前访问的
A[i + step] == target
那么就找到了; - 如果
A[i + step] < target
,那么 target 的位置在i + step
的右边,向右走i += step
,然后将step
翻倍; - 如果
A[i + step] > target
,那么 target 的位置在i + step
的左边,不能向右走,而是将step
减半。
代码 (C++, 模板)
1 | class Solution { |
$2 倍增法应用场景
1. 快速幂
参考文章:
2. LCA
参考文章:
3. RMQ
参考文章:
4. 倍增优化DP
参考文章:
5. 多重背包
参考文章:
6. 后缀数组
参考文章:
$7 理想跳表
参考文章: