第二十八章：解题技巧

 哨兵

设置“哨兵”，哨兵就是待查值，将它放在查找方向的“尽头”处，免去了在查找过程中每一次比较后都要判断查找位置是否越界，从而提高查找速度。

例1（提高效率）

假设一个乱序数组，需要查找一个元素是否在该数组中，这时需要用到顺序查找，也就是遍历数组。

一般情况下我们会写下如下代码：

//函数返回在a数组中查找到元素key的下标，若没有找到返回0
int Search(int a[],int n,int key)
{
    //假设我们的数组都是从1下标开始存的
    int i;
    for(int i=1;i<=n;i++)
    {
        if(a[i]==key)
            return i;//找到了，返回下标
    }
    return 0;//查找失败
}

Copy

在《大话数据结构》书中运用哨兵元素，改成这样的代码：

//函数返回在a数组中查找到元素key的下标，若没有找到返回0
int Search2(int a[], int n, int key)
{
    //同样的，假设我们的数组都是从1下标开始存的
    int i=0;
    a[0]=key;//哨兵
    i=n;
    while(a[i]!=key)
    {
        i--;
    }
    return i;//返回0就是查找失败

Copy

仔细看来没有什么太大差别，当数组有10亿个元素，我们来看一下4次测试的时间。

Search函数	3.494s	3.202s	3.216s	3.237s
Search2函数	2.332s	2.307s	2.24s	2.194s

为什么基本一样的代码，方案2比方案1性能提升了30%~40%左右？？？

在循环中， Search函数有3条指令： i<=n 、a[i]==key 和i++；而 Search2函数只有两条指令： a[i]!=key和i--，少了i<=n 这个比较操作，所以Search2函数 性能得到了提升 ，这也是哨兵元素的妙用。

例2（解题思路）

统计单词数 我们可以对两个比对的字符串添加哨兵，统一处理查找问题。

string s;
cin >> s;
s = ' ' + s;//此处的空格就是一个哨兵

Copy

参考代码如下：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string a,b; 
    getline(cin,a);
    getline(cin,b);
    a=' '+a+' ';//a字符串添加两个哨兵
    b=' '+b+' ';//b字符串添加两个哨兵
    for(int i=0;i<a.size();i++)
    {
        if(a[i]>='A'&&a[i]<='Z') a[i]=a[i]+32;
    }
    for(int i=0;i<b.size();i++)
    {
        if(b[i]>='A'&&b[i]<='Z') b[i]=b[i]+32;
    }
    int idx=b.find(a),s=0;
    while(idx!=string::npos)
    {
        if(idx!=string::npos)
            s++;
        idx=b.find(a,idx+a.size()-1);
    }   
    if(s==0) cout<<"-1";
    else cout<<s<<" "<<b.find(a);
}

Copy

打表

对于数据小又容易超时的题，可以采取打表法。用数组来存储我们可能会用到的数据，通过下标来访问，这种方式我们称为 打表 。

优缺点

1. 快速，易行（可以写暴力枚举程序）。

2. 缺点是代码可能太大，或者情况覆盖不完。

对于不会超时，数据规模适合打表，为了简洁你也可以打表。通过两个例题我们来看一下。

例题1：火柴棒等式

这道题n<=20完全可以通过 打表生成答案 ：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
    int a[10]={6,2,5,5,4,5,6,3,7,6};
    int i,j,temp=0,num=0,k,in[2020],n;
    in[0]=6;
    for(i=1;i<=2000;i++){
        k=i;
        temp=0;
        while(k){
            temp+=a[k%10];
            k/=10;
        }
        in[i]=temp;
    }
    for(n=0; n <= 24; n++)
    {
        num=0;
        for(i=0;i<=999;i++){
            for(j=0;j<=999;j++){
                if(n==in[i]+in[j]+in[i+j]+4) num++;
            }
        }
        printf("%d,",num);
    }
    return 0;
}

Copy

通过上面的程序，我们生成了答案，然后提交下面的代码：

#include<iostream>
using namespace std;
int ans[]={0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,8,9,6,9,29,39,38,65,88,128};
int n;
int main(){
    cin>>n;
    cout<<ans[n]<<'\n';
    return 0;
}

Copy

是不是很简洁。

例题2：日期

思路

计算这两个日期距离1月1日的天数，然后求两个天数的绝对值即可。

方法1

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int k, d1, d2; 
    cin >> k;
    for(int i = 0; i < k; i++)
    {
        cin >> d1 >> d2;
        int t1 = 0, t2 = 0;//t1和t2计算出到1月1号的天数，想一想为什么这里在循环中声明？ 
        for(int j = 1; j < d1/100; j++)
        {
            if(j == 2 || j == 4 || j == 6 || j == 9 || j == 11)
            {
                t1 += 30;
                if(j == 2)
                {
                    t1 -= 1;//题目中只计算闰年，闰年的2月份是29天，所以减去1即可
                }
            }
            else
            {
                t1 += 31;
            }
        }
        for(int j = 1; j < d2/100; j++)
        {
            if(j == 2 || j == 4 || j == 6 || j == 9 || j == 11)
            {
                t2 += 30;
                if(j == 2)
                {
                    t2 -= 1;//题目中只计算闰年，闰年的2月份是29天，所以减去1即可
                }
            }
            else
            {
                t2 += 31;
            }
        }
        t1 += d1 % 100;
        t2 += d2 % 100;
        if(abs(t1-t2) > 100) cout << "YES\n";
        else cout << "NO\n";
    }
}

Copy

方法2

我们也可以用一个一维数组，直接存储12个月每个月的天数，这样就减少了很多分支结构，看起来更简洁，效率上也更快。

int day[13] = {0,31,29,31,30,31,30,31,31,30,31,30,31};

Copy

方法2拓展

当然我们也可以用一个数组存储从11月到 ii 月总共需要多少天。

例如：

int day2[13] = {0,31,60,91,121,152,182,213,244,274,305,335,366};

Copy

day2[i]表示11月到 ii 月总共过去了多少天，注意：这里是不计算 ii 月的。

如果我们不用day2数组，那么我们需要一个for循环来计算从11月到 ii 月需要的天数。通过day2数组，我们可以直接通过下标来访问，优化掉一个for循环，当然这里的循环最多就12次，那如果一道题目是1万次，10万次，外面还有一两个循环嵌套的呢？那我们通过打表，就能把速度大大提升！！！这种优化，在很多程序优化中都有着至关重要的作用。

例题参考代码如下：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int day[13] = {0,31,60,91,121,152,182,213,244,274,305,335,366};
    int k, d1, d2, t1, t2;//t1和t2计算出到1月1号的天数 
    cin >> k;
    for(int i = 0; i < k; i++)
    {
        cin >> d1 >> d2;
        t1=day[d1/100-1]+d1%100;
        t2=day[d2/100-1]+d2%100;
        if(abs(t1-t2) > 100) cout << "YES\n";
        else cout << "NO\n";
    }
}

Copy