今日頭條筆試

【問題描述】給定一個段落，由 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 ;
}