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.
- Xoay phải bằng slicing
- Dùng % để xử lý k lớn
- collections.deque.rotate
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.
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 đầuvalues[:-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]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
if not values: return []xử lý list rỗng, vì khi đó% len(values)sẽ chia cho 0.steps %= len(values)làm cho số bước lớn quay vòng lại.values[-steps:]là phần đuôi chuyển lên đầu:[4, 5].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.rotatexoay 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ụ
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))
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.
- 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.
- In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
- Đ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.
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.
return values[-steps:] + values[:-steps] # steps = 5 gives a list of 10
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