给定一个string iniString,请返回一个string,为该字符串翻转后的结果。要求不使用额外数据结构和储存空间,可以使用单个过程变量,保证字符串的长度小于等于5000。
测试样例:
"This is nowcoder"
返回:"redocwon si sihT"
折半交换。
将字符串一分为二。分别交换这两部分即可。
递归停止条件是子串长度为2或3.这两种情况可以之间返回交换后的结果。
设字符串长度为l:
若l为双数,分别处理 substring(l/2,l)+substring(0,l/2).
如“abcdefgh”=>“efgh|abcd”=>“gh|ef|cd|ab”=>“hg|fe|dc|ba”即可。
若l为单数,分别处理substring(l/2+1,l)+charAt(l/2)+substring(0,l/2).
如“abcdefghi”=>"fghi|e|abcd"=>"hi|fg|e|cd|ab"=>"ih|gf|e|dc|ba".
if(iniString.length()==2){ return ""+iniString.charAt(1)+iniString.charAt(0); } if(iniString.length()==3){ return ""+iniString.charAt(2)+iniString.charAt(1)+iniString.charAt(0); } //双数 if(iniString.length()%2==0) return reverseString(iniString.substring(iniString.length()/2,iniString.length())) +reverseString(iniString.substring(0,iniString.length()/2)); //单数 else return reverseString(iniString.substring(iniString.length()/2+1,iniString.length())) +iniString.charAt(iniString.length()/2) +reverseString(iniString.substring(0,iniString.length()/2));
//提供三种思路四种方法
//jdk方法,没有考虑***对,位运算巧妙解决了奇偶个数问题
public static String rNative(String s){
int length = s.length();
char[] carray = s.toCharArray();
for(int i=(length-1)>>1; i>=0; i--){
carray[length-1-i] = s.charAt(i);
carray[i] = s.charAt(length-1-i);
}
return new String(carray);
}
//直接用
public static String r(String s){
StringBuffer sb = new StringBuffer(s);
return sb.reverse().toString();
}
//二分法递归
public static String r1(String s){
int length = s.length();
if(length <= 1)
return s;
String left = s.substring(0, length/2);
String right = s.substring(length/2, length);
return r1(right)+r1(left);
}
public static String r2(String s){
String reverse = "";
for(int i=s.length()-1; i>=0; i--){
reverse += s.charAt(i);
}
return reverse;
}
import java.util.*; public class Reverse { public String reverseString(String iniString) { // write code here int len = iniString.length(); StringBuilder sb = new StringBuilder(iniString); for(int i = 0;i < len/2;i++){ char tmp = sb.charAt(len-i-1); sb.setCharAt(len-i-1, sb.charAt(i)); sb.setCharAt(i, tmp); } return sb.toString(); } }
import java.util.*; public class Reverse { public String reverseString(String iniString) { StringBuilder sb = new StringBuilder(iniString); int low = 0; int high = iniString.length()-1; char temp = '\0'; while(low<high){ temp = sb.charAt(low); sb.setCharAt(low, sb.charAt(high)); sb.setCharAt(high, temp); low++;high--; } return sb.toString(); } }
public class Reverse { public String reverseString(String iniString) { String temp1=iniString; StringBuffer temp2=new StringBuffer(); for(int i=0;i<temp1.length();i++) { temp2.append(temp1.charAt(temp1.length()-i-1)); } return temp2.toString(); } }
//核心代码演示 public static String reverseString(String iniString) { //先将字符穿转换成字符数组 char []str = iniString.toCharArray(); //临时变量,用于交换数值 char temp; //交换次数 int n = str.length/2; int i=0,j = str.length-1; while(n-->0) { temp = str[i]; str[i] = str[j]; str[j] = temp; i++;j--; } //返回交换后的字符串 return String.valueOf(str); }