以欧拉计划第八题讲解滑动窗口法
如果现在这里有1000个数字
731671765313306249192251196744265747423553491949349698352031277450632623957831801698480186947885184385861560789112949495459501737958331952853208805511125406987471585238630507156932909632952....（更多详见欧拉原题）
请你找出其中相邻五位最大的乘积（欧拉原题可不止这么点位置，我就是举个例子！后文附欧拉习题链接、原题、数据、源代码）
你会怎么计算？
我相信你一定已经有了思路：读入，然后暴力求解，然后输出
输入部分
但是首先我们遇到了第一个问题:该怎么输入呢？
上述相邻的数个数字
电脑该如何判断，第一个要输入的数字，是7，还是73，还是731，还是73167…呢？
我来提供一种思路：
将数字当作字符来处理。
char num[1010];
int len=0;
while(~scanf("%s",num+len))len=strlen(num);
这串代码首先声明了一个字符类型的数组
然后声明了一个变量len作为指针
每当输入一个数字后，将字符数组长度记为len
注：
num为首地址，即&num[0]
则num+len 等价于 &num[len]
然后向num[len]中输入一个字符，
再然后len记为字符长度，
再向num[len]输入一个字符，
len初始值为0，
也就是说，将这个1000位分别存储在num[0]-num[999]中，
举个例子，当len为50时，下一个该输入的为51位。
计算部分
我们的第一种思路为，暴力！
#include <iostream>
#include <string.h>
#include <cstdio>
using namespace std;
int main()
{
char num[1010];
int len=0;
int ans=0;
while(~scanf("%s",num+len))len=strlen(num);
for(int i=1;i<1000;i++){
int a=(num[i]-'0')*(num[i+1]-'0')*(num[i+2]-'0')*(num[i+3]-'0')*(num[i+4]-'0');
if(a>ans)ans=a;
}
printf("%d",ans);
return 0;
}
这显然是可以算的！
但是吧…他的时间复杂度是Olg(n^5)
太慢了
我们需要进行优化…
滑动窗口法
如果你要计算相邻四个数字的乘积，该怎么计算呢？
1 : a[1] * a[2] * a[3] * a[4]
2 : a[2] * a[3] * a[4] * a[5]
3 : a[3] * a[4] * a[5] * a[6]
很显然，我们计算了很多重复的步骤…
1 : a[1] * a[2] * a[3] * a[4]
2 : a[2] * a[3] * a[4] * a[5]
当我使ans从
a[1] * a[2] * a[3] * a[4]
变为
a[2] * a[3] * a[4] * a[5]时
其实不需要计算 a[2] * a[3] * a[4]
只要使ans/a[1]*a[5]就可以
这就是滑动窗口法的基本原理
需要注意的是
前后必须为逆运算，且每个值都不能等于零
当某一个值等于0时，这个式子就没办法按照滑动窗口法计算了。
那么，我们自然形成了对于0的判断思路：
1.当读取到0时，我们直接使窗口跳到0之后的第一位。
2.设置变量Zero来存储窗口中0的个数。只要Zero不等于0，窗口内的答案就无效。
欧拉第八题英文原题：https://projecteuler.net/problem=8
欧拉第八题中英对照：http://pe-cn.github.io/8/
/*************************************************************************
> File Name: ol8.cpp
> Author:ray
> Mail:1430134583@qq.com
> Created Time: Wed 05 Aug 2020 10:42:50 AM CST
************************************************************************/
#include <cstdio>
#include <string.h>
char num[1010];//开一个全局数组，节省空间
using namespace std;
int main()
{
int len = 0;//声明一个整形变量，作为指针
while (~scanf("%s", num + len))len = strlen(num);//向num中循环读入字符
long long ans = 0, p = 1, zero =0;//声明一个长整型变量ans计算结果，声明一个长整型变量p初始化为1，声明一个长整型变量zero初始化为0
//ans存储结果，p存储窗口当前的量，zero存储窗口中0的个数
for (int i = 0; num[i]; i++) {//以num[i]为判断条件。因为num[]为一个字符数组，所以当某一位存储为0时，值是0的ASILL码，只有某一位为空时，才停止循环。
num[i] -= '0';//使这一位由字符变成数字
if (num[i]) p*= num[i];//若num[i]不为0，p=p*num[i]（后一项进入窗口）
else zero += 1;//若为0，Zero++，即窗口中0的个数加一
if (i < 13) continue;//如果i<13 继续下一层循环（此时窗口还没存满数字，不进行出栈）
if (num[i - 13]) p /= num[i - 13];//如果p[i-13]不是0，则p=p/num[1-13]（前一项退出窗口）(加这个判断条件，是因为除数不能为0)
else zero -= 1;//如果num[i-13]=0，令zero=-1，即窗口中0的个数减一
//zero代表的是当前窗口中0的个数
if (zero == 0 && p > ans) ans = p;//如果zero=0（也就是窗口中没有0。此处写成zero<=0也行，不过没啥用，因为0的个数不会为负数）
//且ans<p，更新ans，使其变为p
}
printf("%lld\n",ans);//输出ans
return 0;
}