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

function move(&$str , $n){
    for ($i = 0; $i<$n; $i++){
        LeftShiftOne($str);
    }
}

function LeftShiftOne(&$str){
    $len = strlen($str);
    $last = $str[$len - 1];
    for ($i = 0; $i<$len-1; $i++){
        $str[$i - 1] =$str[$i];
    }
    $str[$len-2] = $last;
}
$str = "abcd";
move($str, 4);

时间复杂度为O(m n)，空间复杂度为O(1),空间复杂度符合题目要求，但时间复杂度不符合，所以，我们得需要寻找其他更好的办法来降低时间复杂度。 ###解法二：三步反转法 对于这个问题，换一个角度思考一下。 将一个字符串分成X和Y两个部分，在每部分字符串上定义反转操作，如X^T，即把X的所有字符反转（如，X="abc"，那么X^T="cba"），那么就得到下面的结论：(X^TY^T)^T=YX，显然就解决了字符串的反转问题。 例如，字符串 abcdef ，若要让def翻转到abc的前头，只要按照下述3个步骤操作即可：

• 首先将原字符串分为两个部分，即X:abc，Y:def；
• 将X反转，X->X^T，即得：abc->cba；将Y反转，Y->Y^T，即得：def->fed。
• 反转上述步骤得到的结果字符串X^TY^T，即反转字符串cbafed的两部分（cba和fed）给予反转，cbafed得到defabc，形式化表示为(X^TY^T)^T=YX，这就实现了整个反转。

/**
 * 旋转字符串
 * @param $str
 * @param $start
 * @param $end
 */
function ReverseString(&$str, $start, $end){
    while($start < $end){
        $t = $str[$start];
        $str[$start++] = $str[$end];
        $str[$end--] = $t;
    }
}


/**
 * @param $str
 * @param $n 字符串长度
 * @param $m 移动位数
 */
function LeftRotateString(&$str, $n, $m){
    $m %= $n;
    ReverseString($str, 0, $m-1);
    ReverseString($str, $m, $n-1);
    ReverseString($str, 0, $n-1);

}

$str = "abcd";
LeftRotateString($str, strlen($str), 1);

这就是把字符串分为两个部分，先各自反转再整体反转的方法，时间复杂度为O(n)，空间复杂度为O(1)，达到了题目的要求。