Сложность: medium
Есть несколько камней, расположенных в разных позициях на оси X. Вам дан целочисленный массив stones - позиции камней. Назовите камень конечным, если он имеет наименьшую или наибольшую позицию. За один ход вы берете конечный камень и перемещаете его в незанятую позицию так, чтобы он перестал быть конечным. В частности, если камни находятся, скажем, в позиции stones = [1,2,5], вы не можете переместить конечный камень в позицию 5, поскольку перемещение его в любую позицию (например, 0 или 3) сохранит этот камень в качестве конечного. Игра заканчивается, когда вы не можете сделать больше ни одного хода (т.е, камни находятся в трех последовательных позициях). Возвращает целочисленный массив answer длины 2, где: answer[0] - минимальное количество ходов, которое вы можете сделать, а answer[1] - максимальное количество ходов, которое вы можете сделать.
Пример:
Input: stones = [7,4,9]
Output: [1,2]
👨💻 Алгоритм:
1⃣Сортировка:
Сначала отсортируем массив камней.
2⃣Максимальное количество ходов:
Максимальное количество ходов равно (последняя позиция - первая позиция + 1) - количество камней, исключая случаи, когда уже имеются три последовательных камня.
3⃣Минимальное количество ходов:
Минимальное количество ходов можно определить следующим образом:
Если первый или последний камень уже находится на своем месте, необходимо проверить остальные камни.
Если расстояние между первым и последним камнем равно 2 (то есть, всего три камня и они расположены последовательно), то минимальное количество ходов равно 0.
В других случаях минимальное количество ходов равно либо 2 (если среди первых или последних трех камней есть два подряд и одно пропущенное), либо 1 (если можно переместить один камень в нужное место).
😎 Решение:
def numMovesStonesII(stones):
stones.sort()
n = len(stones)
max_moves = stones[-1] - stones[0] + 1 - n
max_moves -= min(stones[1] - stones[0] - 1, stones[-1] - stones[-2] - 1)
min_moves = float('inf')
j = 0
for i in range(n):
while j < n and stones[j] - stones[i] + 1 <= n:
j += 1
already_in_window = j - i
if already_in_window == n - 1 and stones[j-1] - stones[i] + 1 == n - 1:
min_moves = min(min_moves, 2)
else:
min_moves = min(min_moves, n - already_in_window)
return [min_moves, max_moves]
Ставь 👍 и забирай 📚 Базу знаний