0

題幹懶人包

``````Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]
``````

• `1 <= nums.length <= 2 * 104`
• `-231 <= nums[i] <= 231 - 1`
• `0 <= k <= 105`

解法

1. 先用 tmp 紀錄最後一段的數組切片(比方說上面那個例題，先用tmp紀錄[5, 6, 7])
2. 將nums的第k項到最後一項用0到n-k項取代([4, 5, 6, 7]被[1, 2, 3, 4]取代)
3. 最後再將tmp放回去 ([1, 2, 3]被[5, 6, 7]取代)。

``````class Solution:
def rotate(self, nums, k: int) -> None:
n = len(nums)
# k 取餘數，比方說等於n根本不用旋轉
k %= n
if k != 0:
# 1
tmp = nums[-k:]
# 2
nums[k:n] = nums[:n - k]
# 3
nums[0:k] = tmp
``````

別人的正解

1. 首先先將整個數組翻轉一次
2. 接下來看k多少決定左邊以及右邊的分界
3. 翻轉左邊，然後翻轉右邊
``````1. [1,2,3,4,5,6,7] -> [7, 6, 5, 4, 3, 2, 1]
3. [7, 6, 5, 4, 3, 2, 1] -> [5, 6, 7, 4, 3, 2, 1]
3. [5, 6, 7, 4, 3, 2, 1] -> [5, 6, 7, 1, 2, 3, 4]
``````

``````class Solution:
def rotate(self, nums, k: int) -> None:
k %= len(nums)

def reverse(nums, i, j):
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1

reverse(nums, 0, len(nums)-1)
reverse(nums, 0, k-1)
reverse(nums, k, len(nums)-1)
``````

reverse 函數

``````# 比方說reverse([1, 2, 3, 4, 5, 6, 7], 0, 3)
# 第一次
[1, 2, 3, 4, 5, 6, 7] -> [4, 2, 3, 1, 5, 6, 7]
# 第二次(注意這次是2跟3交換了)
[4, 2, 3, 1, 5, 6, 7] -> [4, 3, 2, 1, 5, 6, 7]
# 準備第三次時i現在等於2，j現在等於1，因此停止
``````

``````def reverse(nums, i, j):
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
``````