JuniorДебаггингЧастоЕщё не отвечали
Исправьте счётчик длиннейшей серии единиц, теряющий последнюю серию
Функция должна возвращать длину длиннейшей серии подряд идущих 1, но даёт неверный ответ для массивов, кончающихся на 1, напр. {0,1,1,1} возвращает 0.
Найдите и исправьте ошибку.
int maxConsecutiveOnes(const std::vector<int>& nums) {
int cur = 0, best = 0;
for (int n : nums) {
if (n == 1) {
cur++;
} else {
best = std::max(best, cur); // max берётся только на нуле
cur = 0;
}
}
return best;
}Найдите и исправьте ошибку.
best обновляется только в ветке else (на нуле), поэтому хвостовая серия 1, не встретившая ноль, не сравнивается. Исправьте, обновляя best = max(best, cur) на каждой 1 (внутри if) или ещё раз после цикла. O(n).
- ✗Считать счётчик верным, ведь он работает для массивов, кончающихся на 0
- ✗Обновлять максимум лишь на границах серий, отмеченных нулём
- ✗Добавить проверку после цикла, но забыть про пустой массив
- →Как изменится исправление, если нужно вернуть и индекс начала серии?
- →Какой аналогичный баг для длиннейшей серии любого фиксированного значения?
Оглавление
Задача
Счётчик длиннейшей серии единиц теряет серию, которой кончается массив. Найдите и исправьте баг.
Решение
#include <vector>
#include <algorithm>
int maxConsecutiveOnes(const std::vector<int>& nums) {
int cur = 0, best = 0;
for (int n : nums) {
if (n == 1) {
cur++;
best = std::max(best, cur); // обновляем на каждой 1
} else {
cur = 0;
}
}
return best;
}Ключевые моменты
- Баг: максимум брался только в ветке
else, на нуле. - Хвостовая серия единиц так не сравнивается.
- Чиним обновлением максимума на каждой
1(или после цикла).
Оглавление
