Макс повторил слово в строке


Я пытаюсь сделать очень распространенная проблема интервью "найти максимальное слово в строке" и не мог найти много ресурсов в сети на 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);
}


5177
4
задан 23 марта 2011 в 12:03 Источник Поделиться
Комментарии
2 ответа

Вот длинный список пожеланий. Извините за тупой тон, но я пытаюсь быть краток:


  1. parsestr изменяет глобальную переменную, но возвращает значение, соответствующее
    эту переменную (счетчик). Это непоследовательно. Либо возвращать как
    граф и массива (или сделать вещи легче на себя и использовать
    вектор , который знает свой размер), или принять считать глобальной тоже.

  2. Ты не справился со знаками препинания. Разве это требование? Следует
    "а(б)" быть одно слово? Должны "есть. а" два уникальных слов?

  3. Вам нужно разделить на символы, чем космос? Насчет или
    \п? Другие пробельные символы Юникода?

  4. Ваше время(я < свойство maxlength) петли могут более просто для петли.

  5. Выстраивая слово, постепенно contatenating символов на
    строки медленно. Он будет периодически требуют динамического выделения. Более
    эффективным решением будет запомнить индекс начала слова. Когда
    Вы дойдете до конца, создать строку из подстроки (начало, конец) в одном
    шаг.

    Идем дальше оттуда, нет никаких причин, чтобы даже сохранить эти слова
    отдельно с этого начала, окончания пары достаточно, чтобы реконструировать его по мере необходимости.


  6. Ваша программа будет таинственно сбой, если вы проходите предложение с более
    десять слов. :( Поскольку вы используете динамическое выделение везде (строка
    это под капотом) нет никаких причин, чтобы использовать фиксированный массив слов.
    По крайней мере, вы должны иметь постоянное для такого размера и убедитесь, что
    вы не переполнение массива.

  7. индекс не является полезным имени переменной. Назвать это wordIndex.

  8. Кроме того, wordcnt бы лучше, как приложения WordCount.

  9. maxrepeatedWord представляет собой смесь из верблюжьего и все строчные. Будьте последовательны
    (и верблюжьего вообще лучше, так как это делает его легче для читателя
    разбить его на слова).

  10. wordcntArr бы лучше, как wordCounts. Тот факт, что это массив
    самоочевидным.

  11. я <= графа должна быть просто <. Индексация массивов начинается с нуля, поэтому
    wordcntArr[граф] прошли последние допустимый элемент.

  12. индекс -> indexOfMax.

  13. Вы отдаете рассчитывать на countwords хотя бы тем, что граф имеет отношение
    на глобальную переменную, которая обращается напрямую. Почему бы просто не сделать графу
    глобальные тоже?

  14. В остальное {} ничего не совершает. Удалить его.

  15. Если вы объявляете wordcnt внутри для(int я... петли, вам не придется
    инициализируйте его в каждой итерации.

  16. инт wordcntArr[10] снова повторяет магические буквальное 10. Использовать
    постоянное или, лучше, динамически размера контейнера.

  17. Ты избыточно вспоминая каждое слово каждый раз, когда это происходит. С
    "Я есмь хорошо", вы получите графа массив 1 3 3 3 2 2.
    Если у тебя есть коллекция уникальных слов вместо О(N^2)сложность
    бы спуститься к О(М*Н) , где м - количество уникальных слов.

    Хеш-таблица будет хороший способ, чтобы создать набор уникальных слов.


  18. Ваша тестовая строка предполагает повторяющиеся слова будут непрерывными (в отличие,
    сказать "Я хороший, я хороший я."). Это намеренно? Желательно?

На высоком уровне, ваш алгоритм не оптимальный. У вас есть о(п^2) производительность, игнорируя динамическое выделение, как вы постепенно наращивать эти строки. С этим, становится хуже.

Я считаю, что стандартное решение это (грубо):

create a map of words -> counts
set wordStart to 0
iterate through the string
if the current character is a word delimiter
set word to the substring from wordStart to here
set wordStart to here
if map contains word
increment the count for that word
else
add the word to the map with a count of 1
end
end
end

set maxWord to null
set max to 0
iterate through the map
if count for this word > max
set maxWord to this word
set max to count
end
end

return maxWord

Что дает вам o(п): вы только ходить всю строку сразу.

5
ответ дан 23 марта 2011 в 06:03 Источник Поделиться

Некоторые общие замечания первое:

1) комментировать, комментировать, комментировать. Хотя сейчас это кажется довольно ясно, что это не больно, чтобы сделать это очень ясно для тех, кому приходится поддерживать ее, когда ты ушел.

2) Вы, возможно, захотите, чтобы иметь отдельные функции для подсчета слов и для отображения графов слова.

Комментарии На Языке C++

3) Вы используете C++, так что вы можете положить это в классе.

4) стандартная библиотека-твой друг. В частности, вы, возможно, захотите, чтобы увидеть, если СТД::карта<...> может сделать вашу жизнь немного легче при подсчете слов.

5) Использование "строку слово[10]" делает предположение о том, как много разных слов будут. Было бы лучше, чтобы позволить произвольным числом различных слов, используя что-то вроде СТД::вектор. Кроме того, разный подход может быть использован (см. #4).

6) строку.найти(..) и строки.подстрока(..) может оказаться полезным.

1
ответ дан 23 марта 2011 в 05:03 Источник Поделиться