字符串的旋转（《编程之法：面试和算法心得》）

题目：给定一个字符串，要求将字符串前面的若干个字符移动到字符串的尾部。比如：将字符串 “ abcdef” 的前 3 个字符进行移动，得到“def abc”。写一个函数实现此功能。

一、我的思路

1. 把这个字符串看成两个部分，“abc” 和 “def”。

2. 用 “def” 加上 “abc” 就得到题目的答案。

下面是思路的代码实现：

var MoP = {};
    
// Definition
function stringReverse(str, pos) {
    var temp_str = str.substring(0, pos);
    return str.substring(pos) + temp_str;
}
    
// Assignment
MoP.stringReverse = stringReverse;
    
// Print
MoP.stringReverse('abcdef', 3) // "defabc"

stringReverse 函数接收两个参数：第一个 str，表示给定的一个字符串；第二个 pos，表示将字符串的前 pos 个字符进行移动。

二、July 的解法

July 给出的两种解法：

1. 蛮力解法：将需要移动的字符一个一个地移动到字符串的尾部。

2. 三步反转：把字符串看成两部分，“abc” 和 “def”，分别对它们进行反转，得到 “cba” 和 “fed”，再将 “cbafed” 整体进行反转，就得到 “defabc”这个要求的结果了。

对于上面的两种解法，我与 July 就一个“把字符串看成是两部分”的思路是一致的，其他的都没想到。

July 提供的两种解法，是基于 C 语言代码实现的，是把给出的字符串当成数组来进行处理。下面为了方便我学习，我用 JavaScript 代码进行改写，加深我的印象。

解答一的代码：

function leftShiftOne(arrObj) {
    var temp = arrObj[0];
    
    var i, len = arrObj.length;
    for (i = 1; i < len; i++) { 
        arrObj[i-1] = arrObj[i];
    }
    arrObj[len-1] = temp; 
    // after one step: ["a", "b", "c", "d", "e", "f"] => ["b", "c", "d", "e", "f","a"]
}

function leftRotateString(arrObj, pos) {
    while (pos--) {
        leftShiftOne(arrObj);
    }
}

var arr1 = ["a", "b", "c", "d", "e", "f"];
leftRotateString(arr1, 3);
arr1 // ["d", "e", "f", "a", "b", "c"]

解答二的代码：

var UTIL = {};    
    
function reverseString(arrObj, from, to) {
    while (from < to) {
        var t = arrObj[from];
        arrObj[from++] = arrObj[to];
        arrObj[to--] = t;
    }
}

UTIL.rS = reverseString;

function leftRotateString(arrObj, startPos) {
    var len = arrObj.length;
    UTIL.rS(arrObj, 0, startPos - 1);
    UTIL.rS(arrObj, startPos, len - 1);
    UTIL.rS(arrObj, 0, len - 1);
}    

var arr2 = ["a", "b", "c", "d", "e", "f"];
leftRotateString(arr2, 3);
arr2 // ["d", "e", "f", "a", "b", "c"]

三、练习

将一个英文句子，比如 “I am a student.” 进行反转，得到 “student. a am I”。也就是说句子里的单词反转了，但是单词里的字母顺序不变。(注：单词间以空格隔开，标点符号跟字母一样处理)

分析：单词字母顺序没变，整个句子反转 1 次。

下面是代码的实现：

"I am a student.".split(" ").reverse().join(" ") // "student. a am I"

在这里使用了 ECMAScript 标准提供的几个方法，分别是：split、reverse、join 。字符串 “I am a student.” 发生了下面的事情：

1）. 以 “ ”（空格）为分隔符，处理成数组 ["I", "am", "a", "student."] ；

2）. 数组里元素进行了反转处理，变成了 ["student.", "a", "am", "I"] ；

3）. 将数组 ["student.", "a", "am", "I"] 里的元素依序以 “ ” 为连接符连接成字符串；

4）. 得到结果。

四、参考资料

1. 《编程之法：面试和算法心得》（人民邮电出版社，2015） 1.1 字符串的旋转

（完）

秒客网

字符串的旋转（《编程之法：面试和算法心得》）

相关文章