当前位置:  编程技术>java/j2ee

java之左旋转字符串介绍

    来源: 互联网  发布时间:2014-10-23

    本文导语:  题目:定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。要求时间对长度为n的字符串操作的复杂度为O(n),辅助内存为O(1)。 ...

题目:定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。要求时间对长度为n的字符串操作的复杂度为O(n),辅助内存为O(1)。

分析:如果不考虑时间和空间复杂度的限制,最简单的方法莫过于把这道题看成是把字符串分成前后两部分,通过旋转操作把这两个部分交换位置。于是我们可以新开辟一块长度为n+1的辅助空间,把原字符串后半部分拷贝到新空间的前半部分,在把原字符串的前半部分拷贝到新空间的后半部分。不难看出,这种思路的时间复杂度是O(n),需要的辅助空间也是O(n)。

接下来的一种思路可能要稍微麻烦一点。我们假设把字符串左旋转m位。于是我们先把第0个字符保存起来,把第m个字符放到第0个的位置,在把第2m个字符放到第m个的位置…依次类推,一直移动到最后一个可以移动字符,最后在把原来的第0个字符放到刚才移动的位置上。接着把第1个字符保存起来,把第m+1个元素移动到第1个位置…重复前面处理第0个字符的步骤,直到处理完前面的m个字符。

该思路还是比较容易理解,但当字符串的长度n不是m的整数倍的时候,写程序会有些麻烦,感兴趣的朋友可以自己试一下。由于下面还要介绍更好的方法,这种思路的代码我就不提供了。

我们还是把字符串看成有两段组成的,记位XY。左旋转相当于要把字符串XY变成YX。我们先在字符串上定义一种翻转的操作,就是翻转字符串中字符的先后顺序。把X翻转后记为XT。显然有(XT)T=X。

我们首先对X和Y两段分别进行翻转操作,这样就能得到XTYT。接着再对XTYT进行翻转操作,得到(XTYT)T=(YT)T(XT)T=YX。正好是我们期待的结果。

分析到这里我们再回到原来的题目。我们要做的仅仅是把字符串分成两段,第一段为前面m个字符,其余的字符分到第二段。再定义一个翻转字符串的函数,按照前面的步骤翻转三次就行了。时间复杂度和空间复杂度都合乎要求。

代码如下:

public class Test_21 {
 public static void main(String[] args){
  StringBuilder str = new StringBuilder("abcde");
  int index =5;
  System.out.println(LeftTurn(str,index));
 }
 public static String LeftTurn(StringBuilder sb,int index){
  int strlen = sb.length();
  if(sb !=null&&index>=0&&index

    
 
 

您可能感兴趣的文章:

  • java实现判断字符串是否全是数字的四种方法代码举例
  • Java中关于字符串字符数目的问题
  • java字符串比较获取字符串出现次数的示例
  • 在JAVA中如何实现在一个长字符串查找某个字符串??
  • 我使用corba将Java和C程序连接起来,由Java向C传递一个字符串,但是我发现我原来的0a被换成了0d 0a,那位给各解释。
  • 用Java正则去掉字符串中重复出现的字符
  • java实现压缩字符串和java字符串过滤
  • java 字符串有沒有 像 javascript 中 split() 的方法.
  • 如何从java字符串中判断空格在第几位
  • java把字符串写入文件里的简单方法分享
  • java中如何将数字转化为字符串并且不足位数补0
  • 如可在java程序中产生一个几乎永不重复的字符串?
  • 使用java如何分析系统不能识别的字符串?
  • 菜鸟问题:在Java中如何接收从键盘输入的字符串?
  • 请问JAVA中怎样去掉字符串后面的空格,谢谢!!!
  • JAVA求字符串的子串,谢谢!
  • 在java/jsp里怎样判断一个yyyymmdd格式的字符串是合法的日期型字符串,并求两日期字符串之间的天数?
  • 请问在Java里有没有 运算一个字符串的方法? 如vbscript的 eval("3+5*2") = 13
  • java中一个逻辑判断字符串 (1&&0)如何转变成boolean值?
  • java字符串的合并
  • Java判断字符串为空、字符串是否为数字
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • java中如何将ascII 码转换成字符以及将字符转换成ascII码? 在线等待加分!
  • java中对字符串每个字符统计的方法
  • java判断日期字符是否有效(在线等待答案)
  • 如何在java中将任意字符转化为数字
  • 我的问题是:在java中是否有方法能够去掉一行字符串中的某个字符。
  • java中的转义字符介绍
  • Java String字符串和Unicode字符相互转换代码
  • 16进制值为0D的字符在java里怎么写?
  • 菜鸟问题:java如何进行字符处理?
  • 请问java如何判断中文字和字符,有没有这样的类或方法...
  • 如何在java中获取dll中的字符串或者字符数组(通过jni)?
  • 在Java中如何取得一个字符的ASCII码值?
  • java字符如何得到它的ASCII值?
  • 中文字符问题,用java连sybase(在线等待。。)
  • java用的是unicode, c 用的哪种字符编码?
  • Java中去除字符串中所有空格的几种方法
  • Java中统计字符个数以及反序非相同字符的方法详解
  • java 里怎样判断一个字符串为空?
  • socket中,从client端(用java编写的)传到server端(用c编写的)的字符串为何总多一个ASCII码为10的字符呀?
  • Java是否有能够将经过quoted-printable编码的字符序列转换为原文的函数?
  • java命名空间java.sql类types的类成员方法: java_object定义及介绍
  • 我想学JAVA ,是买THINK IN JAVA 还是JAVA2核心技术:卷1 好???
  • java命名空间java.awt.datatransfer类dataflavor的类成员方法: imageflavor定义及介绍
  • 请问Java高手,Java的优势在那里??,Java主要适合于开发哪类应用程序
  • java命名空间java.lang.management类managementfactory的类成员方法: getcompilationmxbean定义及介绍
  • 如何将java.util.Date转化为java.sql.Date?数据库中Date类型对应于java的哪个Date呢
  • java命名空间java.lang.management接口runtimemxbean的类成员方法: getlibrarypath定义及介绍
  • 谁有电子版的《Java编程思想第二版(Thinking in java second)》和《Java2编程详解(special edition java2)》?得到给分
  • java命名空间java.lang.management接口runtimemxbean的类成员方法: getstarttime定义及介绍
  • 本人想学java,请问java程序员的待遇如何,和java主要有几个比较强的方向
  • java命名空间java.awt.datatransfer类dataflavor的类成员方法: stringflavor定义及介绍




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3