Получить самую длинную непрерывную последовательность 1s

Question

Недавно я столкнулся с проблемой, о он говорит:

Given an array of 0s and 1s, find the position of 0 to be 
replaced with 1 to get longest continuous sequence of 1s. 

For example : Array- 1,1,0,0,1,0,1,1,1,0,1,1,1 
Output - index 9 

Я попытался грубой силой подход заменяя каждого сталкивался 0 с 1 и после каждой такой замены, я пересчитал большую непрерывную повторяющуюся последовательность из 1 и обновлять его каждый раз.

Есть ли лучший подход/алгоритм для решения этой проблемы?

Answer 1

Для этого должно быть однопроходное решение. Общая идея состоит в том, чтобы подсчитать их и добавить длины для каждого нуля по мере продвижения. Ну, не каждый ноль, только последний столкнулся с одним и самым длинным.

Вы должны следить за двумя вещами:

• Самая длинная цепь до сих пор.
• Предыдущее нулевое значение вместе с длиной предыдущих.

Процесс затем следующим образом:

1. Начиная ходьбу через строку, пока не столкнулись с нуля. Следите за количеством тех, которые вы идете.

2. Когда вы нажмете нуль, запомните положение нуля вместе с числом предыдущих 1 секунд.

3. Подсчитайте 1s до следующего нуля.

4. Вернитесь к предыдущему нолю и добавьте новые «единицы» в предыдущие «единицы». Если это длиннее самой длинной цепи, замените самую длинную цепь.

5. Помните этот нуль вместе с предыдущими 1s.

6. Повторяйте, пока не достигнете конца строки.

7. В конце строки вернитесь назад и добавьте длину к предыдущему нолю и, если необходимо, замените самую длинную цепь.

Answer 2

Вы можете себе представить, вы должны поддерживать набор 1, позволяющий только один из них 0, так

1) walk over the array, 
2) if you are getting a 1, 
    check a flag if you are already in a set, if no, 
then you start one and keep track of the start, 
    else if yes, you just update the end point of set 
3) if you get a 0, then check if it can be included in the set, 
(i.e. if only one 0 surrounded by 1 "lonely zero") 
if no, reset that flag which tells you you are in a set 
else 
    is this first time ? (store this 0 pos, initialized to -1) 
     yes, then just update the zero position 
     else okk, then previous set, of one..zero..one gets finished here, 
now the new set's first half i.e. first consecutive ones are the previous set's last portion, 
so set the beginning of the set marker to last zero pos +1, update the zero position. 

Так что, когда, чтобы проверить, если текущий набор, имеющий наивысшую длину? См., Мы обновляем конечную точку только в разделе 2 -> else, поэтому просто проверяйте с max start, max end и т. Д. В этой точке, и этого должно быть достаточно

Answer 3

Используя динамическое программирование, вы можете решить этот код. Сложность времени - это O (n), а пространственная сложность - O (n).

public static int Flipindex(String mystring){ 

    String[] arr = mystring.split(","); 
    String [] arrays= new String[arr.length]; 
    for(int i=0;i<arr.length;i++){ 
     arrays[i]="1"; 
    } 
    int lastsum = 0; 
    int[] sumarray =new int[arr.length]; 
    for(int i=0;i<arr.length;i++){ 
     if(!arr[i].equals(arrays[i])){ 
      ++lastsum;    
     } 
     sumarray[i]=lastsum; 
    } 
    int [] consecsum = new int [sumarray[sumarray.length-1]+1]; 

    for(int i: sumarray){ 
     consecsum[i]+=1; 
    } 

    int maxconsecsum=0,startindex=0; 

    for(int i=0;i<consecsum.length-1;i++){ 
     if((consecsum[i]+consecsum[i+1])>maxconsecsum){ 
      maxconsecsum=(consecsum[i]+consecsum[i+1]); 
      startindex=i; 
     } 
    } 
    int flipindex=0; 
    for(int i=0;i<=startindex;i++){ 
     flipindex+=consecsum[i]; 
    } 
    return flipindex; 

} 


public static void main(String[] args) { 
    String s= "1,1,0,0,1,0,1,1,1,0,1,1,1"; 
    System.out.println(Flipindex(s)); 
} 

