Поиск пар не-гласных в C ++

Question

У меня есть проблема в программировании, где я должен создать программу, которая будет вычислять количество пар букв (букв рядом друг с другом), которые не являются «a», «e», «i», «o»,'u' (гласные).

Примеры:

• jas 0
• olovo 0
• skok 1 (sk)
• стандартность 4 (st, tv, rn, st)

Ввод состоит из маленьких буквкоторые составляют слово не длиннее 200 символов, и на выходе должно быть выведено количество пар букв, которые не являются гласными (a, e, i, o, u).

ограничение по времени :

• 1 сек

Ограничение памяти :

• 64 МБ

Примеры, приведенные в задаче, которую мне дали:

• Вход skok
• Выход 1

Однако, когда я ввожу слова «скок», программа не работает (кажется, что она продолжает работать в фоновом режиме, но не отображает ничегона экране).Однако слово «stvarnost» (реальность) работает, отображая «4» - как указано в задаче.

Из 10 тестовых наборов два тестовых набора дают мне правильный вывод, один - неверный вывод, а семь других тестовых наборов говорят мне, что я превысил свой срок.

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

Вот код, который я начал:

#include <iostream>
#include <string.h>

using namespace std;

int main() {

    char zbor[200];
    cin.get(zbor, 200);
    int length = strlen(zbor);
    int j_value = 0;
    int check_pairs = 0;
    int pairs = 0;
    int non_vowels = 0;

    for (int i = 0; i < length; i++) {
        if (zbor[i] == 'a' || zbor[i] == 'e' || zbor[i] == 'i' || zbor[i] == 'o' || zbor[i] == 'u') {
            continue;
        } else {
            non_vowels++;
            for (int j = i + 1; j < length; j++) {
                if (zbor[j] == 'a' || zbor[j] == 'e' || zbor[j] == 'i' || zbor[j] == 'o' || zbor[j] == 'u') {
                    break;
                } else {
                    non_vowels++;
                    if (non_vowels % 2 != 0) {
                        check_pairs = non_vowels / 2 + 1;
                    } else {
                        check_pairs = non_vowels / 2;
                    }
                    if (pairs < check_pairs) {
                        pairs++;
                    }
                    j_value = j;
                }
            }
            i = j_value +  1;
        }
    }

    cout << pairs;

    return 0;
}

Редактировать:

#include <iostream>
#include <string.h>

using namespace std;

int main() {

    char zbor[200];
    cin.get(zbor, 200);
    int length = strlen(zbor);
    int pairs = 0;
    int non_vowels = 0;

    for (int i = 0; i < length; i++) {
        if (zbor[i] == 'a' || zbor[i] == 'e' || zbor[i] == 'i' || zbor[i] == 'o' || zbor[i] == 'u') {
            non_vowels = 0;
            continue;
        } else {
            non_vowels++;
            if (non_vowels >= 2) {
                if (non_vowels % 2 != 0) {
                    pairs = non_vowels / 2 + 1;
                } else if (non_vowels % 2 == 0) {
                    pairs = non_vowels / 2;
                }
            }
        }
    }

    cout << pairs;

    return 0;
}

Редактировать код, используя фрагменты кода ответов ниже, ( bruno 's и Ozzy ' s) вот окончательная версия, которая работает:

#include <iostream>
#include <string.h>

using namespace std;

bool vowel(char c) {
    switch(c) {
    case 'a':
    case 'e':
    case 'i':
    case 'o':
    case 'u':
        return true;
    default:
        return false;
    }
}

int main()
{

    char zbor[200];
    cin.get(zbor, 200);
    int N = strlen(zbor);
    int non_vowels = 0;
    int pairs = 0;

    for (int i = 0; i < N; i++) {
        if (!vowel(zbor[i])) {
            non_vowels = 0;
        } else {
            non_vowels++;
            if (!vowel(zbor[i])) {
                non_vowels = 0;
            } else {
                non_vowels++;
                if (non_vowels > 1) {
                    pairs++;
                }
            }
        }
    }

    cout << pairs;

    return 0;
}

Answer 1

Вот решение, использующее std ::acent_find :

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

bool isConsonant(char c)
{
    static const char *vowels = "aeiou";
    return strchr(vowels, c)?false:true;
}

int main()
{
    std::string s = "stvarnost";
    auto it = s.begin();
    int count = 0;
    while (true)
    {
        // find the adjacent consonants
        auto it2 = std::adjacent_find(it, s.end(), 
                                     [&](char a, char b) 
                                     { return isConsonant(a) && isConsonant(b); });
        if ( it2 != s.end())
        {
            // found adjacent consonents, so increment count and restart at the next character.
            ++count;
            it = std::next(it2);
        }
        else
            break;
    }
    std::cout << count << "\n";
}

Вывод:

4

Живой пример

Answer 2

Вот решение на C ++ 17, которое использует string_view и соседний_финд. Это идиоматический C ++, что делает его довольно коротким и простым для понимания.

#include <algorithm>
#include <iostream>
#include <string_view>
using namespace std;

bool checkPair(char a, char b)
{
    string_view vowels { "aeiou" };
    bool aNotVowel = vowels.find(a) == string_view::npos;
    bool bNotVowel = vowels.find(b) == string_view::npos;
    return aNotVowel && bNotVowel;
}

