算法：基于相同序列的数字替换

Question

我似乎无法处理我的学习作业。 我陷入了指针搜索方法。但是，我正在考虑在哪里更改这些数字。如果且为的话我最终会得到一百万。

我有一个数字数组，比如说

int[] numbers = { 0, 0, 1, 1, 1, 0, 0, 1 };

我需要让它变得美丽。美丽的地方在于，一行中的某个数字（可能是零）第一个是 0，其他都是 1。

例如： 001111很漂亮，但00001011不漂亮。

我可以将每个数字替换为相反的数字。需要输出replaces的最小值，才能让数组美观。

例如。0110

输出：1

例如。11

输出：0

注意 在第一个示例中，我们可以替换最后一位数字，那么目标将看起来像0111。在第二个示例中，原始目标已经很漂亮了。

我应该朝什么方向思考？ 现在我只能找到由 0 组成的左侧范围。并且在右侧范围中 0 被 1 替换。

static void FindZeroSegment(int[] numbers, out int start, out int end)
{
    start = -1;
    end = -1;

    for (int i = 0; i < numbers.Length; i++)
    {
        if (numbers[i] == 0)
        {
            if (start == -1)
            {
                start = i;
            }
            end = i;
        }
        else
        {
            if (start != -1)
            {
                break;
            }
        }
    }
}

static int CountOnesInRightSegment(int[] numbers, int startIndex)
{
    int count = 0;

    for (int i = startIndex + 1; i < numbers.Length; i++)
    {
        if (numbers[i] == 1)
        {
            count++;
        }
        else
            numbers[i] = 1;
    }

    return count;
}
static void Main(string[] args)
{
    int[] numbers = { 0, 0, 0, 1, 0, 0 };
// Output 0, 0, 0, 1, 1, 1

    int start;
    int end;
    FindZeroSegment(numbers, out start, out end);
    
    int rightSegment = CountOnesInRightSegment(numbers, end);

    foreach (var item in numbers)
    {
        Console.Write(item);
    }

}

Answer 1

这是假设当您指的是“替换”时，您可以交换任意两个字符，而不仅仅是相邻的字符。

简单来说，逻辑是：

最左边的“1”右边有多少个“0”？

一个简单的单遍 Linq 语句就可以回答这个问题。

var input = "0110";

var answer = input
    .SkipWhile(x => x is '0') // from the left of the string, skip until you hit the first '1'
    .Where(x => x is '0')     // from that point on, collect all the '0's
    .Count();                 // how many '0's did you collect?

Console.WriteLine(answer); // prints 1