String or Array Rotation

字符串、数组的反转、逆序问题

三步翻转法

将一个字符串分成X和Y两个部分，在每部分字符串上定义反转操作，如X^T，即把X的所有字符反转（如，X="abc"，那么X^T="cba"），那么就得到下面的结论：(X^TY^T)^T=YX，显然就解决了字符串的反转问题。

例如，字符串 "abcdef" ，若要让"def"翻转到"abc"的前头，只要按照下述3个步骤操作即可：

1. 首先将原字符串分为两个部分，即X: "abc"，Y: "def"；

2. 将X反转，X -> X^T，即得：abc -> cba；将Y反转，Y -> Y^T，即得：def -> fed。

3. 反转上述步骤得到的结果字符串X^TY^T，即反转字符串cbafed的两部分（cba和fed）给予反转，cbafed得到defabc，形式化表示为(X^TY^T)^T=YX，这就实现了整个反转。

https://segmentfault.com/a/1190000002694646

https://blog.csdn.net/u010016196/article/details/45126853

Array Rotate Template

// 3-step reverse - O(n) time, O(1) space
class Solution {
    public void rotateRight(int[] nums, int k) {
        int n = nums.length;
        k = k % n; 
        reverse(nums, 0, n - k - 1);
        reverse(nums, n - k, n - 1);
        reverse(nums, 0, n - 1);
    }
    public void rotateLeft(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n - k - 1);
        reverse(nums, n - k, n - 1);
        reverse(nums, 0, n - 1);
    }
    private void reverse(int[] nums, int s, int t) {
        while (s < t) {
            int tmp = nums[s];
            nums[s] = nums[t];
            nums[t] = tmp;
            s++;
            t--;
        }
    }
}

相关问题：

Rotate Array - Solution