前兩天看到有人在發Google實習生招聘題，自己手癢也實現了一個。
原帖地址：
http://www.tkk7.com/andyelvis/archive/2009/04/14/265496.html
原題：
要求：寫一個函數void count(char* input,int len)，此函數的功能是計算出一個字符串中每個字符的個數，不區分大小寫，輸出結果時按字符在字符串中出現的先后順序。使用程序語言不限。
例如：input="abCc*b"，輸出結果是a:1 b:2 c:2 *:1
1 import static java.lang.System.out;
2 import org.junit.Test;
3
4 /**
5 * 一道Google2009夏季實習生招聘筆試程序設計題
6 * 要求：寫一個函數void count(char* input,int len)，此函數的功能是計算出一個字符串中每個字符的個數，不區分大小寫，輸出結果時按字符在字符串中出現的先后順序。使用程序語言不限。
7 * 例如：input="abCc*b"，輸出結果是a:1 b:2 c:2 *:1
8 * @author Johny Huang
9 * @date 2009-4-14
10 */
11 public class TestCountChar {
12
13 public static class BNode{
14 private BNode left;
15 private BNode right;
16 private int count;
17 private char character;
18
19 public BNode(char c,int count){
20 this.character=c;
21 this.count=count;
22 }
23 public char getCharacter() {
24 return character;
25 }
26 public void setCharacter(char character) {
27 this.character = character;
28 }
29 public BNode getLeft() {
30 return left;
31 }
32 public void setLeft(BNode left) {
33 this.left = left;
34 }
35 public BNode getRight() {
36 return right;
37 }
38 public void setRight(BNode right) {
39 this.right = right;
40 }
41
42 public int getCount() {
43 return count;
44 }
45 public void setCount(int count) {
46 this.count = count;
47 }
48 public void addOne(){
49 this.count++;
50 }
51 }
52
53 @Test
54 public void test(){
55 char[] input="fbagcdagaddddgFBAGCDAGADDDDG".toCharArray();
56 count(input,input.length);
57 }
58
59 /**
60 *
61 * @param input 傳入的字符數組
62 * @param len 需要處理的長度
63 */
64 public void count(char[] input,int len){
65 /*
66 * 主要思想是用一個二叉樹來存儲字符，這樣可以減少字符對比的次數（至少減少一半），
67 * 另外再用一個數組（或鏈表）來保存字符的順序。
68 */
69
70 //校驗參數
71 if(input==null){
72 return;
73 }
74 if(len<1||input.length <1){
75 return;
76 }
77
78 int length=len;
79 if(len>input.length){
80 length=input.length;
81 }
82 //拷貝一個小寫的字符數組
83 char[] inputCopy=new char[length];
84 for(int i=0;i<length;i++){
85 inputCopy[i]=Character.toLowerCase(input[i]);
86 }
87
88 //取第一個字符作為根節點
89 BNode root=new BNode(inputCopy[0],1);
90 //將當前節點設為根節點
91 BNode current=root,temp;
92
93 //申請一個節點數組來保存字符順序，當然也可以用List來保存
94 BNode[] charSeq=new BNode[length];
95 charSeq[0]=root;
96 //charSeq數組的下標（索引）
97 int charSeqIndex=1;
98 char curChar;
99
100 //從第二個字符開始遍歷字符數組
101 for(int i=1;i<length;i++){
102 curChar=inputCopy[i];
103 while(true){
104 //如果字符與當前節點字符相同，則累加1
105 if(curChar==current.getCharacter()){
106 current.addOne();
107 break;
108 }else {
109 if(curChar<current.getCharacter()){
110 //如果字符小于當前節點字符，則轉向左子節點對比
111 if(current.getLeft()==null){
112 //左子節點為空，則加入新的節點
113 temp=new BNode(curChar,1);
114 current.setLeft(temp);
115 //將節點引用保存到數組
116 charSeq[charSeqIndex]=temp;
117 charSeqIndex++;
118 break;
119 }
120 current=current.getLeft();
121 }else{
122 //如果字符大于當前節點字符，則轉向右子節點對比
123 if(current.getRight()==null){
124 temp=new BNode(curChar,1);
125 current.setRight(temp);
126 charSeq[charSeqIndex]=temp;
127 charSeqIndex++;
128 break;
129 }
130 current=current.getRight();
131 }
132 }
133 }
134 //將當前節點指向根節點
135 current=root;
136 }
137
138 for(BNode node:charSeq){
139 out.print(node.getCharacter()+":"+String.valueOf(node.getCount())+" ");
140 }
141 }
142
143 }
主要是通過二叉樹來保存字符，從而減少對比的次數來達到優化。因為想到很多面試題目都不給用泛型，所以這里都用數組實現了。
程序員的一生其實可短暫了，這電腦一開一關，一天過去了，嚎；電腦一開不關，那就成服務器了，嚎……