Thuật toán Python

Xoay list trong Python

Đưa k giá trị cuối lên đầu mà vẫn giữ thứ tự của chúng, chỉ với một biểu thức cắt list.

  • Trung cấp
  • Đọc trong 2 phút
  • 1 ví dụ chạy được
Bạn sẽ học được gì
  • Xoay phải bằng slicing
  • Dùng % để xử lý k lớn
  • collections.deque.rotate
Xoay phải 2 vị trí
1
2
3
4
5
4
5
1
2
3

Cắt đôi và đổi chỗ hai phần

Vấn đề

Việc xoay vòng một list hay gặp trong lịch trực (đến lượt ai), bộ đệm vòng, các mẹo xử lý ảnh và câu hỏi phỏng vấn. Dịch từng bước một thì được nhưng chậm; slice làm xong chỉ trong một bước.

Hình dung đời thường

Xoay list giống một bàn tròn mà mọi người cùng dịch sang phải hai ghế. Hai người cuối đi vòng lên hai ghế đầu, còn những người khác giữ nguyên thứ tự. Xoay đúng bằng số ghế thì chẳng có gì thay đổi.

Từ chiếc bàn tròn đến code
steps %= len(values)🔁 Dịch 7 ghế ở bàn 5 chỗ cũng như dịch 2 ghế
values[-steps:]🚶 Hai người cuối chuyển lên đầu
values[:-steps]🪑 Những người còn lại giữ nguyên thứ tự
+🔗 Xếp họ ngồi cạnh nhau: [4, 5, 1, 2, 3]
Cắt list thành hai mảnh rồi đổi chỗ hai mảnh.
Định nghĩa ngắn gọn

Xoay list sang phải k bước là chuyển k phần tử cuối lên đầu mà vẫn giữ thứ tự của mọi phần tử.

Những điểm quan trọng

  1. if not values: return [] xử lý list rỗng, vì khi đó % len(values) sẽ chia cho 0.
  2. steps %= len(values) làm cho số bước lớn quay vòng lại.
  3. values[-steps:] là phần đuôi chuyển lên đầu: [4, 5].
  4. values[:-steps] là phần còn lại: [1, 2, 3], và + ghép hai mảnh lại.

Khi nào nên sử dụng?

  • Chia lượt xoay vòng và xếp lịch trực.
  • Bộ đệm vòng và cửa sổ dữ liệu trượt.
  • Câu hỏi phỏng vấn về slice và phép chia lấy dư.

Khi nào chưa cần

  • Xoay nhiều lần, mỗi lần một bước: collections.deque.rotate xoay tại chỗ rất hiệu quả.
  • List cực lớn khi bộ nhớ quan trọng: cách đảo ngược tại chỗ không cần tạo bản sao.

Xem cách hoạt động

Nhấp vào một ô hoặc kéo thanh trượt để chọn chỉ số. Chèn hoặc xóa để thấy vì sao mọi phần tử phía sau phải dịch chuyển.

Code ví dụ

Chạy code →
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))
Lấy nút Run cho ví dụ này

Kết quả khi chạy

[4, 5, 1, 2, 3]

Giải thích code

Phép chia lấy dư steps %= len(values) xử lý trường hợp số bước lớn hơn độ dài danh sách, vì xoay 7 lần một danh sách 5 phần tử cũng giống như xoay 2 lần. Hai phép cắt values[-steps:] và values[:-steps] lấy k phần tử cuối và phần còn lại, rồi ghép chúng theo thứ tự mới. Độ phức tạp thời gian và bộ nhớ đều là O(n).

Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.

Bài tập mở rộng

Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.

  1. Thử với danh sách rỗng, danh sách chỉ có một phần tử hoặc có giá trị trùng lặp.
  2. In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
  3. Đo thời gian chạy với 100, 1.000 và 10.000 phần tử, rồi so sánh với một cách giải khác.
Chạy trong trình biên dịch Python →

Lỗi hay gặp

Quên trường hợp số bước bằng 0

values[-0:] là cả list, nên thiếu % thì kết quả bị nhân đôi.

Sai
return values[-steps:] + values[:-steps]  # steps = 5 gives a list of 10
Cách sửa
steps %= len(values)
return values[-steps:] + values[:-steps]

Bạn học xong bài này chưa?

Đánh dấu đã học để theo dõi tiến độ của bạn.

Luyện tập với thử thách

Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.

Tất cả thử thách