第七章小结—

第七章小结——查找

查找

首先是定义：

　　查找表：由同一类型的数据元素（或记录）构成的集合。

　　关键字：标识记录数据项的值，唯一标识就是主关键字，否则就是次关键字。

　　动态和静态：查找的同时进行修改，例如插入或删除，就是动态，否则就是静态。

　　平均查找长度：

　　其中pi为查找表中第i个记录的概率，Ci为找到表中其关键字与给定值相等的第i个记录时，和给定值已进行过比较的关键字个数，ASL用于衡量查找算法的性能。

二分查找

时间复杂度：非顺序的是O（nlogn），顺序的是O（logn）。

　　代码：

int binsearch(int a[ ], int key,int n)
{//在数组a中从1到n二分查找key关键字，找到返回元素位置，找不到返回-1
    int l=1,r=n;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(key==a[mid])
            return mid;
        if(key<a[mid])
            r=mid-1;
        else
            l=mid+1;
    }
    //程序跑到这里意味着了l>r，也就是说查找范围不合理即找不到、
    return -1;
}

那么二分的实际应用用于什么呢？

题目链接：https://cn.vjudge.net/contest/283500#problem/A

　　题意：给出n条线段，以米的单位给出，小数点后两位（精确到厘米），要你对这些线段裁剪，裁剪出k条等长的线段，并且让这些线段尽可能长另外线段的长度不能小于1厘米，如果筹不够m条，输出0.00

　　题解：切成k段，设那么每段绳子长度为x，显然x的取值范围为1到最长的那个绳子，显然是要暴力枚举的，那么怎么暴力才省时省力呢，如果要一个人来暴力，那么他先试试x为5，分出了好多好多条，比k大，也就是说x可以大一点，再试试x大于5的，如果x太大了，都分不出k条，那么就让x小一点，这个思路就是对答案进行二分。

AC代码：

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#define eps 1e-8
using namespace std;
double a[10005];
int n,k;
bool ok(double mid)
{
    int count=0;
    for(int i=0; i<n; i++)
    {
        count+=(int)(a[i]/mid);
    }
    if(count>=k) return 1;
    else return 0;
}
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        double sum=0.0;
        for(int i=0; i<n; i++)
        {
            scanf("%lf",&a[i]);
            sum=max(sum,a[i]);
        }
        double l=0,r=sum;
        for(int i=0;i<100;i++)
        {
            double mid=(l+r)/2.0;
            if (ok(mid)) l=mid;//x可以再大点
            else r=mid;//x太大了
        }
        int tmp = r * 100;
        printf("%.2f
",tmp*0.01);
    }
    return 0;
}

View Code

散列表的哈希

　　书上的构造方法有：数字分析法，平方中取法，折叠法和除留余数法。

　　在stl我们可以用map进行哈希映射，在这里我想介绍一下字符串哈希的方法。（转载一下我自己的博客，手动滑稽）

哈希公式：

　　hash[i] = hash[ i - 1 ] *p + id( s[i] )

其中id（x）为x-‘a’+1或者x的ask码，p为质数。例如对abcd哈希：　

可以看到，在求abcd的过程，也顺便把abcd前缀的哈希值求了一遍，那么现在如果要获得abcd子串的哈希值呢，例如要获得bc的哈希值，要从b开始哈希一遍吗？其实是有o（1）的算法的：

来看看 abcd 如果从1开始标号，s[1]=a,s[2]=b,s[3]=c,s[4]=d,为推导方便省略id（），那么：

hash [1]=s[1];

hash [2]=s[1]*p+s[2]

hash [3]=s[1]*p²+s[2]*p+s[3]

hash [4]=s[1]*p³+s[2]*p²+s[3]*p+s[4]

现在要求s₂s₃的哈希值，根据定义就是s[2]*p+s[3],现在观察一下上面四条式子，很容易看出hash[ 3 ]- hash[ 1 ]*p²就等于hash[s2s3]了。

　　可以推广出公式：在字符串s中，第l到r位子串的哈希值为：hash[r]-hash[l-1]*p^r-l+1,所以，只要我们得到了一个字符串的哈希值，就可以在o(1)的时间内得到它的子串的哈希值。　

例题　

华工赛字符串题：https://ac.nowcoder.com/acm/contest/625/K

意思是给定一个字符串，有q次查询，每次查询给字符串设个断点，计算断点前的字符串的子串在断点后的字符串出现的次数和。

例如ababa，对于查询给出的2，将它分成了ab aba两段，前面的子串有a,b,ab, 在后面分别出现了2,1,1次，所以答案是4。字符串长度是1000，而查询有1e5那么多，肯定要预处理ans数组的。总体思路为：

ac代码：

 1 #include<bits/stdc++.h>
 2 #include<tr1/unordered_map>
 3 using namespace std::tr1;
 4 #define ll long long
 5 #define maxn 1234
 6 ll t,seed=131,ans[maxn];
 7 ll f[maxn],g[maxn],sum,x;//f【i】为前i个字母组成的前缀哈希成的数字
 8 unordered_map<ll,int>pre,now;
 9 char s[maxn];
10 ll geth(int l,int r)
11 {
12     return f[r]-f[l-1]*g[r-l+1];
13 }
14 int main()
15 {
16     scanf("%s%lld",s+1,&t);//输入字符串,从一开始
17     int n=strlen(s+1);//长度为n
18     g[0]=1;//.......................
19     for(int i=1; i<=n; i++)
20     {//................
21         g[i]=g[i-1]*seed;//g用于求子串的哈希值
22         f[i]=f[i-1]*seed+s[i];//将每个前缀哈希成一个数字（fi是ll）
23     }
24     for(int i=1; i<=n; i++)
25         for(int j=i; j<=n; j++)
26             pre[geth(i,j)]++;//i到j为一条子串，并将该子串哈希，放到pre里面，个数++
27     for(int i=1; i<=n; i++)
28     {//从一开始设置断点
29         for(int j=i; j>=1; j--)
30         {
31             ll id=geth(j,i);//获得前件后缀的哈希值
32             now[id]++;//当前后缀的个数++
33             if(pre[id])//若后件有该子串，sum+上该子串的个数
34                 sum+=pre[id];
35         };
36         for(int j=i; j<=n; j++)
37         {
38             ll id=geth(i,j);//获取后件子串的哈希值
39             pre[id]--;//子串个数--
40             if(now[id])
41                 sum-=now[id];
42         }
43         ans[i]=sum;//对此时的断点预处理完成   大重点，sum没有初始化，是继续用的
44     }
45     while(t--)
46     {
47         scanf("%lld",&x);
48         printf("%lld
",ans[x]);
49     }
50     return 0;
51 }

View Code

实践题题解：用stl的map

AC代码：

#include <iostream>
#include <map>
using namespace std;
map<string,string> a;
string qq,mima;
char str[2];


int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
       
        cin>>str>>qq>>mima;
        if(str[0]=='L'){
            if(a[qq].length()==0)
            {
                cout<<"ERROR: Not Exist
";
                continue;
            }
            if(a[qq]==mima) cout<<"Login: OK
";
            else cout<<"ERROR: Wrong PW
";
        }
        else{
            if(a[qq].length()==0)
            {
                a[qq]=mima;
                cout<<"New: OK
";
            }
            else cout<<"ERROR: Exist
";
        }
    }
    return 0;
}

View Code