int main(int argc, char **argv)
{
    int pairs { 0 };
    string_view input(argv[1]);

    for(auto next = input.begin(); next != input.end();)
    {
        next = adjacent_find(next, input.end(), checkPair);
        if(next != input.end())
        {
            ++pairs;
            ++next;
        }
    }
    cout << pairs << endl;

    return 0;
}

Answer 3

Вы можете легко упростить свой код, используя функции C ++, предложение:

#include <algorithm>
#include <iostream>
#include <array>
#include <vector>

const std::array<char, 5> vowels = {'a', 'e', 'i', 'o', 'u'};

bool isVowel(char c)
{
    return std::find(vowels.begin(), vowels.end(), c) != vowels.end();
}

bool checker(char c)
{
    static bool lastFound = false;

    if (lastFound && !isVowel(c))
        return true;
    else
        lastFound = !isVowel(c);

    return false;   
}

int main()
{
    std::vector<char> v{'s', 'k', 'o', 'k', 'a', 'k'};

    int num_items = std::count_if(v.begin(), v.end(), &checker);

    std::cout << num_items << std::endl;
}

Answer 4

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

#include <iostream>
#include <string.h>

using namespace std;

bool IsVowel(char ch)
{
    switch (ch)
    {
    case 'a':
    case 'e':
    case 'i':
    case 'o':
    case 'u':
    case 'A':
    case 'E':
    case 'I':
    case 'O':
    case 'U':
        return true;
        //break;
    default:
        return false;
    }

    return false;
}

int CountNonVowelPair(char* chIn)
{
        char zbor[200];
        //cin.get(zbor, 200);
        strcpy(zbor, chIn);
        int length = strlen(zbor);
        int j_value = 0;
        int check_pairs = 0;
        int pairs = 0;
        int non_vowels = 0;

        if (length <= 1)
            return 0;

        for (int i = 1; i < length; i++)
        {
            if (IsVowel(zbor[i - 1]) || IsVowel(zbor[i]))
                continue;
            else
                pairs++;
        }

        return pairs;
}

int main() 
{
    int nRet;
    nRet = CountNonVowelPair("jas");
    cout << nRet <<endl;
    nRet = CountNonVowelPair("olovo");
    cout << nRet <<endl;
    nRet = CountNonVowelPair("skok");
    cout << nRet <<endl;
    nRet = CountNonVowelPair("stvarnost");
    cout << nRet <<endl;

    return 0;
}

Answer 5

1. Оптимизация времени: при разборе строк (char *), проходите через «while» вместо получения длины и «for».Вы получаете только 1 проход вместо 2 (1 проход уже принят strlen).
2. Оптимизация кода: если у вас есть код, который повторяется, поместите его в функцию или макрос.
3. Используя две приведенные выше точки, вот пример кода (вы можете управлять вводом):

Образец

#include <iostream>
#include <cstddef>

using namespace std;

#define IS_VOWEL(a) ((a == 'a') || (a == 'i') || (a == 'u') || (a == 'e') || (a == 'o') || (a == 'y'))

int find_pairs(char * input, char ** stop_pos)
{
    char * input_cursor = input;

    while ((*input_cursor != 0) && IS_VOWEL(*input_cursor))
    {
        input_cursor++;
    }
    size_t used_count = 0;
    while ((*input_cursor != 0) && !IS_VOWEL(*input_cursor))
    {
        used_count++;
        input_cursor++;
    }
    *stop_pos = input_cursor;
    if (used_count < 2)
    {
        return 0;
    }
    else
    {
        return used_count - 1;
    }
}

int main()
{
    char input[] = "stvarnost";
    char * input_cursor = input;
    int found = 0;
    while (*input_cursor != 0)
    {
        found += find_pairs(input_cursor, &input_cursor);
    }
    cout << found << endl;
    return 0;
}

Получайте удовольствие:)

Answer 6

Действительно, есть несколько вещей ..

1. доступ к zbor [i] может занять очень много времени, потому что он всегда ищет позицию i снова для каждого сравнения (если только компилятороптимизирует некоторые вещи)

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

3. Использование функций C ++, таких как лямбда-выражения, для облегчения чтения вашего кода

.

auto isVowel = [](char& c) {return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';};

for (int i = 0; i < length; i++)
{
  if (isVowel(zbor[i]))
  {
    non_vowels = 0;
  }
  else
  {
    non_vowels++;

    if (non_vowels > 1)
      pairs++;
  }
}

cout << pairs;

Answer 7

Предложение:

#include <iostream>

using namespace std;

bool vowel(char c)
{
    switch (c) {
    case 'a':
    case 'e':
    case 'i':
    case 'o':
    case 'u':
    case 'y':
        return true;
    default:
        return false;
    }
}

int main()
{
    string zbor;

    if (! (cin >> zbor))
        return -1;

    int pairs = 0;

    for (size_t i = 0; i < zbor.length(); ++i) {
        if (!vowel(zbor[i])) {
          int n = 0;

          do
            n += 1;
          while ((++i != zbor.length()) && !vowel(zbor[i]));

          pairs += n - 1;
        }
    }

    cout << pairs << endl;

    return 0;
}

Компиляция и исполнение:

/tmp % g++ -pedantic -Wextra p.cc
/tmp % ./a.out
jas
0
/tmp % ./a.out
olovo
0
/tmp % ./a.out
skok
1
/tmp % ./a.out
stvarnost
4