算法专题-STL篇

这篇文章着重记录c++中STL的用法。主要粗略的介绍其用法，以知识点的形式呈现其功能，不会深入源码分析其工作原理。

排序和检索.

sort(a,a+n),对a[0]往后的n个元素(包括a[0])进行排序，默认的这种形式由小到大的排序.其属于<algorithm>这个头文件中，它可以给任何对象进行排序，但是需要写自定义函数cmp.完整形式为sort(a,a+n,cmp).

low_bound(a , a+n ,x)-a得到数组a[]从a[0]往后n个长度中，第一个大于或者等于x的下标index.这里的下标，是指数组a[0],a[1],a[2],…,a[n-1]中的下标。

Q1(uva 10474)：

现在有N个大理石每颗石头上写了一个非负整数。首先把各数从小到大排序，然后进行Q次质询，每次质询给出一个负整数，需要你找到这个整数在第几颗石头上(排序后)。

具体代码：

 #include<cstdio>
#include<algorithm>

using namespace std;
const int maxn = 10000;

int main()
{
    int n , q , a[maxn] , kase = 1;
    while(scanf("%d%d",&n , &q) != EOF)
    {
         if(n == 0)  break;
          printf("CASE# %d:
",kase++);
         for(int i = 0;i < n;i++)
              scanf("%d",&a[i]);

         sort(a , a + n);
         while(q--)
         {

            int x;
            scanf("%d",&x);
            int index;
            index = lower_bound(a , a + n , x) - a;
            if(a[index] == x)  printf("%d found at %d
",x , index + 1);
            else               printf("%d not found
",x);
         }
    }
}

集合set：集合是stl中一个容器，它储存字符串的时候。默认按照字典序排列。

stringstream(str):这个对象的用法，是以流的方式，将一个字符串s(形如s1 s2 s3)分别表示成三个子串s1,s2,s3的形式。

Q2：给出一个文本，找出所有不同的单词(连续的字母序列)，按字典序从小到大输出，单词不区分大小写。

分析：这个问题就是为了简单的呈现set和stringstream的用法。首先我们利用特殊的输入技巧，将文本的被空格分隔的连续串拿下来，然后基于stringstream的用法再将某个连续串中非字母的成分变为空格，再把真正的连续字母序列拿到，将其存在容器set里面，由于set容器对字符串默认为由小到大的字典序排列，我们只需要再将容器中的内容顺序输出即可。

参考代码如下：

 #include<cstdio>
#include<iostream>
#include<string>
#include<set>
#include<sstream>
using namespace std;
set<string> dict;

int main()
{
     string s , buf;
     while(cin>>s)
     {
          for(int i = 0;i < s.length();i++)
             if(isalpha(s[i]))  s[i] = tolower(s[i]);
             else               s[i] = ' ';

            stringstream ss(s);
            while(ss >>  buf)  dict.insert(buf);
     }

     for(set<string>::iterator it = dict.begin();it != dict.end();++it)

           cout <<*it<<"
";

     return 0;
}

映射map：

map能够建立两个数组元素之间的一一对应关系，例如我们建立星期几的英文单词和数字1~7的映射关系，就可以定义map<string , int> a, a[“Monday”] = 1.

Q3(uva 156)：

给出一个文本，找到文本中的一类单词，这一类单词满足该文本中其余任何单词，通过重组字母序列，都无法得到这个单词，找到所有这类的单词之后，按照字典序输出。

分析：这个看似和字符串有关的复杂模拟题目，和诸多stl中的用法结合起来，就会显得一场简洁.

考虑如何满足那条性质，假设我们用一个vector<string> s来储存原始的文本，遍历每个单词，我们将得到的单词按照字母大小顺序进行重排，得到新的序列r,将其放入映射中，我们领用map<string , int> cnt记录重排后的序列r出现的次数，遍历完文本单词之后，我们再遍历储存原始文本的向量s，如果当前的单词s[i]，其重排之后的序列r，满足cnt[r] = 1,说明这个字符串是满足要求的字符串，将其放入一个新的字符串向量ans中，枚举完成后，将ans按照字典序排序，然后顺序输出即可。

参考代码如下：

#include<cstdio>
#include<iostream>
//#include<cctype>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
map<string , int> cnt;
vector<string> words;

string repr(const string &s)
{
      string ans = s;
      for(int i = 0;i < ans.length();i++)
          ans[i] = tolower(ans[i]);

      sort(ans.begin() , ans.end());

      return ans;
}

int main()
{
      int n = 0;
      string s;
      while(cin >> s)
      {
            if(s[0] == '#') break;
             words.push_back(s);
             string r = repr(s);

             if(!cnt.count(r))  cnt[r] = 0;
             cnt[r]++;
      }

      vector<string> ans;
      for(int i = 0;i < words.size();i++)
          if(cnt[repr(words[i])] == 1)   ans.push_back(words[i]);
      sort(ans.begin() , ans.end());

      for(int i = 0;i < ans.size();i++)
        cout<<ans[i]<<"
";
}