PAT 解题报告 1071. Speech Patterns (25)

1071. Speech Patterns题目描述:

People often have a preference among synonyms of the same word. For example, some may prefer “the police”, while others may prefer “the cops”. Analyzing such patterns can help to narrow down a speaker’s identity, which is useful when validating, for example, whether it’s still the same person behind an online avatar.

Now given a paragraph of text sampled from someone’s speech, can you find the person’s most commonly used word?

Here a “word” is defined as a continuous sequence of alphanumerical characters separated by non-alphanumerical characters or the line beginning/end.

题目就是要求统计出一段话里面出现频率最好的一个单词. 这里的单词是一个连续的字符串而且这个字符串只有字母和数字组成并且不区分大小写.

1071. Speech Patterns算法分析:

使用哈希表统计频率或者构建一颗平衡二叉树统计频率然后输出频率最大的即可. AC代码如下:

#include <cstdio>
#include <cctype>
#include <map>
#include <string>
#include <iostream>

void convert2lower(std::string &line) {
    int len = line.size();
    for(int i = 0; i < len; ++i) line[i] = tolower(line[i]);
}

std::pair<std::string, int> gao(const std::string &line) {
    std::map<std::string, int> freq;
    int p1, p2;
    p1 = p2 = 0;
    int len = line.size();

    for(int i = 0; i <= len; ++i) {
        if(i < len && isalnum(line[i])) {
            ++p2;
        }
        else {
            if(p2 > p1) {
                std::string subs = line.substr(p1, p2 - p1) ;
                convert2lower(subs);
                auto it = freq.find(subs);
                if(freq.end() == it)
                    freq[subs] = 1;
                else
                    freq[subs] += 1;
            }
            p1 = p2 = i + 1;
        }
    }

    int largest = 0;
    std::map<std::string, int>::iterator ptr = freq.begin();

    for(auto it = freq.begin(); it != freq.end(); ++it) {
        if(it->second > largest)  {
            ptr = it;
            largest = it->second;
        }
    }
    return *ptr;
}

int main() {
    std::string line;
    std::getline(std::cin, line);
    std::pair<std::string, int> res = gao(line);
    printf("%s %d\n", res.first.c_str(), res.second);
    return 0;
}

1071. Speech Patterns注意点:

判断word(一个连续的字符串而且这个字符串只有字母和数字组成)注意两个指针的位置关系即可.

Written on November 30, 2013