我似乎无法完成我的学习任务. 我被指针搜索方法困住了.但是,我在考虑在哪里更改这些数字.我最终会得到一百万美元.

我有一个数字数组,假设是int[] numbers = { 0, 0, 1, 1, 1, 0, 0, 1 };

我要把它弄得漂亮些.美丽的是一行中的某个数字(可能是零)是第一个0.其余的都是1.

For example: 001111是美丽的,但00001011不是.

我可以把每个数字都换成相反的数字.为了使数组美观,有必要输出最小的置换值.

Ex. 0110

输出:1

Ex. 11.

发帖主题:Re:Kolibri

Note个 在第一个例子中,我们可以替换最后一个数字,然后目标将看起来像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);
    }

}

推荐答案

让我们从degenerated case开始:all zeroes数组很漂亮,它需要

// Let me use Linq, but you can sum in a loop if you want
int current = numbers.Sum();
int result = current;

操作,使最初的numbers数组成为漂亮的全零(我们应该把每个1变成0). 现在,让我们判断一下生成数组需要进行多少次操作

  • 除最后一项外全部为零
  • 除最后两项外全部为零 ...
  • 所有人:
for (int i = numbers.Length - 1; i >= 0; --i) {
  if (number[i] == 1)
    current -= 1;
  else
    current += 1;

  result = Math.Min(result, current);
}

把所有这些片段放在一起:

private static int Solve(int[] numbers) {
  int current = numbers.Sum();
  int result = current;

  for (int i = numbers.Length - 1; i >= 0; --i) {
    if (numbers[i] == 1)
      current -= 1;
    else
      current += 1;

    result = Math.Min(result, current);
  }

  return result;
}

演示:

int[][] tests = new int[][] {
  new int[] { 0, 0, 1, 1, 1, 0, 0, 1 },
  new int[] { 0, 1, 1, 0 },
  new int[] { 1, 1 },
  new int[] { 0, 0, 1, 1, 0, 0, 0, 1 } 
};
      
string report = string.Join(Environment.NewLine, tests
  .Select(test => $"[{string.Join(", ", test)}] : {Solve(test)}"));  
      
Console.WriteLine(report);

输出:

[0, 0, 1, 1, 1, 0, 0, 1] : 2
[0, 1, 1, 0] : 1
[1, 1] : 0
[0, 0, 1, 1, 0, 0, 0, 1] : 2 

Fiddle

时间复杂度:O(n)

空间复杂性:O(1)

Csharp相关问答推荐

如果第一个匹配项为空,则规则运算不会拆分C#中分离字符串上的子菜单

是否可以将gltf转换为字节数组,然后将字节数组转换回文件?

在ASP.NET中为数据注释 Select 合适的语言

如何在C#中删除一个特殊字符,如"使用Regex"

为什么我的ASP.NET核心MVC应用程序要为HTML元素添加一些标识符?

Microsoft. VisualBasic. FileIO. FileSystem. MoveFile()对话框有错误?

JsonSerializer.Deserialize<;TValue>;(String,JsonSerializerOptions)何时返回空?

在路由中使用枚举

ASP.NET配置kestrel以使用Windows证书存储中的HTTPS

如何使用EF Core和.NET 8来upsert到具有多对多关系的表?

取决于您的数据量的多个嵌套循环

VS 2022 for ASP.NET Core中缺少自定义项模板

避免只读记录 struct 中的防御副本

按需无缝转码单个HLS数据段

毛伊岛.NET 8图片不再适合按钮

如何设置WinForms按钮焦点,使其看起来像是被Tab键插入其中?

删除MudRadio时,MudRadioGroup未 Select 正确的MudRadio

Xamarin.Forms项目中缺少MainPage.xaml

使用本地公共PEM文件加密字符串,使用Azure KayVault中的私钥解密

实例化列表时的集合表达式是什么?