面试算法题之旋转置换，旋转跳跃我闭着眼

轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

借用临时数组

我们可以新建一个临时数组，用于存储旋转后的元素。首先获取数组的长度n，并计算k%n将k值限制在数组nums长度范围内，避免不必要的旋转。创建一个临时数组ans，在第一个循环中，从位置n-k开始，将nums向量中的元素逐个添加到ans向量中。在第二个循环中，从位置 0 开始，将 nums 向量中的元素逐个添加到 ans 向量中。执行完两个循环后就得到了旋转后的数组，但题意需要通过参数nums传递结果，所以通过最后一个循环将数组ans中的元素逐个复制回数组nums中。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        vector<int> ans;
        for(int i=n-k;i<n;i++) {
            ans.push_back(nums[i]);
        }
        for(int i=0;i<n-k;i++) {
            ans.push_back(nums[i]);
        }
        for(int i=0;i<n;i++) {
            nums[i] = ans[i];
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度为 O(n)，空间复杂度为 O(n)。

多次翻转数组

实际上我们将数组旋转后，最终结果是将末尾$k$位数移动至数组开头，部分数组元素排序并没有改变。那么如何可以快速将末尾元素调换至数组开头呢？

如nums = [1,2,3,4,5,6,7,8], k = 2, n = 8，数组旋转后得到[7,8,1,2,3,4,5,6]。

我们先将整个数组翻转，得到[8,7,6,5,4,3,2,1]，这样末尾元素就移动到了数组开头，但元素顺序改变了。这时，我们将数组前$k$位分为一组，其余元素为另一组。分别对这两组执行一次数组翻转，这样元素顺序也就调转回来了，得到结果[7,8,1,2,3,4,5,6]。

class Solution {
public:
    void reverse(vector<int>& nums, int s, int e) {
        while(s < e) {
            swap(nums[s++], nums[e--]);
        }
    }
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        reverse(nums, 0, n-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, n-1);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度为 O(n)，空间复杂度为 O(1)。

分组循环

在上述使用临时数组方案中，临时数组是为了避免替换位置的元素被覆盖。当然，我们也可以使用一个临时变量去记录。

我们假设将数组分为cnt组，每个组的大小为n/cnt。这里分组数cnt计算如下：

假设从起点开始到最终回到起点共经历m个元素，恰好走了t圈，那么有$tn=mk$，由于是第一次返回到起点，则$t$一定要小，即为$m、k$的最小公倍数$lcm(n,k)$。得到$m=\frac{lcm(n,k)}{k}$，即一组遍历会经过$m$个元素。那么有$cnt=\frac{n}{m}=\frac{nk}{lcm(n,k)}=gcd(n,k)$，其中$lcm$表示最小公倍数，$gcd$表示最大公约数。

第一组从位置 0 开始，tmp = nums[0]，根据题意，位置 0 的元素会被置于$j=(0+k)\mathrm{mod}n$的位置，交换tmp和nums[j]，此时tmp已经更新，即被替换的j位置的原元素。之后，再观察j位置，交换tmp和nums[(j+k)%n]，再次更新了tmp。如此依次处理数组内的元素，直至回到初始位置 0。

接下来每组亦是如此依次处理数组内的元素，直至回到初始位置 0。

如nums = [1,2,3,4,5,6,7,8], k = 2, n = 8，如此计算k和n的最大公约数为 2
，我们可以将数组分成 2 组，[1,3,5,7]和[2,4,6,8]，变换过程如下图。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        int cnt = gcd(n,k);
        for(int i=0; i<cnt; i++) {
            int curr = i;
            int tmp = nums[i];
            do {
                int j = (curr + k) % n;
                swap(nums[j], tmp);
                curr = j;
            }while(i != curr) ;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度为 O(n)，空间复杂度为 O(1)。

旋转链表

给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

合并成循环链表

旋转链表与旋转数组不同，不经历一次遍历无法确定链表的长度$n$。另一个不同点在于移动一个链表元素不需要整体元素移动。

利用这点特性，我们可以先将链表合并成环，并在链表的$n-(k\mathrm{mod}n)$处断开，如此就可以得到旋转后的链表。具体如何操作呢？

我们先定义一个迭代指针p，用于遍历链表记录链表长度$n$，此时p指针正指向链表尾部元素，并将链表头尾连接。

知道链表长度$n$后，由此就可以得到需要再向前移动p指针的步数$cnt=n-(k\mathrm{mod}n)$，再移动p指针$cnt$步，此时p指针正指向旋转后链表的尾部元素，定义ans记录新链表的头部元素，再断开链表就完成链表的旋转啦。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(k==0 || head==nullptr || head->next==nullptr)
            return head;
        int n = 1;
        ListNode* p = head;
        while(p->next != nullptr) {
            p = p->next;
            n++;
        }
        p->next = head;
        // 需要移动的步数
        int cnt = n - k % n;
        while(cnt-- > 0) {
            p = p->next;
        }
        ListNode* ans = p->next;
        p->next = nullptr;
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

时间复杂度O(n)，空间复杂度O(1)。

旋转字符串

给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。

s 的 旋转操作 就是将 s 最左边的字符移动到最右边。

• 例如, 若 s = 'abcde'，在旋转一次之后结果就是'bcdea' 。

模拟旋转

如果目标字符串goal与s长度不一致，则肯定不会得到目标字符串。

字符串goal与s长度一致时，则采用模拟旋转的方式比较goal中的字符，当i固定时，所有j对应字符都相同，则表示可以由字符串s旋转得到goal；否则，将继续往下进行遍历i。若遍历所有的i任不能使得s旋转为goal，则表明不可以由字符串s旋转得到goal。

class Solution {
public:
    bool rotateString(string s, string goal) {
        int n = s.size(), m = goal.size();
        if(n != m) {
            return false;
        }
        for(int i=0; i<n; i++) {
            bool f = true;
            for(int j=0; j<n; j++) {
                if(s[(i+j) % n] != goal[j]) {
                    f = false;
                    break;
                }
            }
            if(f) {
                return true;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

时间复杂度为O($n^2$)，空间复杂度为O(1)。