前两天看到有人在发Google实习生招聘题，自己手痒也实现了一个。
原帖地址：
http://www.blogjava.net/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 }
主要是通过二叉树来保存字符，从而减少对比的次数来达到优化。因为想到很多面试题目都不给用泛型，所以这里都用数组实现了。
程序员的一生其实可短暂了，这电脑一开一关，一天过去了，嚎；电脑一开不关，那就成服务器了，嚎……