algorithm - 通过用 '1' 替换任何一个 '0' 来查找二进制数组中最长的 '1' 序列

Question

我有一个仅由 0 和 1 组成的数组。任务是找到 0 的索引，将其替换为 1 会导致给定数组的最长可能序列。 解决方案必须在 O(n) 时间和 O(1) 空间内工作。

例如:

数组 - 011101101001
答案 - 4(产生 011111101001)

我的方法给出了比 O(n2) 更好的结果，但在输入长字符串时超时。

int findIndex(int[] a){

    int maxlength = 0; int maxIndex= -1;
    int n=a.length;
    int i=0; 
    while(true){

        if( a[i] == 0 ){
            int leftLenght=0;
            int j=i-1;
            //finding count of 1s to left of this zero
            while(j>=0){
                if(a[j]!=1){
                    break;
                }
                leftLenght++;
                j--;
            }

            int rightLenght=0;
            j=i+1;
            // finding count of 1s to right of this zero
            while(j<n){
                if(a[j]!=1){
                    break;
                }
                rightLenght++;
                j++;
            }

            if(maxlength < leftLenght+rightLenght + 1){
                maxlength = leftLenght+rightLenght + 1;
                maxIndex = i;
            }
        }
        if(i == n-1){
            break;
        }
        i++;
    }
    return maxIndex;
}

Answer 1

方法很简单，只需要在遍历数组的时候维护两个数，一个的连续 block 的当前个数，一个的最后一个连续 block 的个数，用零隔开。

注意:该解法假设数组中至少有一个零，否则返回-1

int cal(int[]data){
    int last = 0;
    int cur = 0;
    int max = 0; 
    int start = -1; 
    int index = -1;
    for(int i = 0; i < data.length; i++){
        if(data[i] == 0){
           if(max < 1 + last + cur){
              max = 1 + last + cur;
              if(start != -1){
                index = start;
              }else{
                index = i;
              }
           }
           last = cur;
           start = i;
           cur = 0;  
        }else{
            cur++;
        }
    }
    if(cur != 0 && start != -1){
       if(max < 1 + last + cur){
          return start;
       }
    }     
    return index;
}

O(n) 时间，O(1) 空间

现场演示:https://ideone.com/1hjS25