题目:现有一个英语语句,比如“London bridge is falling down”,把它完全倒装起来,“down falling is bridge London”。要求:不使用额外的存储空间。
解法1:
使用右移思想,字母和空格分开处理,每次将字符串的最后一位设为临时变量,将数组向右移动一位后,将临时变量放在对应位置。循环结束的条件是最初字符串的第一个单词长度+指针移动变量的位置=整个字符串长度时,结束循环,实现输出。
具体代码1:
public class reverse {private int p = 0,q = 0,i = 0,flag = 0;private char c;public void rev(String str){int len = str.length();char[] ch = str.toCharArray();while(ch[i++]!=' '){flag++;}for(i=len-1;;){if(ch[i]!=' '){if((q+flag)==len){ //判断循环是否结束break;}c=ch[i];for(int j=len-2;j>=p;j--){ //数组整体往后移一位,注意这里是j>pch[j+1]=ch[j];}ch[p]=c;q++;}else{for(int j=len-2;j>=q;j--){ch[j+1]=ch[j];}ch[q++]=' ';p=q;}}System.out.println(ch);}public static void main(String[] args){reverse rev = new reverse();rev.rev("London bridge is falling down");}
}
输出截图1:
解法2:
另一种解法是,首先将整个字符串数组倒置,然后分别将每个单词倒置。
具体代码2:
public class London {private char temp;private int len;public char[] rev(String str){ //将整个字符串倒置len = str.length();char[] chr = str.toCharArray();for(int i=0,j=len-1;i<j;i++,j--){temp = chr[j];chr[j] = chr[i];chr[i] = temp;}return chr;}public void subRev(char[] chars){ //利用p,q变量控制每个单词的初始位置和结束位置(空格)int i = 0,p = 0,q = 0;char ch;while(i< len){while(chars[i++]!=' ') {q++;if(i==len){break;}}for(int m=p,n=q-1;m<n;m++,n--){temp = chars[n];chars[n] = chars[m];chars[m] = temp;}q+=1;p=q;}System.out.println(chars);}public static void main(String[] args){London london = new London();char[] s = london.rev("London bridge is falling down");london.subRev(s);}
}
输出结果2: