旋转问题

leetcode上有一系列的，旋转相关的题目，旋转字符串，旋转链表，旋转数组等等.

这篇文章中，我们来逐个解决这些问题。

其实考察的知识点不相同，本不该放在同一篇文章中汇总说明，主要还是考虑到都包含 旋转 就给它归一啦。

剑指 Offer 58 - II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab”。

示例 1：

输入: s = “abcdefg”, k = 2 输出: “cdefgab” 示例 2：

输入: s = “lrloseumgh”, k = 6 输出: “umghlrlose”

限制：

1 <= k < s.length <= 10000

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

思路一：

  • substring 切割
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// 直接用 substring 切割字符串
public String reverseLeftWords(String s, int n) {
    if (n == 0 || s == null || s.length() == 0) return s;

    StringBuilder sb = new StringBuilder();
    sb.append(s.substring(n, s.length()));
    sb.append(s.substring(0, n));

    return sb.toString();
}

思路二

  • 使用新的存储空间存储 最终结果字串

  • 遍历字符串, 从 k 处开始拼接字符

  • 到头时，拼接 开头字符 (此操作用 取余 实现)

代码如下 :
1
2
3
4
5
6
7
8

    public String reverseLeftWords(String s, int n) {
        if (n == 0 || s == null || s.length() == 0) return s;
        
        StringBuilder res = new StringBuilder();
        for(int i = n; i < s.length() + n; i++)
            res.append(s.charAt(i % s.length()));
        return res.toString();
    }
复杂度分析 :

时间复杂度 : O(N) 遍历了一整遍字符串

空间复杂度 : O(N) 使用了额外的字符串存储最终结果

思路三：

  • 字符串转为字符数组
  • 先整体反转字符数组
  • 再分别反转字符数组的 [0, chars.length - n - 1], [chars.length - n, chars.length - 1]
代码如下 :
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public static String reverseLeftWords(String s, int n){
        n %= s.length();
        char[] chars = s.toCharArray();
        chars = reverse(chars, 0, chars.length - 1);
        chars = reverse(chars, 0, chars.length - n - 1);
        chars = reverse(chars, chars.length - n, chars.length - 1);
        
        StringBuilder sb = new StringBuilder();
        sb.append(chars, 0, chars.length);

        return sb.toString();
    }

    public static char[] reverse(char[] chars, int left ,int right){
        while (left < right){
            char tmp = chars[left];
            chars[left] = chars[right];
            chars[right] = tmp;
            left ++;
            right --;
        }
        return chars;
    }

189. 旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,3,4,5,6] 向右旋转 2 步: [6,7,1,2,3,4,5] 向右旋转 3 步: [5,6,7,1,2,3,4] 示例 2:

输入: [-1,-100,3,99] 和 k = 2 输出: [3,99,-1,-100] 解释: 向右旋转 1 步: [99,-1,-100,3] 向右旋转 2 步: [3,99,-1,-100] 说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。 要求使用空间复杂度为 O(1) 的 原地 算法。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/rotate-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

