c++ - 解决到最近元音程序的距离问题

Question

我正在尝试编写一个函数，它接受一个字符串和每个字符，并返回到字符串中最近的元音的距离。如果字符本身是元音，则返回 0，但是当我不知道我的代码有什么问题时，因为我的 s vector (包含答案的所有值)中的前两个元素正在工作。其余的只是返回 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 && 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";
    }
}

Answer 1

现代 C++ 中算法和有状态 Lambda 的强大功能。 . .

请先看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::string& s) {

    // Lambda to calculate if a character is a vowel
    auto isVowel = [](char c) { return (0x208222 >> (c & 0x1f)) & 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(), [&, 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(), [&, 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 位不同。所以，如果我们用 0x1F 屏蔽 ASCII 码，那么 char c{'a'}; unsigned int x{c & 0x1F}，我们将得到 1 到 26 之间的值。因此，我们可以为每个字母计算一个 5 位的值。如果我们现在用 1 标记所有元音，我们可以构建一个由 32 位(无符号整数)组成的二进制数，并在元音为真的每个位置设置一个位。然后我们得到类似的东西

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 & 1F )中屏蔽掉不需要的位，并将二进制数向右移动尽可能多位置，作为生成的字母代码。如果该位设置在 LSB 位置，则我们有一个元音。这知道如何已有数十年历史。

啊哈。不太容易，但适用于 ASCII 编码的字母。

顺便说一下，它也适用于其他字符选择。

生成的 Lambda 很简单:

auto isVowel = [](char c) { return (0x208222 >> (c & 0x1f)) & 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

最后一行是结果。

现在，我们将使用有状态的 Lambda 来计算第一行:

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

因此，我们将遍历整个字符串。从左到右。如果我们找到一个元音，我们将距离设置为 0。如果我们找到一个辅音，我们将增加距离。距离值是 Lambda 的一个状态，我们用一个很大的值初始化它，这里是字符串的大小。

然后，接下来，我们从右到左做同样的事情。我们将使用 std::transform 的第二种形式，我们可以在其中使用 2 个源容器并创建一个新目标。因此，我们将使用字符串和已经(从左到右)计算出的距离 vector 并将结果再次存储在距离 vector 中，因为我们不需要新的。代码非常相似:

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

不同之处在于我们从右到左迭代并存储我们刚刚计算的距离和之前已经计算的距离的最小值。

就是这样。

在 main 中，我们添加一些驱动程序代码并在控制台上生成一些输出。

我希望我能以一种易于理解的方式解释该算法。

如有疑问，请提出。