一道字符串翻转题

算法类 80

在网上看到了一道C语言的题，采用了三步翻转法实现 

给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcde”前面的2个字符'a'和'b'移动到字符串的尾部，使得原字符串变成字符串“cdeab”。请写一个函数完成此功能，要求对长度为n的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。

三步翻转法：

把一个字符串分成X，Y两部分，先把X部分翻转，再把Y部分翻转，最后再把XY一起翻转；比如"abcde"分成"ab"，"cde"两部分，"ab"部分翻转为"bc"，"cde"翻转为"edc"
 两部分合在一起为"baedc"再翻转一次，变为"cdeab"。 

void ReverseString(char* s,int from,int to)
{
    while (from < to)
    {
        char t = s[from];
        s[from++] = s[to];
        s[to--] = t;
    }
}

void LeftRotateString(char* s,int n,int m)
{
    m %= n;               //若要左移动大于n位，那么和%n 是等价的
    ReverseString(s, 0, m - 1); //反转[0..m - 1]，套用到上面举的例子中，就是X->X^T，即 abc->cba
    ReverseString(s, m, n - 1); //反转[m..n - 1]，例如Y->Y^T，即 def->fed
    ReverseString(s, 0, n - 1); //反转[0..n - 1]，即如整个反转，(X^TY^T)^T=YX，即 cbafed->defabc。
}

实际上，用js实现起来不需要用这个思路，直接用 sclie()剪出来在拼接会方便很多。 

var str = "abcde";
var str1 = str.slice(0, 2);
var str2 = str.slice(2);
var newStr = str2 + str1;

alert(newStr);   //cdeab

但是因为心情好，还是照着写了 js 实现的版本 

var string = "abcde"

function reverseString(str,from, to){
    str = string;
    splitStr = str.split("");

    while(from < to){                  //翻转
        var temp = splitStr[from];
        splitStr[from++] = splitStr[to]
        splitStr[to--] = temp;

    }
    string = splitStr.toString();
    string = string.replace(/,/g, ""); // 去掉字符串中的逗号 
}

function leftRotateString(str, n ,m){   //字符串长度为n，要把m个字符移动到末尾
    m %= n;   //确保 m < n

    reverseString(str, 0, m - 1); //套用在例子中就是 ab->ba
    reverseString(str, m, n - 1); //cdef->fedc
    reverseString(str, 0, n - 1); //cbafed->defabc。

    return string;
}

alert(leftRotateString(string, 5, 2)) // "cdeab"
Comments
Write a Comment