JAVA实现字符串反转(Reverse)的方法（没有最快，只有更快） |
您所在的位置：网站首页 › java怎么写一个方法的程序 › JAVA实现字符串反转(Reverse)的方法（没有最快，只有更快） |
|
字符串反转在Java程序笔试面试中经常遇到，程序出了满足设计需要外，往往我们还要考虑到性能及内存相关的问题，如果考虑到性能和内存相关的问题，在笔试或面试中更容易赢得考官的青睐。 不多说，给出我这边实现的几种方案： 方案一： private static String reverse(String str) { if (str == null) { return null; } return new StringBuffer(str).reverse().toString(); }利用StringBuffer或StringBuilder自带reverse方法，简单！ 方案二： private static String reverse1(String str) { if (str == null) { return null; } String result = ""; for (int i = str.length() - 1; i >= 0; i--) { result = result + str.charAt(i); } return result; }利用String的charAt方法，逆序拼接。 方案三： private static String reverse2(String str) { if (str == null) { return null; } String result = ""; char[] chars = str.toCharArray(); for (int i = chars.length - 1; i >= 0; i--) { result = result + chars[i]; } return result; }利用String的toCharArray方法，逆序拼接。 方案四： private static String reverse4(String str) { if (str == null) { return null; } int stackSize = str.length(); Stack theStack = new Stack(); for (int i = 0; i < stackSize; i++) { theStack.push(str.charAt(i)); } StringBuilder result = new StringBuilder(); while (!theStack.isEmpty()) { char ch = (char) theStack.pop(); result.append(ch); } return result.toString(); }利用栈，压栈出栈来逆序。 方案五： private static String reverse4(String str) { if (str == null) { return null; } char[] chars = str.toCharArray(); int n = chars.length - 1; for (int i = 0; i < chars.length / 2; i++) { char temp = chars[i]; chars[i] = chars[n - i]; chars[n - i] = temp; } return new String(chars); }二分法逆序字符串数组。 以上方法是容易想到的，都可以实现字符串逆序的功能。我们可以测试下上述五种方法执行的效率。 import java.util.Random; import java.util.Stack; public class TestStringReverse { public static void main(String[] args) { // 实例一个长度为100000的字符串 String test = ""; Random random = new Random(); StringBuffer sb = new StringBuffer(); for (int i = 0; i < 100000; i++) { sb.append(random.nextInt(10)); } test = sb.toString(); // 方法1 long start1 = System.nanoTime(); String reverse1 = reverse1(test); System.out.println("reverse1 time = " + (System.nanoTime() - start1)); // 方法2 long start2 = System.nanoTime(); String reverse2 = reverse2(test); System.out.println("reverse2 time = " + (System.nanoTime() - start2)); // 方法3 long start3 = System.nanoTime(); String reverse3 = reverse3(test); System.out.println("reverse3 time = " + (System.nanoTime() - start3)); // 方法4 long start4 = System.nanoTime(); String reverse4 = reverse4(test); System.out.println("reverse4 time = " + (System.nanoTime() - start4)); // 方法5 long start5 = System.nanoTime(); String reverse5 = reverse5(test); System.out.println("reverse5 time = " + (System.nanoTime() - start5)); System.out.println(test); System.out.println(reverse1); System.out.println(reverse2); System.out.println(reverse3); System.out.println(reverse4); System.out.println(reverse5); } private static String reverse1(String str) { if (str == null) { return null; } return new StringBuffer(str).reverse().toString(); } private static String reverse2(String str) { if (str == null) { return null; } String result = ""; for (int i = str.length() - 1; i >= 0; i--) { result = result + str.charAt(i); } return result; } private static String reverse3(String str) { if (str == null) { return null; } StringBuilder result = new StringBuilder(); char[] chars = str.toCharArray(); int endIndex = chars.length - 1; for (int i = endIndex; i >= 0; i--) { result.append(chars[i]); } return result.toString(); } private static String reverse4(String str) { if (str == null) { return null; } int stackSize = str.length(); Stack theStack = new Stack(); for (int i = 0; i < stackSize; i++) { theStack.push(str.charAt(i)); } StringBuilder result = new StringBuilder(); while (!theStack.isEmpty()) { char ch = (char) theStack.pop(); result.append(ch); } return result.toString(); } private static String reverse5(String str) { if (str == null) { return null; } char[] chars = str.toCharArray(); int n = chars.length - 1; int limit = chars.length / 2; for (int i = 0; i < limit; i++) { char temp = chars[i]; chars[i] = chars[n - i]; chars[n - i] = temp; } return new String(chars); } }运行结果：（方法一到五对应时间分别为reverse1到reverse5，方法执行时间使用纳秒计时单位） reverse1 time = 5624211 reverse2 time = 4089409874 reverse3 time = 2358496 reverse4 time = 14649641 reverse5 time = 1216452 因为测试时间具有随机性，所以测试多组，五种方法耗时关系：reverse2>reverse4>reverse1>reverse3>reverse5. 简单分析下： Java官方API解释： The Java language provides special support for the string concatenation operator ( + ), and for conversion of other objects to strings. String concatenation is implemented through the StringBuilder(or StringBuffer) class and its append method. String conversions are implemented through the method toString, defined by Object and inherited by all classes in Java. For additional information on string concatenation and conversion, see Gosling, Joy, and Steele, The Java Language Specification. 意思是：Java语言为字符串连接运算符（+）提供特殊支持，并为其他对象转换为字符串。 字符串连接是通过StringBuilder （或StringBuffer ）类及其append方法实现的。 另外字串在拼接生成新字串的时候，实际上是在不断的创建新的对象，而原来的对象就会变为垃圾被ＧＣ回收掉，可想而知这样执行效率会有多低。 所以：reverse2比reverse1耗时 方法三和方法四实现上其实也有字串的循环拼接，charAt的效率比char数组取指定index的字符效率低，且方法四多了栈操作比数组操作慢 所以：reverse4比reverse3耗时。 方法三和方法一比较，方法三主要是使用了StringBuilder，StringBuilder效率高，但线程不安全。 所以：reverse1比reverse3耗时。 方法五比方法一要快,这个可以从StringBuffer源码上分析： public AbstractStringBuilder reverse() { boolean hasSurrogates = false; int n = count - 1; for (int j = (n-1) >> 1; j >= 0; j--) { int k = n - j; char cj = value[j]; char ck = value[k]; value[j] = ck; value[k] = cj; if (Character.isSurrogate(cj) || Character.isSurrogate(ck)) { hasSurrogates = true; } } if (hasSurrogates) { reverseAllValidSurrogatePairs(); } return this; } /** Outlined helper method for reverse() */ private void reverseAllValidSurrogatePairs() { for (int i = 0; i < count - 1; i++) { char c2 = value[i]; if (Character.isLowSurrogate(c2)) { char c1 = value[i + 1]; if (Character.isHighSurrogate(c1)) { value[i++] = c1; value[i] = c2; } } } }可以看出，StringBuffer逆序也是基于char数组，循环次数（时间复杂度）比方法五要多。 所以：reverse1比reverse5耗时 最后，关于字符串逆序方法应该还有其他方法，后续如发现比方法五还高效的方法会补充。 备注： 1.大家如有更高效方法，请留言补充； 2.方法暂时未考虑空间复杂度，一般来说高效的方法或多或少空间复杂度高，即所谓的空间换时间。 |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |