翻转一个二进制数所能得到的连续1或0的最大值

本文关键字：连续 最大值 一个 二进制数 翻转 | 更新日期: 2023-09-27 18:15:50

给定一个二进制数，求出仅翻转1位(1或0)即可得到的连续1或0的最大值

给出的代码是

    public int getMacCon(string[] A)
    {
        int n = A.Length;
        int result = 0;
        for (int i = 0; i < n - 1; i++)
        {
            if (A[i] == A[i + 1])
                result = result + 1;
        }
        int r = -2;
        for (int i = 0; i < n; i++)
        {
            int count = 0;
            if (i > 0)
            {
                if (A[i - 1] != A[i])
                    count = count + 1;
                else
                    count = count - 1;
            }
            if (i < n - 1)
            {
                if (A[i + 1] != A[i])
                    count = count + 1;
                else
                    count = count - 1;
            }
            r = Math.Max(r, count);
        }
        return result + r;
    }
我发现很难弄清楚这里的逻辑。特别是下面给出的部分 
    for (int i = 0; i < n - 1; i++)
    {
        if (A[i] == A[i + 1])
            result = result + 1;
    }
如果有人能给我解释一下这个解决方案的逻辑，我将非常感激。由于

翻转一个二进制数所能得到的连续1或0的最大值

您突出显示的位只是计算当前相邻相等值的数量，即一个值(A[i])等于下一个值(A[i+1])。然后它依次询问(第二个循环)，对于每个值，翻转它是否会增加、减少或不改变相邻相等值的数量;因此，如果当前值与前一个值(A[i-1] != A[i])不同，则翻转将是增加-否则减少;其后的也是如此。最后的结果是预先存在的相邻相等值的数目(result)，加上在扫描中发现的最佳增量(r)。

public int getMacCon(string[] A)
{
    int n = A.Length;
    int result = 0;
    // find how many adjacent values are currently in the string
    for (int i = 0; i < n - 1; i++)
    {
        // if same as the next value, that's a hit
        if (A[i] == A[i + 1])
            result = result + 1;
    }
    // worst case delta from flipping one value is that me make it
    // worse on both sides, so -2
    int r = -2;
    // now consider each value in turn
    for (int i = 0; i < n; i++)
    {
        int count = 0;
        if (i > 0) // test value before, if not the first value
        {
            if (A[i - 1] != A[i])
                count = count + 1; // before is different; flip is incr
            else
                count = count - 1; // before is same; flip is decr
        }
        if (i < n - 1) // test value after, if not the last value
        {
            if (A[i + 1] != A[i])
                count = count + 1; // after is different; flip is incr
            else
                count = count - 1; // after is same; flip is decr
        }
        // compare that to the tracking counter, and keep the best value
        r = Math.Max(r, count);
    }
    // final result is sum of pre-existing count plus the delta
    return result + r;
}

顺便说一句，优化可能是将第二个循环测试从i < n更改为i < n && r != 2 -即，一旦找到最佳增量(使两边都更好，+2)就停止

不直接回答你的问题(Marc Gravell的回答涵盖了足够的内容)，但我只需要添加我将如何解决这个问题:

  1. 用RLE(运行长度编码)对字符串进行编码

    所以你需要b,v,n值的数组。其中b>=0为起始位置，v={0,1}为位值，n为顺次出现次数。例如:

    const int _max=100; // max number of bits
int b[_max],v[_max],n[_max],bvns=0;

    bvns是数组中已使用b,v,n的个数。

  2. 重置您的实际解决方案

    您需要位位置来改变ix和翻转sz后产生的后续位数计数。

  3. 扫描RLE中n=1

    如果找到

    ，则表示RLE中的前后项是相同的，因此翻转将连接它们。因此，计算结果大小，如果大于则存储为实际解决方案，如:

    for (int i=1;i<bvns-1;i++) // scann RLE except first and last item
 if (n[i]==1) // single bit found
  {
  l=n[i-1]+1+n[i+1]; // resulting size
  if (l>=sz) { sz=l; ix=b; } // update solution
  }

  4. 检验扩增单序列是否较大

    : 

    for (int i=0;i<bvns;i++) // scann RLE
 if (n[i]>=sz) // result is bigger?
  {
  sz=l; ix=b-1; // update solution
  if (ix<0) ix=b+n[i];
  }
相关文章：