Answer 4

Игра вокруг с консолью дала мне это, подправить и покрыть края случай, то вы хорошо идти

function getIndices(arr, val) { 
    var indexes = [], i = -1; 
    while ((i = arr.indexOf(val, i+1)) != -1){ 
     indexes.push(i); 
    } 
    return indexes; 
} 

var a = [1,1,1,1,1,0,0,1,0,0,1,1,1,0,1,1,1,1,1,1,0]; 

var z = getIndices(a, 0); 
z.unshift(0); 

var longestchain = 0; 
var target = 0; 
for(var i=0;i<z.length;i++) { 
    if(i == 0) { //first element 
     longestchain = z[i] + z[i+1]; 
     target = i; 
    } else if (i == z.length-1) { //last element 
     var lastDistance = Math.abs(z[i] - z[i-1]);  
     if(lastDistance > longestchain) { 
      longestchain = lastDistance; 
      target = i; 
     } 
    } else { 
     if(Math.abs(z[i] - z[i+1]) > 1) { //consecutive 0s 
      //look before and ahead 
      var distance = Math.abs(z[i-1] - z[i]) + Math.abs(z[i] - z[i+1]); 
      if(distance > longestchain) { 
       longestchain = distance; 
       target = i;   
      } 
     } 
    } 
} 
console.log("change this: " + z[target]); 

Я первый поиск нулей в массиве и сохранили позицию в другом массиве, поэтому в моем примере вы получите что-то вроде этого [0,5,6,8,9,13,20], затем я просто запускаю один цикл, чтобы найти наибольшее расстояние от каждого элемента со своими соседними, и сохраняя расстояние в «самой длинной цепочке» », каждый раз, когда я нахожу более длинную цепочку, я обращаю внимание на индекс, в данном случае« 13 ».

Answer 5

Это мое решение. Он чист, принимает O (n) время и O (1) память.

public class Q1 { 
    public Q1() {  
    } 

    public static void doit(int[] data) {  
     int state = 0; 
     int left, right, max_seq, max_i, last_zero;    
     left = right = 0; 
     max_seq = -1; 
     max_i = -1; 

     // initialization 
     right = data[0]; 
     last_zero = (data[0]==0) ? 0 : -1; 
     for (int i = 1; i < data.length; i++) { 
      state = data[i - 1] * 10 + data[i]; 
      switch (state) { 
      case 00: //reset run 
       left = right = 0; 
       last_zero = i; 
       break; 

      case 01: // beginning of a run 
       right++;     
       break; 

      case 10:// ending of a run 
       if(left+right+1>max_seq){ 
        max_seq = left+right+1; 
        max_i = last_zero; 
       } 
       last_zero = i; //saving zero position 
       left = right; // assigning left 
       right = 0; // resetting right 
       break; 

      case 11: // always good 
       right++; 
       break; 
      } 
     } 
     //wrapping up 
     if(left+right+1>max_seq){ 
      max_seq = left+right+1; 
      max_i = last_zero; 
     } 

     System.out.println("seq:" + max_seq + " index:" + max_i); 
    } 

    public static void main(String[] args) {    
     //Q1.doit(new int[] { 1,1,0,0,1,0,1,1,1,0,1,1,1 }); 
     Q1.doit(new int[] { 1,1,0,0,1,0,1,1,1,0,1,1,1 }); 
    } 

} 

Answer 6

Эта реализация кода на языке C основана на алгоритме, предоставленном @ gordon-linoff выше.

int maxOnesIndex1(bool arr[], int n) 
{ 

    int prevZeroPos = 0; 
    int oldOneCnt = 0; 
    int newOneCnt = 0; 
    int longestChainOfOnes = 0; 
    int longestChainPos = 0; 
    int i; 

    for(i=0; i<n; i++) 
    { 

     if(arr[i]!=0) 
     { 
      oldOneCnt++; 
     } 
     else // arr[i] == 0 
     { 
      prevZeroPos = i; 
      newOneCnt = 0; 

      // move by one to find next sequence of 1's 
      i++; 

      while(i<n && arr[i] == 1) 
      { 
       i++; 
       newOneCnt++; 
      } 

      if((oldOneCnt+newOneCnt) > longestChainOfOnes) 
      { 
       longestChainOfOnes = oldOneCnt+newOneCnt+1; 
       longestChainPos = prevZeroPos; 
      } 

      oldOneCnt = 0; 
      i = prevZeroPos; 

     } 

    } 

    if((oldOneCnt+newOneCnt) > longestChainOfOnes) 
    { 
     longestChainOfOnes = oldOneCnt+newOneCnt+1; 
     longestChainPos = prevZeroPos; 
    } 

    return longestChainPos; 
} 

