Ctrl K

Соседние доски одного цвета

Средняя
Забор состоит из planks досок, стоящих в ряд и пронумерованных с нуля. Сначала ни одна доска не покрашена. Маляр делает мазки по списку strokes: мазок [i, c] перекрашивает доску i в цвет c (цвета — положительные числа; прежний цвет доски пропадает). После каждого мазка посчитайте, сколько пар соседних досок покрашены в один и тот же цвет. Непокрашенные доски пар не образуют. Верните список этих чисел — по одному на каждый мазок, в том же порядке.
Пример 1
planks=5, strokes=[[1, 4], [2, 4], [0, 4], [1, 7], [3, 4]] → [0, 1, 2, 0, 1]

Забор после каждого мазка: [0,4,0,0,0] → 0 пар; [0,4,4,0,0] → 1; [4,4,4,0,0] → 2; [4,7,4,0,0] → 0; [4,7,4,4,0] → 1.

Пример 2
planks=2, strokes=[[0, 3], [1, 3], [1, 3]] → [0, 1, 1]

После второго мазка обе доски цвета 3 — одна пара. Повторная покраска в тот же цвет ничего не меняет.

Пример 3
planks=1, strokes=[[0, 5]] → [0]

У единственной доски нет соседей.

Ограничения
  • 1 ≤ planks ≤ 10⁵
  • 1 ≤ len(strokes) ≤ 10⁵
  • strokes[k].length == 2
  • 0 ≤ i < planks
  • 1 ≤ c ≤ 10⁵
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиДве доски и вода СредняяТройки с нулевой суммой СредняяСумма тройки ближе всего к цели СредняяЧетыре числа с заданной суммой СредняяСледующая расстановка по порядку Средняя
загружаем Python…
Вход
planks=5, strokes=[[1, 4], [2, 4], [0, 4], [1, 7], [3, 4]]
Ожидается
[0, 1, 2, 0, 1]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 77 тестов на сервере, включая скрытые.