Алгоритмы на Python

Циклический сдвиг списка в Python

В этом уроке вы сдвинете список на k позиций вправо с помощью срезов (slicing).

  • Средний
  • Чтение: 2 мин
  • Примеров для запуска: 1

Введение

Какую задачу это решает

Поворот списка встречается в расписаниях (чья очередь следующая), кольцевых буферах, трюках с изображениями и на собеседованиях. Сдвиг элементов по одному шагу работает, но медленно; срезы делают это за один шаг.

Пример из жизни

Поворот списка похож на круглый стол, где все пересаживаются на два места вправо. Последние двое обходят стол и садятся на первые места, а остальные сохраняют свой порядок. Поворот на полное число мест ничего не меняет.

От круглого стола к коду
steps %= len(values)🔁 Сдвиг на 7 мест за столом на 5 - то же, что на 2
values[-steps:]🚶 Последние двое переходят вперёд
values[:-steps]🪑 Остальные сохраняют порядок
+🔗 Посадить вместе: [4, 5, 1, 2, 3]
Разрежьте список на две части и поменяйте их местами.
Одним предложением

Поворот списка вправо на k переносит его последние k элементов в начало, сохраняя порядок всех элементов.

Главное

  1. if not values: return [] обрабатывает пустой список, где % len(values) делило бы на ноль.
  2. steps %= len(values) заставляет большие повороты идти по кругу.
  3. values[-steps:] - хвост, который переходит вперёд: [4, 5].
  4. values[:-steps] - остальное: [1, 2, 3], а + соединяет две части.

Когда это нужно?

  • Очерёдность по кругу и расписания.
  • Кольцевые буферы и сдвигающиеся окна данных.
  • Вопросы на собеседованиях о срезах и делении с остатком.

Когда это не нужно

  • Многократный поворот на один шаг: collections.deque.rotate делает это на месте эффективно.
  • Огромные списки, где важна дополнительная память: метод с переворотом на месте обходится без копии.

Как это работает

Щёлкните по ячейке или двигайте ползунок, чтобы выбрать индекс. Вставьте или удалите элемент и посмотрите, почему все следующие элементы должны сдвинуться.

Пример кода

Запустить код →
main.py
def rotate_right(values, steps):
    if not values:
        return []
    steps %= len(values)
    return values[-steps:] + values[:-steps]

print(rotate_right([1, 2, 3, 4, 5], 2))
Получить кнопку запуска для этого примера

Результат выполнения

[4, 5, 1, 2, 3]

Разбор кода

Остаток от деления steps %= len(values) обрабатывает случай, когда число шагов больше длины списка: сдвиг списка из 5 элементов на 7 равносилен сдвигу на 2. Срезы values[-steps:] и values[:-steps] берут последние k элементов и остальную часть и соединяют их в новом порядке. И по времени, и по памяти сложность O(n).

Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.

Упражнения для практики

Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.

  1. Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
  2. Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
  3. Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Запустить в компиляторе Python →

Частые ошибки

Забыт случай нулевого сдвига

values[-0:] - весь список, поэтому без % результат удваивается.

Ошибка
return values[-steps:] + values[:-steps]  # steps = 5 gives a list of 10
Исправление
steps %= len(values)
return values[-steps:] + values[:-steps]

Закончили этот урок?

Отметьте его как изученный, чтобы следить за прогрессом.

Попрактикуйтесь на задаче

Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.

Все задачи