The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this patt ...
The string "PAYPALISHIRING"
is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)
P A H NA P L S I I GY I R
And then read line by line: "PAHNAPLSIIGYIR"
Write the code that will take a string and make this conversion given a number of rows:
string convert(string text, int nRows);
convert("PAYPALISHIRING", 3)
should return "PAHNAPLSIIGYIR"
.
题目意思很简单,给定一个字符串以及行数之后输出一个按规定格式的的Z型字符串。本题我采用的方法思路很简单,算法复杂度也较好,是O(n),以下粘贴下我的代码:
public String convert(String s, int numRows) { if(numRows<=1){ return s; } String result = ""; for(int i=0;i<numRows;i++){ int index = i; int nums = 0; while(index<s.length()){ if(i>0&&i<numRows-1){ result+=s.charAt(index); if(nums%2==1){ index+=i*2; } else{ index+=(numRows-1-i)*2; } nums++; } else{ result+=s.charAt(index); index+=(numRows-1)*2; } } } return result; }
但是一上LeetCode看了下击败的人数仅有10%,这就有点纳闷了,同样的算法复杂度却差距这么大,唯一有可能出现问题的地方就是字符串的拼接这时间开销太大了。
然后我将字符串的拼接方式进行更改:
StringBuilder result = new StringBuilder();result.append("123");
用该方法进行字符串拼接,以下是更改后的代码:
public String convert(String s, int numRows) { if(numRows<=1){ return s; } StringBuilder result = new StringBuilder(); for(int i=0;i<numRows;i++){ int index = i; int nums = 0; while(index<s.length()){ if(i>0&&i<numRows-1){ result.append(s.charAt(index)); if(nums%2==1){ index+=i*2; } else{ index+=(numRows-1-i)*2; } nums++; } else{ result.append(s.charAt(index)); index+=(numRows-1)*2; } } } return result.toString(); }
然后在LeetCode上跑了下,下面是结果的截图,击败了92.31%的用户,果然是字符串的拼接效率出现了问题。
下面介绍几种Java中字符串的拼接方法以及相应的时间复杂度:
1、最基础的String+=背后的实质其实是使用StringBuilder对象,究其本质是String对象不可变的原因。虽然编译器对其做了优化,使用StringBuilder的append方法进行追加,但是每循环一次都会创建一个StringBuilder对象,且都会调用toString方法转换成字符串,所以开销很大。因此执行一次字符串“+”,相当于 str = new StringBuilder(str).append("a").toString(); 所以该方法性能极其低下,不适用于大批量数据的拼接操作。
2、StringBuffer 和 StringBuilder 的append方法都继承自AbstractStringBuilder,整个逻辑都只做字符数组的加长,拷贝,到最后也不会创建新的String对象,所以速度很快,完成拼接处理后在程序中用strBuffer.toString()来得到最终的字符串。这两种方法适用于大批量字符串的拼接操作处理。
原标题:LeetCode 6: ZigZag Conversion ——Java中字符串拼接的效率问题
关键词:JAVA
*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们:
admin#shaoqun.com
(#换成@)。