在ACM之家看到一道有趣的算法题，好多类似华为，Google等IT巨鳄，都以此为模板来考察实习生。
（1）华为的考题形式是：通过键盘输入一串小写字母（a~z）组成的字符串，编写一个字符串过滤程序，若字符串中出现多个相同的字符，将非首次出现的字符过滤掉。如，输入字符串“abacacde”，则输出的过滤结果为“abcde”。
不是很难的问题，采用枚举法，一个二重循环就可搞定。示例代码如下：
1 package org.warnier.zhang.demo; 2 3 public class StringFilter { 4 5 public String filter(String origin) { 6 String result; 7 if (origin == null) { 8 result = null; 9 } else { 10 char[] chars = origin.toCharArray(); 11 StringBuilder sb = new StringBuilder(); 12 13 for (int i = 0; i < chars.length; i++) { 14 int j = 0; 15 for (; j < i; j++) { 16 if (chars[i] == chars[j]) { 17 break; 18 } 19 } 20 if (j == i) { 21 sb.append(chars[i]); 22 } 23 } 24 result = sb.toString(); 25 } 26 return result; 27 } 28 }
官网给出的解决方案更巧妙，如下翻译为了Java版：
1 public String filter(String origin){ 2 String result; 3 if(origin == null){ 4 result = null; 5 }else{ 6 /** 7 * 判断字符是否出现的标志； 8 */ 9 boolean[] flags = new boolean[26]; 10 for(int i = 0; i < flags.length; i++){ 11 flags[i] = false; 12 } 13 char[] chars = origin.toCharArray(); 14 StringBuilder sb = new StringBuilder(); 15 /** 16 * 判断字符是否第一次出现； 17 */ 18 for(int i = 0; i < chars.length; i ++){ 19 if(false == flags[chars[i] - 'a']){ 20 flags[chars[i] - 'a'] = true; 21 sb.append(chars[i]); 22 } 23 } 24 result = sb.toString(); 25 } 26 return result; 27 }
（2）Google的考题形式是：在一个字符串中找到第一个只出现一次的字符，如输入abaccdeff，则输出b。
如果提前参见过华为面试的实习生是不是就要幸运的多了，在没有算法复杂度的要求下，上面的代码简单修改一下就搞定了。如，
1 public String filter(String origin) { 2 String result = null; 3 if (origin != null) { 4 char[] chars = origin.toCharArray(); 5 for (int i = 0; i < chars.length; i++) { 6 for (int j = 0; j < i; j++) { 7 if (chars[i] == chars[j]) { 8 chars[i] = '0'; 9 chars[j] = '0'; 10 break; 11 } 12 } 13 } 14 for (int i = 0; i < chars.length; i++) { 15 if (chars[i] != '0') { 16 result = String.valueOf(chars[i]); 17 break; 18 } 19 } 20 } 21 return result; 22 }
官网也给出了一种全新的解法，翻译为Java版如下：
1 public String filter(String origin){ 2 String result = null; 3 if(origin != null){ 4 /** 5 * 保存字符出现的次数； 6 */ 7 int[] flags = new int[26]; 8 for(int i = 0; i < flags.length; i++){ 9 flags[i] = 0; 10 } 11 /** 12 * 统计字符出现的次数； 13 */ 14 char[] chars = origin.toCharArray(); 15 for(int i = 0; i < chars.length; i++){ 16 flags[chars[i] - 'a']++; 17 } 18 for(int i = 0; i < flags.length; i++){ 19 if(flags[i] == 1){ 20 result = String.valueOf((char)('a' + i)); 21 break; 22 } 23 } 24 } 25 return result; 26 }
其实，官网给出的答案不难看出与上面华为考题解答的相似处。这从另一个角度说明，这道考题虽然华为，Google的考察角度不同，但是万变不离其宗，解题的过程中要拨开迷雾，看清本质。
再者，官网的解题策略也是一种巧妙的思路，我曾在自己的一篇博客“分享：GenericCalendar工具类”中，采用类似上述“判断字符是否出现”，“保存字符出现次数”标志量的方式处理平，闰年二月天数的选择问题。