題目描述
給定一個隻包含小寫字母的字元串s，牛牛想将這個字元串中的所有’a’字母全部移動到字元串的末尾，而且保證其它字元的相對順序不變。其中字元串s的長度<=1e6。
一開始的思路是使用一個linkedlist，對string的每個char進行判斷，若不等于‘a’，存入linked；設定一個計數值index，若==‘a’，則index+1，最後再将a加入到linkedlist中去，就得到了排列好順序的字元串，代碼如下：
public class Solution {
/**
* @param s string字元串
* @return string字元串
*/
public String change (String s) {
List <String> a= new LinkedList<>();
int index=0;
for(int i=0;i<s.length();i++) {
if(s.charAt(i)=='a') {
index++;
}
else {
a.add(String.valueOf(s.charAt(i)));
}
}
for(int i=0;i<index;i++) {
a.add("a");
}
return a.toString();
}
}
結果a.toString()得到的是一個排好序的數組，題目要求得到一個string，那不就可以建立一個string然後将linkedlist的值加入到string中
import java.util.*;
public class Solution {
/**
*
* @param s string字元串
* @return string字元串
*/
public String change (String s) {
List <String> a= new LinkedList<>();
int index=0;
for(int i=0;i<s.length();i++) {
if(s.charAt(i)=='a') {
index++;
}
else {
a.add(String.valueOf(s.charAt(i)));
}
}
for(int i=0;i<index;i++) {
a.add("a");
}
String s1=new String();
for(int i=0;i<a.size();i++) {
s1=s1+a.get(i);
}
return s1;
}
}
送出結果：運作逾時 運作時間：2001ms 占用記憶體：15608KB 使用語言：Java 用例通過率：90.00%；看樣子是對了，但是逾時了。
不用linkedlist，使用兩個string來存呢？減少了兩個循環
import java.util.*;
public class Solution {
/**
* @param s string字元串
* @return string字元串
*/
public String change (String s) {
String s1=new String();
String s2=new String();
for(int i=0;i<s.length();i++) {
if(s.charAt(i)=='a') {
s2=s2+"a";
}
else {
s1=s1+s.charAt(i);
}
}
s1=s1+s2;
return s1;
}
}
送出結果：運作逾時 運作時間：2001ms 占用記憶體：15024KB 使用語言：Java 用例通過率：90.00%；看來還是有問題；
如果使用stringbuffer呢？
import java.util.*;
public class Solution {
/**
*
* @param s string字元串
* @return string字元串
*/
public String change (String s) {
char[] arr = s.toCharArray();
StringBuilder sb = new StringBuilder();
StringBuilder aSb = new StringBuilder();
for (char c : arr) {
if (c == 'a') {
aSb.append(c);
}else {
sb.append(c);
}
}
sb.append(aSb);
return sb.toString();
}
}
送出結果：答案正确 運作時間：124ms 占用記憶體：34936KB 使用語言：Java 用例通過率：100.00%
使用stringbuffer效率竟然這麼高，于是我又去查了string與stringbuffer的差別：
簡單地說，就是一個變量和常量的關系。StringBuffer對象的内容可以修改；而String對象一旦産生後就不可以被修改，重新指派其實是兩個對象。
StringBuffer的内部實作方式和String不同，StringBuffer在進行字元串處理時，不生成新的對象，在記憶體使用上要優于String類。是以在實際使用時，如果經常需要對一個字元串進行修改，例如插入、删除等操作，使用StringBuffer要更加适合一些。
string
stringbuffer
測試例子如下
public class Test {
2 public static void main(String args[]) {
3
4 String str = "abc";
5 StringBuffer sb = new StringBuffer("abc");
6 Runtime runtime = Runtime.getRuntime();
7 long start = System.currentTimeMillis();
8 long startFreememory = runtime.freeMemory();
9 for (int i = 0; i < 10000; i++) {
10 str += i;
11 //測試StringBuffer時候把注釋打開
12 //sb.append(i);
13 }
14 long endFreememory = runtime.freeMemory();
15 long end = System.currentTimeMillis();
16 System.out.println("操作耗時:" + (end - start) + "ms," + "記憶體消耗:"
17 + (startFreememory - endFreememory)/1024 + "KB");
18 }
19 }
測試結果：
使用String做10000次向一字元串後添加字元串
操作耗時:1872ms,記憶體消耗:1301KB
使用StringBuffer做10000次向一字元串後添加字元串
操作耗時:15ms,記憶體消耗:162KB
差别非常明顯了。