c++ - 改变 0 以获得 1 的最大序列

Question

我正在尝试解决这个问题，如果 c 更改为 1 将在二进制序列中生成最长的 1 序列，则找到 0 的索引。

有许多不同的方法可以解决这个问题。一种方法是维护零的不同位置的三个变量。但这不是我的算法，我的算法如下。如果它能被优化以完全工作，我会很高兴。

#include <iostream>

using namespace std;

int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int n, temp = 0, count = 0, res = 0;
    bool found = true;

    cin >> n;
    int *a = new int[n];

    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int i = 0; i < n; i++) {
        if (a[i] == 1 || (a[i] == 0 && found == true) && a[i + 1] != 0) {
            count++;
            if (count >= temp) {
                temp = count;
                if (a[i] == 0) {
                    res = i;
                    found = false;
                }
            }
        }
        else {
            count = 0;
            found = true;
        }
    }

    cout << res + 1;

    delete[] a;
    return 0;
}

此输入的算法失败:10

0 0 1 1 1 1 1 0 1 1

它应该输出 8 而不是 2。

Answer 1

解决方案的工作示例:

#include <iostream> // cin, cout
#include <vector> // vector

int main()
{
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    for (auto& x : a)
        std::cin >> x;

    bool is_flipped = false; // Indicates whether we are currently testing a bit or not.
    int index = -1; // Index of the currently tested bit.
    int max_index = -1; // Index of the bit that gave us the longest sequence.
    int length = 0; // Length of the current sequence.
    int max_length = 0; // Length of the longest sequence.

    for (int i = 0; i < n; ++i) {
        if (a[i] == 0) {
            if (is_flipped) {
                is_flipped = false;
                length = -1;
                if (i + 1 < n && a[i + 1] == 1)
                    i = index;
            } else {
                is_flipped = true;
                index = i;
            }
        }
        ++length;
        if (length > max_length) {
            max_index = index;
            max_length = length;
        }
    }

    std::cout << max_index + 1 << '\n';
}

请注意 max_index将是 -1如果算法无法翻转任何位(例如:一个充满 1 的序列)。

---

此外，我想提请您注意一个细节:始终检查是否 i + 1在你的数组范围内 因为你不想访问它之外的东西。像这样:i + 1 < n && a[i + 1] != 0其中 n是数组的大小。除此之外，我建议您使用 vector而不是 C 风格的数组。它是一个具有许多不错特性的动态数组。