尺取法

尺取法：

顾名思义，像尺子一样取一段，借用挑战书上面的话说，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以说尺取法是一种高效的枚举区间的方法，是一种技巧，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情况下尺取法不可行，无法得出正确答案，所以要先判断是否可以使用尺取法再进行计算。

使用尺取法时应清楚以下四点：

1、什么情况下能使用尺取法? 2、何时推进区间的端点？ 3、如何推进区间的端点？ 4、何时结束区间的枚举？

尺取法通常适用于选取区间有一定规律，或者说所选取的区间有一定的变化趋势的情况，通俗地说，在对所选取区间进行判断之后，我们可以明确如何进一步有方向地推进区间端点以求解满足条件的区间，如果已经判断了目前所选取的区间，但却无法确定所要求解的区间如何进一步得到根据其端点得到，那么尺取法便是不可行的。首先，明确题目所需要求解的量之后，区间左右端点一般从最整个数组的起点开始，之后判断区间是否符合条件在根据实际情况变化区间的端点求解答案。

借助问题来进一步去理解尺取法

问题【1】

给你一个序列(大小为n)，让你去找到一个区间[i,j] , 区间内所有数的和 sum >= 15 求出满足这样要求的最小的区间长度

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdbool>
#include <string.h>
#include <math.h>

using namespace std;

//5 1 3 5 10 7 4 9 2 8

int main()
{
    int a[10] = {5,1,3,5,10,7,4,9,2,8};
    int i = 0,j = 0,ans = 100;
    int sum = a[0];
    while (i <= j && j < 10)
    {
        if (sum >= 15)
        {
            //   ans = min(ans,j-i+1);
            if (sum == 15)
            {
              //  printf("i = %d j = %d
",i+1,j+1);
                ans = min(j-i+1,ans);
                sum -= a[i];
                i++;
            }
            else
            {
                ans = min(ans,j-i+1);
                sum -= a[i];
                i++;
            }
        }
        else
        {
            j++;
            sum += a[j];
        }
    }
   printf("%d
",ans);
    return 0;
}

View Code

问题【2】

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长（连续）子数组的长度。

示例 1：

输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：

输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

提示：

1 <= A.length <= 20000
0 <= K <= A.length
A[i] 为 0 或 1

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#include <cstdbool>
#include <string.h>
#include <math.h>

using namespace std;

//5 1 3 5 10 7 4 9 2 8
char a[20005];

int main()
{
    int a[11]={1,1,1,0,0,0,1,1,1,1,0};  //这里数组是定死定，你也可以自己输入
    int left = 0;
    int res = 0;
    int k;
    cin >> k;
    for (int right = 0;right < 11;right++)
    {
        if (a[right] == 0)
            k--;
        if (k < 0)
        {
            if (a[left] == 0)
                k++;
            left++;
        }
        res = max(res,right-left+1);
    }
    printf("%d
",res);
    return 0;
}

View Code