字符串的旋转(《编程之法:面试和算法心得》)

时间:2021-03-18 16:45:24
题目:给定一个字符串,要求将字符串前面的若干个字符移动到字符串的尾部。比如:将字符串 “ 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 字符串的旋转
 
 
(完)