[日常] 算法-旋转字符串-三步翻转法
程序员文章站
2022-03-26 14:05:04
题目描述 给定一个字符串,要求把字符串前面的若干个字符移动到字符串的尾部,如把字符串“abcdef”前面的2个字符'a'和'b'移动到字符串的尾部,使得原字符串变成字符串“cdefab”。请写一个函数完成此功能,要求对长度为n的字符串操作的时间复杂度为 O(n),空间复杂度为 O(1)。 分析与解法 ......
题目描述
给定一个字符串,要求把字符串前面的若干个字符移动到字符串的尾部,如把字符串“abcdef”前面的2个字符'a'和'b'移动到字符串的尾部,使得原字符串变成字符串“cdefab”。请写一个函数完成此功能,要求对长度为n的字符串操作的时间复杂度为 O(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,这就实现了整个反转。
c语言版:
#include <stdio.h> #include <string.h> 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。 } int main(){ char a[]="hello world"; LeftRotateString(a,strlen(a),2); printf("%s\n",a); }
go语言版:
package main import( "fmt" ) func ReverseString(s []byte,from int,to int){ for{ t:=s[from] s[from]=s[to] s[to]=t from++ to-- if from>to{ break } } } func LeftRotateString(s []byte,n int,m int){ m%=n ReverseString(s,0,m-1) ReverseString(s,m,n-1) ReverseString(s,0,n-1) } func main(){ a:=[]byte("hello world") LeftRotateString(a,len(a),2) fmt.Println(string(a)) }
php版:
<?php function ReverseString(&$str,$from,$to){ while($from<$to){ $t=$str[$from]; $str[$from++]=$str[$to]; $str[$to--]=$t; } } function LeftRotateString(&$str,$n,$m){ $m%=$n;//如果转换前几个字符的长度比字符串长度大 ReverseString($str,0,$m-1); ReverseString($str,$m,$n-1); ReverseString($str,0,$n-1); } $a="hello world"; LeftRotateString($a,strlen($a),2); echo $a."\n";
上一篇: 玩游戏 学Flex布局
下一篇: 前端HTML基础知识学什么?