程序员编程艺术

所需积分/C币:10 2014-02-10 13:06:34 8.13MB PDF
收藏 收藏
举报

程序员编程艺术
第一章、左旋转字符串 作者:Juy, yansha、 caopengcs 时间:二零一一年四月十四日 题目描述: 定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾 部,如把字符串 abcdef左旋转2位得到字符串 defat。请实现字符串左旋转的 函数,要求对长度为n的字符串操作的时间复杂度为0(n),空间复杂度为0(1) 思路一、暴力移位法 初看此题,咱们最先想到的笨方法可能就是一位一位移动,故咱们写一个函 数叫做1 eftshiftone(char*s,intn)完成左移动一位的功能 void leftshiftone(char *s, int n)t char t=s[0] //保存第一个字符 for (int i = 1; i n; ++i)f 1 s[n-1]=t 如此,左移m位的话,可以如下实现: void leftshift(char *s, int n, int m) while(m--) leftshiftone(s, n); 思路二、指针翻转法 咱们先来看个例子,如下: abc defghi,若要让abc移动至最后的过程可以 RE: abc defghi->def abcghi->def ghiabc 如此,我们可定义俩指针,p1指向ch[0],p2指向chLm] 下过程循环m次,交换p1和p2所指元素,然后p1++,p2++ 1.第一步,交换abc和def, abc defghi-> def abcghi 2.第二步,交换abc和ghi, def abcghi-> def ghiabc 整个过程,看起来,就是abc步一步向后移动 abc defghi def abcghi def ghi abc //最后的复杂度是0(m+n) 图解如下: 第一步:指针处于初始位置,如下所示 p1 b g 第二步:换abc和de,指针p1和p2移动距离π,如下所示 g h 第三步:首先,p1+,p2+,1和2还是相距m然后交换ae和ghi,如下所示 g h i p p 已 吕 h 至此,整个过程结束,得到最终结果 defghi abc. 出上述例子九个元素的序列 abcdefghi,您已经看到,m=3时,p2恰好指到 了数组最后一个元素,于是,上述思路没有问题。但如果上面例子中i的后面 还有元素列? 即,如果是要左旋十个元素的序列: abcdefghij,ak,下面,就举这个例子, 对 abcdefghij序列进行左旋转操作: 如果 abcdef ghij要变成 defghij abc: abcdef gh 1. def abc ghij 2. def ghi abc j //接下来,j步步前移 3. def ghi ab jc 4. def ghi a j bc 5. def ghi j 下面,再针对上述过程,画个图清晰说明下,如下所示 第一步:指针处于初始位置:其叶p指向首地址,p2指向p(本例n为3),如下图所 PAy a 1 第二妙:父换p1刘p2所元紊,循环n次,zbc与ef父换,然后r1+yp2+,如下图 a」。r。。。, 第三步:重复第二步,a与gh交换,然后p1-+存a,p2+,存j 匚def_g:1a 第四步:如果p2+n-1不越界,说明p2到数组尾之间所包含的元素为m,即为上例(指 abcdef zhi,艽个元素)讨论的清况。香则,说明p2到组末尾之间所包含的元素小于m 倮持p1,n不变,将这些元素可左移动n个甲元即可,如下图所示(下图的情况,就是j 前移个亘位,移到abe的前面去,就k了: C defgh i a1 b I def8hijabc 至此,整个过程结宋,得到最终结果 ok,咱们来好好彻底总结一下此思路二:(就4点,请仔细阅读): 1、首先让pl=ch[0],p2=ch[m],即让p1,p2相隔m的距离 2、判断p2+m-1是否越界,如果没有越界转到3,否则转到4( abcdefgh这 8个字母的字符串,以4左旋,那么初始时p2指向e,p2+4越界了,但事实 上p2至p2+m-1是m个字符,可以再做一个交换) 3、不断交换*p1与*2,然后pl++,p2-+,循环m次,然后转到2 4、此时p2+m-1已经越界,在此只需处理尾巴。过程如下: 4.1通过n-p2得到p2与尾部之间元素个数r,即我们要前移的元素个数。 4.2以下过程执行r次:ch[p2]<>ch[p2-1],ch[p2-1]<ch[p2-2], ch[p1+1]<->ch[p1];pl++;p2++ 所以,之前最初的那个左旋转九个元素 abcdefghi的思路在末尾会出现问题 的(如果p2后面有元素就不能这么变,例如,如果是处理|个元素, abode fghij 列?对的,就是这个意思),解决办法有两个 方法一(即如上述思路总结所述): def ghi abc jk 当pl指向a,p2指向j时,由于p2m越界,那么此时p1l,p2不要变 这里pl之后( abc jk)就是尾巴,处理尾巴只需将j,k移到abc之前,得到最终 序列,代码编写如下: // copyright@Juy、颜沙 //最终代码,Ju1y, updated again,2011.04.17。 #include <iostream> include <string> using namespace std void rotate(string &str, int m) if (str length(==0m <=0) return int n =str length (); if(m %n<=0) return int p1 =0, p2 =m; int k =(n-m)-n% m 交换p1,p2指向的元素,然后移动p1,p wh11e(k--) swap(str[p1], str[p2]); p1++ //重点,都在下述几行。 //处理尾部,r为尾部左移次数 int r=n -p2 While (r-- int i whi1e(主>p1) swap(stri], str[i-1]); 1++ //比如一个例子, abcdefghijk 1 2 //当执行到这里时, defghi a b cjk //p2+m出界了, //r=n-p2=2,所以以下过程,要执行循环俩次 /第一次:j步步前移, abook-> aback-> ajbck-> jack /然后,p1++,p2++,p1指a,p2指k 1 /第二次: defghi j a b k //同理,此后,k步步前移,abck->abkc->akbc- >kabc int main() string ch="abcdefghijk rotate(ch, 3) cout<schscendl return 0; 方法二: def ghi abc jk 当p1指向a,p2指向j时,那么交换p1和p2, 此时为 def ghi jbc ak p1++,p)2++,pl指向b,p2指向k,继续上面步骤得: def ghi jkc ab p1++,p2不动,pl指向c,p2指向b,p1和p2之间(cab)也就是尾巴, 那么处理尾巴(cab)需要循环左移一定次数(而后的具体操作步骤已在下述程序 的注释中已详细给出)。 根据方案二,不难写出下述代码(已测试正确): #include <iostream> include <string> using namespace std //颜沙,思路二之方案二 //Ju1y、 updated,2011.04.16。 void rotate(string &str, int m) if(str.1 ength()==日 m<日 return //初始化p1,p2 int p1 =0, p2 =m int n =str length(): //处理m大于 if(m return //循环直全p2到达字符串末尾 while(true) swap(str[pl], str[p2]) 1+ if (p2< else break //处理尾部,P为尾部循环左移次数 int r=m-n%m;// r=1 whie(r--)//外循环执行一次 int i =p1 char temp str[p1]; whi1e(i<p2)/内循环执行俩次 str[i]= str[i+1]: str[p2]= temp //举一个例子 //abcdefghijk //当执行到这里的时候, defghiabcj 1 // defghi a bcj k,a与j交换, beak,然后,p1++,p2++ i c a k,b与k交换, scab,然后,p1++,p2不动, //r=m-n%m=3-11%3=1,即循环移位1次 p1 p2 i k c a b //p1所指元素c实现保存在temp甲, /然后执行比条语句:str[i]=str[i+1];即a跑到c的位置处,ab //i++,再次执行:str[i]=str[i+1],ab /最后,保存好的c填入,为abc,所以,最终序列为 defghi jk abc。 //Ju1y、 updated,2011.04.17晚,送走了她 int maino) string ch="abcdefghijk"; state(ch, 3) ut<<ch<send return 0 注意:上文中都是假设m<n,且如果鲁棒点的话令m=m‰n,这样m允许大于n。 另外,各位要记得处理指针为空的情况 还可以看下这段代码: cpp Created on: 2011-5-11 Author: Bigpotat #includesiostream> include<string> #define positiveMod(m, n)((m)%(n)+(n))%(n) *左旋字符串str,m为负数时表示右旋abs(m)个字母 d rotate(std: string &str, int m) if (str length== 0) return

...展开详情
试读 127P 程序员编程艺术
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
embeddedness 相当不错,特别是对面试及其有用
2014-08-23
回复
monk0123456 相当不错,特别是对面试及其有用
2014-06-24
回复
上传资源赚积分or赚钱
最新推荐
程序员编程艺术 10积分/C币 立即下载
1/127
程序员编程艺术第1页
程序员编程艺术第2页
程序员编程艺术第3页
程序员编程艺术第4页
程序员编程艺术第5页
程序员编程艺术第6页
程序员编程艺术第7页
程序员编程艺术第8页
程序员编程艺术第9页
程序员编程艺术第10页
程序员编程艺术第11页
程序员编程艺术第12页
程序员编程艺术第13页
程序员编程艺术第14页
程序员编程艺术第15页
程序员编程艺术第16页
程序员编程艺术第17页
程序员编程艺术第18页
程序员编程艺术第19页
程序员编程艺术第20页

试读结束, 可继续阅读

10积分/C币 立即下载 >