Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

 123456 Input: [1,2,3,4,5,6,7] and 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] 

Example 2:

 12345 Input:[-1,-100,3,99] and k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100] 

Note:

1. Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
2. Could you do it in-place with O(1) extra space?

Related Topics:Dynamic ProgrammingBacktracking

## 解題邏輯與實作

### 解法1

 12345678910 class Solution: def rotate(self, nums: List[int], k: int) -> None: n = len(nums) k %= n for i in range(k) : final = nums[n-1] for idx in range((n-1)-1,-1, -1): nums[idx+1] = nums[idx] nums[0] = final 

 1 nums = [nums[n-1]] + nums[:-1] 

### 解法2

 1234567891011 class Solution: def rotate(self, nums: List[int], k: int) -> None: n = len(nums) k %= n final = nums[n-k:] for idx in range((n-k)-1,-1, -1): nums[idx+k] = nums[idx] for idx in range(len(final)): nums[idx] = final[idx] 

Runtime: 68 ms, faster than 46.18% of Python3 online submissions forRotate Array. Memory Usage: 13.4 MB, less than 5.04% of Python3 online submissions for Rotate Array.

### 解法3

Example k = 3
1, 2, 3, 4, 5, 6, 7
4, 3, 2, 1, 5, 6, 7
4, 3, 2, 1, 7, 6, 5
5, 6, 7, 1, 2, 3, 4

 1234567891011121314 class Solution: def rotate(self, nums: List[int], k: int) -> None: n = len(nums) k %= n self.reverse(nums, 0, (n-k)-1) self.reverse(nums, n-k, n-1) self.reverse(nums, 0, n - 1) def reverse(self, nums, start, end): while start < end : nums[start], nums[end] = nums[end], nums[start] start += 1 end -= 1