by addy 原创文章,欢迎转载,但希望全文转载,注明本文地址。

本文地址:https://www.iamaddy.net/2017/08/string-reversal-algorithm/

最近在翻阅《编程珠玑》第二版,真的是字字珠玑。在看到第二章的“啊哈,算法”的一道题目,将字符串反转。将一个具有n个元素的一维向量x向左旋转i个位置。例如,将 abcdefg 向左旋转 3 个位置之后得到 defgabc。要求是花费与n成比例的时间以及尽可能少的空间来完成这个操作。看到此题后的第一想法就是临时数组,下面来看下具体代码:

临时数组法

使用js原生splice与concat方法,可减少大量代码:

var arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
function swap1 (arr, x) { 
    return arr.splice(x).concat(arr);
}
console.log(swap1(arr, 4));

不用javascript原生的方法:

var arr2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
function swap2(arr, x) {
    var temp = [],
    len = arr.length;
    for (var i = 0; i < x; i++) {
        temp[i] = arr[i];
    }
    for (var i = x; i < len; i++) {
        arr[i - x] = arr[i];
    }
    for (var i = 0; i < x; i++) {
        arr[len - x + i] = temp[i];
    }
    return arr;
}
console.log(swap2(arr2, 4));

这种方法大多数人都能够想得到,这是最普通的方法,但比较浪费空间。接下来在看一个也比较普通的方法,不使用临时数组。

元素移位

var arr3 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
function swap3(arr, x) {
    var temp,
    len = arr.length;
    for (var i = 0; i < x; i++) {
        temp = arr[0];
        for (var j = 0; j < len - 1; j++) {
            arr[j] = arr[j + 1];
        }
        arr[j] = temp;
    }
    return arr;
}
console.log(swap3(arr3, 4));

程序的实现原理也很简单,将第一位元素往后移动,而其他元素向前移动。虽然不浪费空间,但如果x比较大的话,花费的时间成本就比较高了。

机智的反转

下面来看作者给出的一个比较机智的方法,真的是灵光一闪的感觉。原问题可以理解为这样:将原数组看成 ab,需要转换成 ba,先单独对子数组a进行反转得到a’b(a’表示a反转后的结果),同理单独反转b,得到 a’b’,最后将得到的 a’b’ 一起进行一次反转可得 (a’b’)’,而这就是最终结果 ba了。还有一个很形象的图来说明:

字符串反转算法

你可以用自己的双手照着图反转着试一下,看看结果是不是正确的。下面给出这种反转的代码:

// 反转函数 1234 => 4321
function reverse(arr, start, end) {
    var temp,
        len = arr.length, 
        mid = Math.floor((start + end) / 2);
    for (var i = start; i < mid; i++) {
        temp = arr[end - i - 1 + start];
        arr[end - i - 1 + start] = arr[i];
        arr[i] = temp;
    }
};
function swap4(arr, x) {
    reverse(arr, 0, x);
    reverse(arr, x, arr.length);
    reverse(arr, 0, arr.length);
    return arr;
}

性能对比

jsper的测试结果:http://jsperf.com/reversea

字符串反转算法

字符串反转算法

从上面的数据看来单位时间内,swap4的性能最好了(果然机智),用js原生的方法则最差,比最快的慢了80%多。swap2在执行上也很快,但多用了一块空间来存放待偏移的temp字符,以空间换时间。swap3性能一般,比较依赖于x的位置,x的位置越靠后,需要花费的时间会越长。

还有一种巧妙的方法

巧妙的杂技表演

先将x[0]移到临时变量t中,再把x[i]移到x[0]腾出来的位置中,x[2i]移到x[i]中,以此类推(每一次移动时将x[]中的下标对其长度n取模),直到又回到从x[0]提取元素,此时应该把临时变量t放入到上一个位置中,并开始下一次迭代,即对x1进行类似的操作。找来书中直观的图如下:

字符串反转算法

代码如下:

function reverse(arr, m){
   var k = 0; 
   for(var i = 0; i < m; i++){ 
      k = 1;  //每次迭代都从1倍位移开始 
      var temp = arr[i]; 
      while(( k * m + i) % arr.length !== i){ 
          arr[( k - 1 ) * m + i] = arr[k * m + i]; 
          k++; 
      } 
      arr[(k - 1) * m + i] = temp; 
   } 
} 

但这种方法有限制性,如果数组的长度不能整除m,则无法正常的运行。

本文为原创文章,可能会经常更新知识点以及修正一些错误,因此转载请保留原出处,方便溯源,谢谢合作

本文地址:https://www.iamaddy.net/2017/08/string-reversal-algorithm/

个人知乎,欢迎关注:https://www.zhihu.com/people/iamaddy

欢迎关注公众号【入门游戏开发】 入门游戏开发