将包含n个元素的数组向右旋转k步。
例如，如果 n = 7 , k = 3，给定数组 [1,2,3,4,5,6,7] ，向右旋转后的结果为 [5,6,7,1,2,3,4]。
注意:
尽可能找到更多的解决方案，这里最少有三种不同的方法解决这个问题。
要求空间复杂度为 O(1)
关联的问题: 反转字符串中的单词 II
将前n-k个原地反转，将后k个原地反转，再将整个数组原地反转，即得所求。【时间复杂度O(n)，空间复杂度O(1)】
class Solution(object):
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
k = k % len(nums)
self.reversePart(nums, 0, len(nums)-k-1)
self.reversePart(nums, len(nums)-k, len(nums)-1)
self.reversePart(nums, 0, len(nums)-1)
def reversePart(self, nums, start, end):
while start < end:
nums[start], nums[end] = nums[end], nums[start]
start, end = start+1, end-1
空间复杂度为O(1)，我们可能会想到对原数组做k次“循环右移一位”的解法。然而直接这么做会超时，所以可以考虑下面的优化做法。其思想是，每次把数组最后k位交换到正确的位置，循环直到所有元素位置正确。
class Solution:
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
k, start, n = k % len(nums), 0, len(nums)
while k % n != 0 and n > 0:
for i in range(k):
nums[start + i], nums[len(nums) - k + i] = nums[len(nums) - k + i], nums[start + i]
start, n = start + k, n - k
k = k % n
