Блог

Я пытаюсь написать функцию, которая принимает строку и для каждого символа и возвращает расстояние до ближайшей гласной в строке. Если символ сам по себе является гласной, верните 0, но когда я не знаю, что не так с моим кодом, так как первые два элемента в моем s-векторе (который содержит все значения ответа) работают. Остальные просто возвращаются как 0. Что я делаю не так?

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

std::vector<int> distance(std::string word){
    std::vector<char> r = {'a', 'e', 'i', 'o', 'u'};
    std::vector<int> s(word.length());
    for(int i = 0; i < word.length(); i  ){
        if(std::find(r.begin(), r.end(), word[i]) == r.end()){
            for(int c = i   1, d = i - 1; c < word.length() || d > 0; c  , d--){
                if(std::find(r.begin(), r.end(), word[c]) != r.end()){
                    s[i] = c - i;
                    break;
                }
                else if(d >= 0 amp;amp; std::find(r.begin(), r.end(), word[d]) != r.end()){
                    s[i] = i - d;
                    break;
                }
            }
        }else s[i] = 0;
    }
    return s;
}

int main() {
  std::vector<int> h = distance("abbb");
    for(auto c : h){
        std::cout<<c<<"n";
    }
}
 

Мощь алгоритмов и лямбд с сохранением состояния в современном C . . .

Пожалуйста, сначала посмотрите на код, который вычисляет результат в O (2n):

 #include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <string>

// Function to calculate the distance to the nearest vowel
auto distanceToNextVowel(const std::stringamp; s) {

    // Lambda to calculate if a character is a vowel
    auto isVowel = [](char c) { return (0x208222 >> (c amp; 0x1f)) amp; 1; };

    // Here we will store the resulting distance
    std::vector<size_t> dist(s.size());

    // Calculate distance from left and from right and use minimum
    std::transform(s.begin(), s.end(), dist.begin(), [amp;, i = s.size()](const char c) mutable { if (isVowel(c)) i = 0; else   i;  return i; });
    std::transform(s.rbegin(), s.rend(), dist.rbegin(), dist.rbegin(), [amp;, i = s.size()](const char c, const size_t s) mutable { if (isVowel(c)) i = 0; else   i;  return std::min(i, s); });

    // Return result to caller
    return dist;
}

// Test Driver
int main() {
    // This is our test string
    const std::string test{"Hello World"};

    // Caclcuate Result
    const auto dist = distanceToNextVowel(test);

    // Show result on console
    std::copy(test.begin(), test.end(), std::ostream_iterator<char>(std::cout, "t")); std::cout << 'n';
    std::copy(dist.begin(), dist.end(), std::ostream_iterator<size_t>(std::cout, "t")); std::cout << 'n';
    return 0;
}
 

Ууух !? Что это?

Это показывает, какие замечательные проблемы могут быть решены на C . Но это требует много объяснений. Во-первых, как проверить, является ли символ гласным.

Если мы используем код ASCII для кодирования букв, то мы увидим следующее:

Мы видим, что код ASCII для прописных и строчных букв отличается только младшими 5 битами. Итак, если мы замаскируем код ASCII с помощью 0x1F, char c{'a'}; unsigned int x{c amp; 0x1F} то получим значения от 1 до 26. Таким образом, мы можем вычислить 5-битное значение для каждой буквы. Если мы теперь пометим все гласные 1, мы можем построить двоичное число, состоящее из 32 бит (unsigned int ) и установить бит в каждой позиции, где гласная является истинной. Затем мы получаем что-то вроде

 Bit position
3322 2222 2222 1111 1111 1100 0000 0000  
1098 7654 3210 9876 5432 1098 7654 3210  
Position with vowels:
0000 0000 0010 0000 1000 0010 0010 0010
 

Это число может быть преобразовано в 0x208222. И если мы теперь хотим выяснить, является ли буква (независимо от того, является ли она прописной или строчной) гласной, то мы маскируем ненужные биты из символа (C amp; 1F ) и сдвигаем двоичное число вправо на столько позиций, сколько имеет результирующий буквенный код. Если затем бит установлен в позиции LSB, то у нас есть гласная. Этому ноу-хау несколько десятилетий.

Ага. Не так просто, но будет работать для букв в кодировке ASCII.

Кстати, это также сработало бы для других вариантов выбора символов.

результирующая лямбда проста:

 auto isVowel = [](char c) { return (0x208222 >> (c amp; 0x1f)) amp; 1; };
 

Круто . . .

Далее, как вычислить расстояние до / от следующей гласной.

Давайте начнем думать. Если мы пройдемся по строке слева направо, то мы установим результирующую позицию индекса в 0, если мы нашли гласную. Затем мы просто считаем для каждой согласной, пока не достигнем следующей гласной. Это будет работать для подсчета слева направо. Если строка не начинается с гласной, то мы используем какое-то большое число индикатора, например 999, потому что в этом направлении расстояния нет. Пример:

 H   e   l   l   o       W   o   r   l   d
999 0   1   2   0   1   2   0   1   2   3
 

Далее, если мы используем точно такой же алгоритм справа налево, тогда мы получим:

 H   e   l   l   o       W   o   r   l   d
1   0   2   1   0   2   1   0   999 999 999
 

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

 String:         H   e   l   l   o       W   o   r   l   d
Left:           999 0   1   2   0   1   2   0   1   2   3
Right:          1   0   2   1   0   2   1   0   999 999 999
Min of above:   1   0   1   1   0   1   1   0   1   2   3
 

И последняя строка — это результат.

Теперь мы будем использовать лямбда-выражение с полным состоянием для вычисления первой строки:

 std::transform(s.begin(), s.end(), dist.begin(), [amp;, i = s.size()](const char c) mutable { if (isVowel(c)) i = 0; else   i;  return i; });
 

Итак, мы будем перебирать строку. Слева направо. Если мы находим гласную, мы устанавливаем расстояние равным 0. Если мы нашли согласную, мы увеличим расстояние. Значение расстояния — это состояние лямбда-выражения, которое мы инициализируем большим значением, здесь размером строки.

Затем, далее, мы делаем то же самое справа налево. Мы будем использовать вторую форму std::transform , где мы можем работать с 2 исходными контейнерами и создавать новую цель. Итак, мы будем использовать строку и уже (слева направо) вычисленный вектор расстояния и снова сохраним результат в distance-vector, потому что нам не нужен новый. Код очень похож:

     std::transform(s.rbegin(), s.rend(), dist.rbegin(), dist.rbegin(), [amp;, i = s.size()](const char c, const size_t s) mutable { if (isVowel(c)) i = 0; else   i;  return std::min(i, s); });
 

Разница в том, что мы выполняем итерацию справа налево и сохраняем минимальное значение нашего только что вычисленного расстояния и уже ранее вычисленного расстояния.

Вот и все.

В main мы добавляем некоторый код драйвера и генерируем некоторый вывод на консоль.

Надеюсь, я мог бы объяснить алгоритм понятным способом.

В случае возникновения вопросов, пожалуйста, задавайте.