Cho một mảng các số nguyên nums. Hãy xoay mảng sang phải k bước, trong đó k là số nguyên không âm.
Yêu cầu tối ưu: Thao tác trực tiếp trên mảng (in-place) với O(1) bộ nhớ phụ.
Ví dụ 1:
Input: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
Output: [5, 6, 7, 1, 2, 3, 4]
Giải thích:
Xoay 1 bước: [7, 1, 2, 3, 4, 5, 6]
Xoay 2 bước: [6, 7, 1, 2, 3, 4, 5]
Xoay 3 bước: [5, 6, 7, 1, 2, 3, 4]Định Dạng Đầu Vào (Input)
Dòng 1: Mảng số nguyên nums
Dòng 2: Số nguyên k
Dòng 2: Số nguyên k
Định Dạng Đầu Ra (Output)
Mảng nums sau khi xoay k bước
Ràng Buộc (Constraints)
1 <= nums.length <= 10^50 <= k <= 10^5
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[1, 2, 3, 4, 5, 6, 7]
3
Output:
[5, 6, 7, 1, 2, 3, 4]
Giải thích: Xoay 3 bước
Ví dụ 2:
Input:
[-1, -100, 3, 99]
2
Output:
[3, 99, -1, -100]
Giải thích: Xoay 2 bước
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Kỹ thuật Đảo 3 Lần (Three Reversals) O(n) Thời Gian & O(1) Bộ Nhớ
1. Lấy k = k % n.
2. Đảo ngược toàn bộ mảng: reverse(0, n - 1).
3. Đảo ngược k phần tử đầu: reverse(0, k - 1).
4. Đảo ngược các phần tử còn lại: reverse(k, n - 1).
Dữ liệu đầu vào (Input):
[1, 2, 3, 4, 5, 6, 7]
3
Kết quả kỳ vọng (Expected Output):
[5, 6, 7, 1, 2, 3, 4]
Dữ liệu đầu vào (Input):
[-1, -100, 3, 99]
2
Kết quả kỳ vọng (Expected Output):
[3, 99, -1, -100]
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
