c++ - 字符串中的最大重复词

Question

我正在尝试做一个非常常见的面试问题“查找字符串中的最大重复词”，但在 net 中找不到太多用于 c/c++ 实现的资源。所以我在这里自己编码。为了更好地理解，我尝试从头开始编写大部分代码。您能否查看我的代码并对我的算法提出意见。有些人建议使用哈希表来存储计数，但我在这里不使用哈希表。

#include<stdafx.h>
#include<stdlib.h>
#include<stdio.h>
#include<string>
#include<iostream>
using namespace std;
string word[10];

//splitting string into words
int parsestr(string str)
{   
    int index = 0;
    int i = 0;
    int maxlength = str.length();
    int wordcnt = 0;
    while(i < maxlength)
    {
        if(str[i]!= ' ')
        {
            word[index] = word[index]+str[i];
        }
        else
        {
            index++;//new word
            wordcnt = index;
        }
    i++;
    }
    return wordcnt;
}

//find the max word count out of the array and return the word corresponding to that index.
string maxrepeatedWord(int wordcntArr[],int count)
{
int max = 0;
int index = 0;
    for(int i=0;i<=count;i++)
    {
        if(wordcntArr[i] > max)
        {
        max = wordcntArr[i];
        index = i;
        }
    }

    return word[index];
}
void countwords(int count)
{
    int wordcnt = 0;
    int wordcntArr[10];
    string maxrepeatedword;
    for(int i=0;i<=count ;i++)
    {
        for(int j=0;j<=count;j++)
        {
            if(word[i]==word[j])
            {
            wordcnt++;
            //word[j] = "";
            }
            else
            {}
        }
        cout<<" word "<< word[i] <<" occurs "<< wordcnt <<" times "<<endl;
        wordcntArr[i] = wordcnt;
        wordcnt = 0;
    }

    maxrepeatedword = maxrepeatedWord(wordcntArr,count);
    cout<< " Max Repeated Word is " << maxrepeatedword;
}

int main()
{
string str = "I am am am good good";
int wordcount = 0;
wordcount = parsestr(str);
countwords(wordcount);
}

Answer 1

只是为了比较，最明显的方法是 C++ 是:

#include <map>
#include <string>
#include <iostream>
#include <sstream>

int main()
{
    std::istringstream input("I am am am good good");
    std::map<std::string, int> count;
    std::string word;
    decltype(count)::const_iterator most_common;
    while (input >> word)
    {
        auto iterator = count.emplace(word, 0).first;
        ++iterator->second;
        if (count.size() == 1 ||
            iterator->second > most_common->second)
            most_common = iterator;
    }
    std::cout << '\"' << most_common->first << "' repeated "
         << most_common->second << " times\n";
}

看它运行here .

注意事项:

• map::emplace 返回 pair<iterator,bool>指示单词及其计数在 map 中的位置, 以及它是否是新插入的。我们只关心在哪里，所以捕获 emplace(...).first .

• 当我们更新计数时，我们会检查这是否使该词成为迄今为止看到的最常见词。如果是这样，我们将迭代器复制到局部变量 most_common , 所以我们记录了迄今为止最常见的单词及其数量。

您正在做的一些值得思考的事情:

• word是一个全局变量 - 将事物作为函数参数传递是一个好习惯，除非它非常不方便，这意味着代码可以更容易地从异步信号处理程序或其他线程中重用，并且在查看函数调用站点时更明显输入是什么输出可能是。按原样，调用 countwords(wordcount)让它看起来像 countwords 的唯一输入是 int wordcount .
• 固定大小的数组:如果你有超过 10 个单词，你就完蛋了。 C++ 标准容器可以按需增长。
• 您可以使用一些方便的函数，例如 std::string::operator+=(char)附加一个 char更简洁alamy_string += my_char;

不过，总的来说，您的代码非常合理，并且显示出对迭代和问题解决的良好理解，所有这些都是在非常底层的情况下完成的，但这是以非常实际的方式理解的好东西。