Answer 7

Пространство Сложность - O (1)

Время Сложность - О (п)

A = map(int, raw_input().strip().split(' ')) 
left = 0 #Numbers of 1 on left of current index. 
right = 0 #Number of 1 on right of current index. 
longest = 0 #Longest sequence so far 
index = 0 
final_index = 0 # index of zero to get the longest sequence 
i = 0 
while i < A.__len__(): 
    if A[i] == 0: 
     left = right 
     index = i 
     i += 1 
     right = 0 
     while i < A.__len__() and A[i] != 0: 
      right += 1 
      i += 1 
     if left + right + 1 > longest: 
      final_index = index 
      longest = left + right + 1 

    else: 
     right += 1 
     i += 1 

print final_index, longest 

Answer 8

Здесь немного другой алгоритм

public static int zeroIndexToGetMaxOnes(int[] binArray) { 
    int prevPrevIndex = -1, prevIndex = -1,currentLenght= -1, maxLenght = -1, requiredIndex = -1; 

    for (int currentIndex = 0; currentIndex < binArray.length; currentIndex++) { 
     if (binArray[currentIndex] == 0) { 
      if (prevPrevIndex != -1) { 
       currentLenght = currentIndex - (prevPrevIndex + 1); 
       if (currentLenght > maxLenght) { 
        maxLenght = currentLenght; 
        requiredIndex = prevIndex; 
       } 
      } 
      prevPrevIndex = prevIndex; 
      prevIndex = currentIndex; 
     } else {// case when last element is not zero, and input contains more than 3 zeros 
      if (prevIndex != -1 && prevPrevIndex != -1) { 
       currentLenght = currentIndex - (prevPrevIndex + 1); 
       if (currentLenght > maxLenght) { 
        maxLenght = currentLenght; 
        requiredIndex = prevIndex; 
       } 
      } 
     } 
    } 

    if (maxLenght == -1) { // less than three zeros 
     if (prevPrevIndex != -1) { // 2 zeros 
      if (prevIndex > (binArray.length - prevPrevIndex - 1)) { 
       requiredIndex = prevPrevIndex; 
      } else { 
       requiredIndex = prevIndex; 
      } 

     } else { // one zero 
      requiredIndex = prevIndex; 
     } 
    } 
    return requiredIndex; 
} 

Здесь блок проверяет

@Test 
public void replace0ToGetMaxOnesTest() { 
    int[] binArray = {1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1}; 
    int index = ArrayUtils.zeroIndexToGetMaxOnes(binArray); 
    assertThat(index, is(9)); 

    binArray = new int[]{1,0,1,1,1,0}; 
    index = ArrayUtils.zeroIndexToGetMaxOnes(binArray); 
    assertThat(index, is(1)); 

    binArray = new int[]{0,1,1,1,0,1}; 
    index = ArrayUtils.zeroIndexToGetMaxOnes(binArray); 
    assertThat(index, is(4)); 

    binArray = new int[]{1,1,1,0,1,0}; 
    index = ArrayUtils.zeroIndexToGetMaxOnes(binArray); 
    assertThat(index, is(3)); 

    binArray = new int[]{0,1,1,1,0}; 
    index = ArrayUtils.zeroIndexToGetMaxOnes(binArray); 
    assertThat(index, is(4)); 

    binArray = new int[]{1,1,1,1,0}; 
    index = ArrayUtils.zeroIndexToGetMaxOnes(binArray); 
    assertThat(index, is(4)); 

    binArray = new int[]{0,1,1,1,1}; 
    index = ArrayUtils.zeroIndexToGetMaxOnes(binArray); 
    assertThat(index, is(0)); 
}