String, Array Rotation or Reverse

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

三步翻转法

将一个字符串分成XY两个部分,在每部分字符串上定义反转操作,如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的两部分(cbafed)给予反转,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

results matching ""

    No results matching ""