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

Ответ 1

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

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

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

Затем выполняется следующее:

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

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

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

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

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

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

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

Ответ 2

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

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 first half i.e. first consecutive ones are the previous set 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 и т.д. И т.д. В этой точке, и этого должно быть достаточно

Ответ 3

Вот мое решение. Он чист, принимает 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 });
    }

}

Ответ 4

Используя динамическое программирование, вы можете решить этот код. Сложность времени - 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));   
}

Ответ 5

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

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 ".

Ответ 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;
}

Ответ 7

Космическая сложность - O (1)

Сложность времени - O (n)

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

Ответ 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));
}