2020-2021:teams:no_morning_training:shaco:知识点:基础:尺取法
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:no_morning_training:shaco:知识点:基础:尺取法 [2020/06/02 21:57] shaco |
2020-2021:teams:no_morning_training:shaco:知识点:基础:尺取法 [2020/06/02 21:58] (当前版本) shaco |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| 通常是具有单调特征序列、寻找连续子区间接近目标值的问题中应用。\\ | 通常是具有单调特征序列、寻找连续子区间接近目标值的问题中应用。\\ | ||
| 关注左右两端的指针，当选定的区间中所关注的值大于目标值时将左侧指针右移，当选定的区间中所关注的值小于目标值时将右指针右移，直至终点。枚举区间的复杂度为O(n)，计算区间的值的复杂度通常是O(1)，不排除有例外。\\ | 关注左右两端的指针，当选定的区间中所关注的值大于目标值时将左侧指针右移，当选定的区间中所关注的值小于目标值时将右指针右移，直至终点。枚举区间的复杂度为O(n)，计算区间的值的复杂度通常是O(1)，不排除有例外。\\ | ||
| - | 在这个过程中间接枚举了每个区间，但与直接枚举并不同，在尺取法应用的问题中一般对区间有要求，较短的区间往往无法符合要求因此将它们包含的较大的区间枚举到即可。\\ | + | 在这个过程中间接枚举了每个区间，但与直接枚举并不同，在尺取法应用的问题中一般对区间有要求，较短的区间往往无法符合要求因此将包含它们的较大的区间枚举到即可。\\ |
| 看几个例题 | 看几个例题 | ||
2020-2021/teams/no_morning_training/shaco/知识点/基础/尺取法.1591106235.txt.gz · 最后更改: 2020/06/02 21:57 由 shaco
