目標：
這題主要目的同樣是協助讀者熟悉陣列操作。

原題：

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

Example 1:
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:
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:
Try to come up with as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?

分析/解題：
題目給定一個陣列，將其往右輪轉k步，
要求直接將該陣列調整成輪轉後的結果。

這題一旦沒有Note的要求的話瞬間簡單一百倍。
舉例來說，我們可以直接將後k項和前l-k項合併起來(l為陣列長度)，
就會是答案了；或者，將整個陣列重複銜接一次，取[(l-k):(2 * l - k)]亦可。
(這兩個解法筆者列在Python的註解中供讀者參閱)
但，它們都不是in-place。

要考慮到in-place的話，我們必須知道，
一定有方法能讓他們跑到該有的地方，且不需用到超過O(1)以外的空間，
一般就意味著會在陣列進行swap的操作(交換兩個元素)。

先看一下原本的例子：
[1,2,3,4,5,6,7] and k = 3 -> [5,6,7,1,2,3,4]
先不論其他的部分，我們可以發現5~7從最尾端3個變成最前面的3個了；
與此同時，1~4自然從最前面4個變成最尾端4個。
我們先不論大家的順序，先將整個陣列倒過來的話，
可以先達到1~4，5~7分別占據目標的區塊的效果：[7,6,5,4,3,2,1]。
接著再比對一下，發現區塊是對了，但各自剛好被顛倒過一次，
那麼我們再對7~5及4~1分別各進行一次反轉，就會得到我們要的結果。

所以整個流程就會變成：

1. 將整個陣列進行反轉
2. 將前k個數進行反轉
3. 將後l-k個數進行反轉

反轉是很基本的操作，希望讀者能熟練掌握，
原則上利用two pointer的方式，每次將兩個元素進行交換，
並對pointer位置進行遞增/遞減的操作，直到相交為止。
(例: [1,2,3,4]->[4,2,3,1]->[4,3,2,1])
Java的部分的兩數交換需要宣告一個暫存值tmp(temp)，
Python的部分則可直接使用a, b = b, a的方式進行交換。
最後，操作之前不要忘記將k先取除以l的餘數。

Java:

class Solution {
    public void rotate(int[] nums, int k) {
        if (nums == null || nums.length < 2) return;
        int len = nums.length;
        k = k % len;
        
        reverse(nums, 0, nums.length - k - 1);
        reverse(nums, nums.length - k, nums.length - 1);
        reverse(nums, 0, nums.length - 1);
    }
    
    private void reverse(int[] nums, int i, int j) {
        int tmp = 0;
        while(i < j) {
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
            i++;
            j--;
        }
    }
}

Python:

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        def numReverse(start, end):
            while start < end:
                nums[start], nums[end] = nums[end], nums[start]
                start += 1
                end -= 1
        k, n = k % len(nums), len(nums)
        if k:
            numReverse(0, n - 1)
            numReverse(0, k - 1)
            numReverse(k, n - 1)
'''
# Not in-place solution
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        l = len(nums)
        k %= l
        if k > 0:
            nums[0:l] = nums[-k:] + nums[:-k]
class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        l = len(nums)
        k %= l
        if k > 0:
            nums[:] = (nums + nums)[l-k:l-k+l]
'''

面試實際可能會遇到的問題：
「時間/空間複雜度？」
(O(N), O(1)(如果是使用3次reverse的方法))

「如不限制空間複雜度必須O(1)？」
(可以參照上面Python程式碼中註解的做法)

下篇預告：
0198. House Robber (Easy)