Created
July 19, 2021 10:56
-
-
Save Lawliet-L/abd59c482c224a31d3d1055eea68130d to your computer and use it in GitHub Desktop.
Задача о длиной цепочке единиц
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Формулировка задачи: | |
* Дана последоватльность 0 и 1 | |
* Нужно найти самую длинную последовательность из 1 (единиц) после удаления любого элемента | |
*/ | |
class Solution { | |
/** | |
* Находит максимальную длину последовательности единиц(1) в массиве с учетом удаления одного из элементов, будь то 0 или 1 | |
* Использует sliding window для нахождения максимальной последовательности единиц, таким образом сложность алгоритма O(n) т.к. каждый элемент обрабатывается лишь единожды | |
* При нахождении второго элемента в sliding window, отличного от 1 оно сжимается таким образом, чтобы содержать как максимум 1 элемент отличный от единицы | |
* Требования алгоритма по памяти O(1) т.к. из дополнительных переменных используются только примитивы 3 типа int и один типа boolean | |
* @param sequence - массив состоящий из 0 и 1, т.к. алгоритм завязан на подсчет 1, то может содержать любое значение byte | |
* @return - максимальная длина последовательных единиц в массиве с учетом удаления одного элемента из этой последовательности | |
*/ | |
private static int maxOnesAfterRemoveItem(byte[] sequence) { | |
int maxSequenceOfOnes = 0; | |
boolean containsNotOne = false; // индикация того, что текущее sliding window содержит в себе 0 | |
for(int leftIndex = 0, rightIndex = 0; rightIndex < sequence.length; rightIndex++) { | |
if(sequence[rightIndex] != 1) { // при нахождении второго элемента отличного от 1 подрезаем sliding window слева чтобы исключить первый | |
while(containsNotOne) { | |
if(sequence[leftIndex] != 1) { | |
containsNotOne = false; | |
} | |
leftIndex++; | |
} | |
containsNotOne = true; | |
} | |
maxSequenceOfOnes = Math.max(maxSequenceOfOnes, rightIndex - leftIndex); | |
} | |
return maxSequenceOfOnes; | |
} | |
public static void main(String[] args) { | |
assert(maxOnesAfterRemoveItem(new byte[]{0,0}) == 0); | |
assert(maxOnesAfterRemoveItem(new byte[]{0,1}) == 1); | |
assert(maxOnesAfterRemoveItem(new byte[]{1,0}) == 1); | |
assert(maxOnesAfterRemoveItem(new byte[]{1,1}) == 1); | |
assert(maxOnesAfterRemoveItem(new byte[]{1, 1, 0, 1, 1}) == 4); | |
assert(maxOnesAfterRemoveItem(new byte[]{1, 1, 0, 1, 1, 0, 1, 1, 1}) == 5); | |
assert(maxOnesAfterRemoveItem(new byte[]{1, 1, 0, 1, 1, 0, 1, 1, 1, 0}) == 5); | |
assert (maxOnesAfterRemoveItem(new byte[]{1}) == 0); | |
assert (maxOnesAfterRemoveItem(new byte[]{0}) == 0); | |
assert (maxOnesAfterRemoveItem(new byte[]{1,0,1}) == 2); | |
assert (maxOnesAfterRemoveItem(new byte[]{1,1,1}) == 2); | |
assert (maxOnesAfterRemoveItem(new byte[]{1,1,1,0,1}) == 4); | |
assert (maxOnesAfterRemoveItem(new byte[]{1,1,1,0,1,1}) == 5); | |
assert (maxOnesAfterRemoveItem(new byte[]{1,1,1,0,1,1,0}) == 5); | |
assert (maxOnesAfterRemoveItem(new byte[]{0,1,1,1,0,1,1,0}) == 5); | |
assert (maxOnesAfterRemoveItem(new byte[]{0,1,1,1,0,1,1,1}) == 6); | |
assert (maxOnesAfterRemoveItem(new byte[]{1,1,1,1,1,1,1,1}) == 7); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment