[日常] 算法-旋转字符串-三步翻转法
2018-06-18 03:47:01来源:未知 阅读 ()
题目描述
给定一个字符串,要求把字符串前面的若干个字符移动到字符串的尾部,如把字符串“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";
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:数组指针
下一篇:MFC 程序退出方法
- C++ rand函数 2020-06-10
- OpenCV开发笔记(五十九):红胖子8分钟带你深入了解分水岭 2020-05-24
- 类欧几里得算法 2020-05-16
- 算法笔记刷题6 ( PAT 1003我要通过 ) 2020-05-08
- 无法正确通过算法题目都是哪些原因造成的? 2020-04-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash