一道Google2009夏季实习生招聘笔试程序设计题

前两天看到有人在发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  }

   
    主要是通过二叉树来保存字符，从而减少对比的次数来达到优化。因为想到很多面试题目都不给用泛型，所以这里都用数组实现了。