SeniorКодРедкоЕщё не отвечали
Длиннейшая серия из 1 после удаления ровно одного элемента
Дан бинарный массив. Верните длину длиннейшей серии 1, получаемой после удаления РОВНО одного элемента. Удаление обязательно даже без нулей, поэтому массив из одних единиц длины L даёт L-1.
Требования:
- O(n) по времени, O(1) доп. памяти; вход не менять.
int maxOnesAfterOneDeletion(const std::vector<int>& a) {
// ваш код здесь
}Допишите реализацию.
Скользящее окно, допускающее не более одного нуля внутри; ответ — максимальный размер окна минус один (один элемент всегда удаляется). Когда нулей нет, это «минус один» всё равно применяется, давая L-1 для массива из одних единиц. Один проход, O(n), O(1).
- ✗Возвращать размер окна без вычитания единицы за обязательное удаление
- ✗Провалить случай всех единиц, где элемент всё равно удаляется (ответ L-1)
- ✗Допускать более одного нуля в окне
- →Чем «ровно одно» удаление отличается от «не более одного» для массива всех единиц?
- →Как обобщить окно на удаление до k элементов?
Оглавление
Задача
Найдите длиннейшую серию единиц после удаления ровно одного элемента, за O(n).
Решение
#include <vector>
#include <algorithm>
int maxOnesAfterOneDeletion(const std::vector<int>& a) {
int left = 0, zeros = 0, best = 0;
for (int right = 0; right < static_cast<int>(a.size()); ++right) {
if (a[right] == 0) ++zeros;
while (zeros > 1) { if (a[left++] == 0) --zeros; }
best = std::max(best, right - left + 1);
}
return best - 1; // ровно одно удаление обязательно
}Ключевые моменты
- Окно допускает не более одного нуля.
- Ответ — лучший размер окна минус один.
- На массиве всех единиц всё равно удаляем один элемент: L-1.
Оглавление