思路一：

  • 分步旋转
  • 一位一位旋转字符，直到旋转 k 次
  • 时间复杂度 : O(N * K)
  • 空间复杂度 : O(1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// 方法1 分步旋转
// 时间复杂度 O(N * K)
// 空间复杂度 O(1)
public void rotate1(int[] nums, int k) {
    k = k % nums.length;

    for (int i = 0; i < k; i++) {
        int tmp = nums[nums.length - 1];
        for (int j = nums.length - 1; j > 0; j--) {
            nums[j] = nums[j - 1];
        }

        nums[0] = tmp;
    }
}

截屏2020-06-22下午12.02.40

  • 算法提交后，虽然ac了，但是可以看出，耗时特别长。 时间复杂度为 O(N * K)
  • 然而，我们貌似完全没必要，一位一位旋转。
  • 下边方法我们对时间复杂度进行优化

思路二：

  • 备份 k 个元素
  • 遍历赋值
 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

// 方法2
// 备份 k 个元素
// 时间复杂度 O(N)
// 空间复杂度 O(K)
public void rotate(int[] nums, int k) {
    if (nums == null || nums.length == 0 || k == 0) return;
    if (nums.length < k) {
        // 保证 k < 数组长度
        rotate(nums, k % nums.length);
        return;
    }

    // 备份 k个元素
    int[] tmp = new int[k];
    for (int i = nums.length - k; i < nums.length; i++) {
        tmp[i + k - nums.length] = nums[i];
    }

    for (int i = nums.length - 1; i >= k; i--) {
        nums[i] = nums[i - k];
    }

    for (int i = 0; i < k; i++) {
        nums[i] = tmp[i];
    }
}

截屏2020-06-22下午12.06.22

复杂度分析 :

时间复杂度 : O(N)

空间复杂度 : O(K)

  • 可以看出， 此算法在执行耗时上优秀很多了。
  • 但是，依然有优化的空间， 因为题目要求我们使用使用原地算法
    • 即时间复杂度 O(1)
  • 接下来，我们尝试将空间复杂度优化至 O(1)

思路三:

  • 跟我们上一题，字符数组操作一致
  • 先将数组整体旋转
  • 再将数组 (0, k) 反转
  • 再将数组 (k + 1, nums.length - 1)反转
 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

// 方法3
// 整体反转 数组
// 再分别反转 前k个 和 后 N-k个
public void rotate2(int[] nums, int k) {
    if (nums == null || nums.length == 0 || k == 0) return;
    if (nums.length < k) {
        // 保证 k < 数组长度
        rotate2(nums, k % nums.length);
        return;
    }

    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k);
    reverse(nums, k+1, nums.length - 1);
}

public void reverse(int[] nums, int left, int right){
    while (left < right){
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;

        left ++;
        right --;
    }
}

截屏2020-06-22下午12.11.42

复杂服分析:

  • 时间复杂度 : O(N)

  • 空间复杂度 : O(1)

尴尬的是，经过我们这一步优化，执行耗时 和 内存消耗均上升了…

  • 时间消耗上升，还能理解， 毕竟从一轮遍历的 O(N)改为 两轮遍历的 O(N)
  • 内存消耗上升，就不能理解了。思路二中，我们使用了额外的 k 个数组存储空间， 而此方法中，我们没有使用额外的存储空间。反而上升了.
  • 神奇的 leetcode.

61. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL 示例 2:

输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/rotate-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

  • 先遍历链表，找到链表的总长度size 并记录 链表最后一个节点lastNode
  • 计算有效旋转的数量
    • k %= size
  • 如果有效旋转为0， 则直接返回 head
  • 有效旋转不为0， 则进行以下操作
    • 快慢指针，找到链表的倒数第 k 个节点的 前驱节点slow
    • 使用 newHead 保存 新的头节点，也就是 倒数第 k 个节点
    • 前驱节点 slow.next = null
    • 最后一个节点 lastNode.next 指向 头节点 head
    • 最后返回 newHead 即可
纸上图解算法执行流程

2541592817409_.pic

 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
33
34
35
36
37
38
39
40

public static ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null || k == 0) return head;

    // 找到链表总长度
    // 同时找到链表的最后一个节点
    ListNode n = head;
    int size = 0;
    ListNode lastNode = null;
    while (n != null){
        lastNode = n;
        n = n.next;
        size ++;
    }

    // 有效旋转的数量
    k %= size;
    // 如果有效旋转为0， 则直接return head
    if (k == 0) return head;

    // 找到链表的 旋转的前一个节点
    ListNode slow = head;
    ListNode fast = head;
    int i = 0;
    while (fast != null){
        fast = fast.next;
        if (i ++ >= k + 1){
            slow = slow.next;
        }
    }

    // newHead 保存 新头节点
    ListNode newHead = slow.next;
    // 旋转前一个节点 置空
    slow.next = null;

    // 最后一个节点 指向头节点
    lastNode.next = head;

    return newHead;
}