文科生都能看懂的循环移位算法

  • 2019 年 10 月 7 日
  • 筆記

循环移位问题真的是一个特别经典的问题了，今天我们就来攻克它。

循环移位的表现形式有很多种，就数据结构来说包括数组，字符串，链表等。就算法来说，有包含问题，直接移动问题，还有查找问题等。

虽然表现形式有很多，但是本质都是一样的，因为从逻辑上来讲其实他们都是线性数据结构，那么让我们来看一下吧。

数组循环移位

LeetCode 和 编程之美等都有这道题目，题目难度为Easy。LeeCode链接[1]

题目描述

给定一个数组，将数组中的元素向右移动 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) 的 原地 算法。

不符合题意的解法

如果你拿到这道题没有思路，不要紧张，因为你不是一个人。

让我们先不要管题目的时间和空间复杂度的限制， 来用最最普通的方式实现它，看能不能得出一点思路。

最简单的做法就是新开辟一个完全一样的数组，然后每次移动的时候从 copy 的数组中取即可，由于新开辟的数组不会被改变，因此这种做法可行，我们直接看下代码：

function RShift(list, k) {    // 空间复杂度O(n)    // 时间复杂度O(n)    const copy = [...list];    const n = list.length;      for (let i = 0; i < n; i++) {      list[i] = copy[(k + i) % n];    }    return list;  }

实际上我们还可以优化一下，如果 k 是 N 的倍数，实际上是不需要做任何移动的，因此直接返回即可。

function RShift(list, k) {    const n = list.length;    if (k % n === 0) return;    // 剩下代码  }

由于我们需要覆盖原来的数组，那么原来的数组中的数据就会缺失，因此我们最简单的就是开辟一个 完全一样的数组，这样就避免了问题，但是这样的空间复杂度是 N。我们有没有办法优化这个过程呢？

而且如果 k 是负数呢？这其实在考察我们思考问题的严谨性。

除此之外，我们还应该思考：

  • k 的范围是多少？如果很大，我的算法还有效么？
  • n 的范围是多少？如果很大，我的算法还有效么?

上面两个问题的答案都是有效。因为 k 就算再大，我们只需要求模，求模的值当成新的 k 即可。因此 k 最大不过就是 n。如果 n 很大，由于我们的算法是 O(N)的复杂度，也就是线性，这个复杂度还是比较理想的。

空间换时间

我们来试一下常数空间复杂度的解法，这种做法思路很简单，我们只需要每次移动一位，移动 k 次即可，移动一次的时间复杂度是 1，k 次公用一个变量即可，因此总的时间复杂度可以降低到 1。

我们来看下代码，这次我们把上面提到的 k 为负数的情况考虑进去。

function RShift(list, k) {    const n = list.length;    if (k % n === 0) return;      let cnt = Math.abs(k > 0 ? k % n : n + (k % n));    let t = null;      while (cnt--) {      t = list[n - 1];      // 右移一位      for (let i = n - 1; i > 0; i--) {        list[i] = list[i - 1];      }      list[0] = t;    }      return list;  }

虽然上面的解法是常数空间复杂度，但是时间复杂度是 O(N * K)，K 取值不限制的话，就是 O(N^2)， 还是不满足题意。不过没关系，我们继续思考。

我们再来看一种空间换时间的做法，这种做法的思路是拼接一个完全一样的数据到当前数据的尾部，然后问题就转化为截取数组使之满足右移的效果，这样的时间复杂度 O(N),空间复杂度是 O(N).

我们看下代码：

function RShift(list, k) {    const n = list.length;    let i = Math.abs(k > 0 ? k % n : n + (k % n));    return list.concat([...list]).slice(n - i, n * 2 - i);  }

哈哈，虽然离题目越来越远了，但是扩展了思路，也不错，这就是刷题的乐趣。

三次翻转法

我们来看下另外一种方法 – 经典的三次翻转法，我们可以这么做：

  • 先把[0, n – k – 1]翻转
  • 然后把[n – k, n – 1]翻转
  • 最后把[0, n – 1]翻转
function reverse(list, start, end) {    let t = null;      while (start < end) {      t = list[start];      list[start] = list[end];      list[end] = t;      start++;      end--;    }  }  function RShift(list, k) {    const n = list.length;    if (k % n === 0) return;    reverse(list, 0, n - k - 1);    reverse(list, n - k, n - 1);    reverse(list, 0, n - 1);    return list;  }

这里给一个简单的数学证明：

  • 对于[0, n – k – 1] 部分，我们翻转一次后新的坐标y和之前的坐标x的关系可以表示为y = n - 1 - k - x
  • 对于[n – k, n -1] 部分，我们翻转一次后新的坐标y和之前的坐标x的关系可以表示为y = 2 * n - 1 - k - x
  • 最后我们整体进行翻转的时候，新的坐标y和之前的坐标x的关系可以表示为
    1. y = n - 1 - (n - 1 - k - x) 即 y = k + x (0 <= x <= n – k – 1)
    2. y = n - 1 - (2 * n - 1 - k - x) 即 y = k + x - n (n – k <= x <= n – 1)

正好满足我们的位移条件。

这种做法时间复杂度是 O(N)空间复杂度 O(1)，终于满足了我们的要求。

字符串循环移位

字符串和数组真的是一模一样，因为字符串也可以看成是字符序列，因此字符串就是数组。本质上来说，它和数组循环移位题目没有任何区别， 现在让我们来通过一道题来感受下。

题目描述

给定两个字符串 s1 和 s2，要求判定 s2 是否能被 s1 循环移位得到的字符串包含。比如，给定 s1 = AABCD 和 s2 = CDAA，返回 true 。给定 s1 = ABCD，s2 = ACBD， 则返回 false。

题目来自《编程之美》

暴力法

s1 我们每次移动一位，然后判断逐一判断以每一个位置开头的字符串是否包含 s2，如果包含则返回 true，否则继续匹配。

这种做法很暴力，时间复杂度 O(n^2)，在 n 特别大的时候不是很有效。

代码如下：

function RIncludes(s1, s2) {    const n = s1.length;    const m = s2.length;    let t = null;    let p1; // s1的指针    let p2; // s2的指针    for (let i = 0; i < n; i++) {      t = s1[0];      for (let j = 0; j < n - 1; j++) {        s1[j] = s1[j + 1];      }      s1[n - 1] = t;      p1 = 0;      p2 = 0;      while (p1 < n && p2 < m) {        if (s1[p1] === s2[p2]) {          p1++;          p2++;        } else break;      }        if (p2 === m) return true;    }      return false;  }

巧用模运算

另外一种方法就是上面那种空间换时间的方式，我们将两个 s1 连接到一起，然后直接双指针即可，这里不再赘述。

这种方法虽然巧妙，但是我们花费了额外的 N 的空间，能否不借助额外的空间呢？答案是可以的，我们可以假想已经存在了另外一个相同的 s1，并且我们将它连接到 s1 的末尾。注意这里是假想，实际不存在，因此时间复杂度是 O(1)。那么如何实现呢？

答案还是利用求模。

function RIncludes(s1, s2) {    const n = s1.length;    const m = s2.length;    let t = null;    let p1; // s1的指针    let p2; // s2的指针    for (let i = 0; i < n; i++) {      p1 = i; // 这一行代码变了      p2 = 0;      while (p1 < 2 * n && p2 < m) {        // 不需要循环移动一位了，也就是说省了一个N的循环        if (s1[p1 % n] === s2[p2]) {          // 这一行代码变了          p1++;          p2++;        } else break;      }        if (p2 === m) return true;    }      return false;  }

至此，这道题就告一段落了，大家如果有别的方法，也欢迎在评论区留言。

链表循环移位

链表不同于前面的数组和字符串，我们来个题目感受一下。

这里出一个 LeetCode 题目，官方难度为中等难度的一个题 – 61. 旋转链表[2]

题目描述

给定一个链表，旋转链表，将链表每个节点向右移动 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

思路

其实这个思路简单，就是先找到断点，然后重新拼接链表即可。这个断点其实就是第n - k % n个节点， 其中 k 为右移的位数，n 为链表长度。这里取模的原因和上面一样，为了防止 k 过大做的无谓运算。但是这道题目限定了 k 是非负数，那么我们就不需要做这个判断了。

如图所示：

代码也很简单，我们来看下。

代码

var rotateRight = function(head, k) {    if (head === null || head.next === null) return head;    const dummy = {      next: head,    };    let p1 = dummy;    let n = 0;      while (p1 && p1.next) {      p1 = p1.next;      n++;    }    let cur = 0;    let p2 = dummy;      while (cur < n - (k % n)) {      p2 = p2.next;      cur++;    }    p1.next = dummy.next;    dummy.next = p2.next;    p2.next = null;      return dummy.next;  };

扩展

  • 循环移位的有序数组，查找某一个值，要求时间复杂度为 O(logn) 这道题我在《每日一题》[3]出过

参考资料

[1]

LeeCode链接: https://leetcode-cn.com/problems/rotate-array/

[2]

61. 旋转链表: https://leetcode-cn.com/problems/rotate-list/

[3]

《每日一题》: https://github.com/azl397985856/fe-interview/blob/master/docs/topics/algorthimn/cycle-sorted-array.md

VirMach 便宜 VPS

QNews

QNews