0

我遇到了一个关于在二进制序列中识别重复项的相当常见的实践问题（通常称为“硬币翻转”问题），并且似乎很难解释它，所以请耐心等待。我需要交替二进制序列中的最小更改次数，同时返回这可能导致的最大不同输出。

示例：给定一个数组 A = [1, 0, 1, 0, 1, 1]，可以进行最小更改以使序列交替，使其 A = [1, 0, 1, 0, 1, 0]，因此更改 = 1。没有其他方法可以进行 1 更改并保持交替序列。

我的问题是我必须找到可以做出的结果的数量。因此，给定数组 A = [0, 1, 1, 0] 可以产生两个最大结果。[1, 0, 1, 0] 或 [0, 1, 0, 1] 都只需要更改 = 2。这可能只是我无法弄清楚正确的逻辑，请参见下面的代码：

public class Solution {
    public int Solution(int[] S) {
        int changes = 0;
        for (int i = 0; i < S.length - 1; i++) { //using length - 1 so my if statement doesn't go out of bounds
            if (S[i] == S[i + 1]) {//How I'm detecting if a duplication has occured (and why length - 1 is necessary)
                changes++;
            }
            if ((S.length >= 4 && i >= 1) && (S[i - 1] == S[i + 2] && S[i] == S[i + 1])) {//This is where I'm having logic issues. It really only addresses the specific instance listed above
                changes++;
            }
        }
        return changes;
    }
}

当找到最小数量的可能变化时，这很好用，但不是结果。这可能只是一个我无法思考的逻辑问题。我见过其他人问过基本相同的问题，但从未试图找到这个神话般的“最大结果”。如果该解决方案存在于不同的线程中，请将其发送给我。非常感谢！

*似乎我做了一个糟糕的例子来解释我所说的最大结果的意思，我做了一个更好的例子：

使用数组 A = [1, 1, 1, 1, 1, 1] 您应该返回 3，从而导致 [1, 0, 1, 0, 1, 0] 用于更改值 1、3 和 5。这是与以 [0, 1, 0, 1, 0, 1] 结尾的更改数量相同。您需要至少更改 3 个值才能生成交替序列，但只有三个更改可能会产生第二个结果。

4

1 回答 1

0

对于给定数量的硬币，只有两种可能的交替序列：一种以 开头0，另一种以 开头1。
假设一枚硬币只能翻转一次1，则只能进行两组可能的更改。一个导致第一个序列，另一个导致第二个解决方案。两组零钱是互补的，所以两者零钱之和一定是硬币的数量。

示例 3 硬币

可能的顺序：

  • 0, 1, 0
  • 1, 0, 1

从 开始0, 1, 1，我们可以翻转：

  • 第三枚硬币并获得第一个序列
  • 翻转第一个和第二个硬币以获得第二个序列。

第二种解决方案 - 抛硬币1和2- 是第一次抛硬币的补码（逆）3。第一个有1零钱，第二个2是3硬币的数量。

结论：如果你找到最小数量的变化，最大值一定是倒数，即翻转所有其他硬币。零钱数只是硬币数和零钱数之差。

示例 6 硬币

可能的顺序：

  • 0, 1, 0, 1, 0, 1
  • 1, 0, 1, 0, 1, 0

从1, 0, 1, 0, 1, 1（您的示例）开始，我们可以翻转：

  • 硬币号码6：1, 0, 1, 0, 1, 0- 计数1
  • 除了数字之外的所有6：0, 1, 0, 1, 0, 1- 计数5

Sum: 1 + 5 = 6, 硬币数量

1否则我们将有无限数量的可能移动 - 掷硬币两次（四、六、...次）将产生相同的结果

于 2021-05-05T17:13:31.220 回答