今日头条笔试

【问题描述】给定一个段落，由 N 个句子组成。第 i 个句子的长度为 L[i]，包含的单词个数为 W[i]。

句子不包含任何除字母和空格( ) 外的符号。

每个句子内部，含有若干个单词，由空格( ) 分隔。句子不会包含连续的空格。

随后给定 M 个查询，每个查询包含一个句子，需要在段落中寻找相同单词数量最多的句子。重复的单词只计一次，且不区分大小写。

输入数据将保证结果是存在且唯一的。

输入格式

第一行是两个整数 N 和 M。

接下来的 N+M 行，每行包含一个句子。

前 N 行代表段落中的句子，后 M 行表示查询。

输出格式

输出 M 行，每行代表查询的结果。

这题思路感觉挺简单的，就是要设计下数据结构，需要了解下C++里面的一些数据结构，所以第一次还是做不出来。

//
//  main.cpp
//  toutiao
//
//  Created by Cicie Sun on 2017/10/13.
//  Copyright © 2017年 Cicie Sun. All rights reserved.
//

#include <iostream>
#include <vector>
#include<algorithm>
#include <unordered_set>
using namespace std;

int main()
{

    int n,m;
    cin>>n>>m;
    vector<unordered_set<string>> sentence();// 存放句子集合
    vector<string> vec();//存放句子以便最后输出
    string str;
    getline(cin,str); //输出一个句子？
    for (int k=; k<n; k++)//输入N个句子
    {
        getline(cin,str);//这可以输入一个句子
        vec.push_back(str);
        unordered_set<string> tmp;
        tmp.clear();
        string word="";
        for(int i=;i<str.size();i++)//将句子中的每个词插入tmp 中 str[i]是单词，str整个存放的是句子
        {
            if(str[i]==' ')//?
            {
                if(word.size()>)
                {
                    transform(word.begin(), word.end(), word.begin(), ::tolower);//word变为小写
                    tmp.insert(word);
                }
                word="";

            }
            else if(str[i]!=' ')
            {
                word+=str[i];
            }
        }
        if(word.size()>)// 最后一个单词，可能最后一个单词后没有空格
        {
            transform(word.begin(), word.end(), word.begin(), ::tolower);
            tmp.insert(word);
        }
        sentence.push_back(tmp);
    }

    //处理需要匹配的句子
    for (int k=; k<m; k++)
    {
        getline(cin,str);
        unordered_set<string> tmp;
        tmp.clear();
        string word ="";
        for (int i=; i<str.size(); i++)
        {
            if(str[i]==' ')
            {
                if(word.size()>)
                {
                    transform(word.begin(), word.end(), word.begin(), ::tolower);//word变为小写
                    tmp.insert(word);
                }
                word="";
            }
            else if(str[i]!=' ')
            {
                word+=str[i];
            }
        }

        if(word.size()>)// 最后一个单词，可能最后一个单词后没有空格
        {
            transform(word.begin(), word.end(), word.begin(), ::tolower);
            tmp.insert(word);
        }


        word="";
        int index = , mx =;
        // 在待输入的句子里找匹配
        for (int i= ; i<n; i++)
        {
            int count =;
            for (auto it =tmp.begin(); it!= tmp.end(); it++)//对输入的这个句子的单词遍历
            {
                if(sentence[i].find(*it)!=sentence[i].end())// 如果找到这些词
                {
                    ++count;
                }
            }
            if(count>mx)
            {
                mx=count;
                index=i;
            }
        }
        cout<<vec[index]<<endl;
    }
    return ;
}