一道笔试题

1. 分析

1. 诚然，最先想到的方法就是10层循环（OMG！），这显然是一个很可怕的方法（虽然这并没有错）。

2. 那么我们该怎么办呢？

3. 接下来就该想到将这62个字符对应一个固定的下标，我们按一定的方法生成一个下标数组，然后取出对应的字符组成字符串，就是我们要的结果啊！

4. 那么这个下标数组该如何生成呢？

5. 我们可以维护一个包含10个下标值的数组（因为元素不能重复，所以初始值可以设定为（0,1,2,3,4,5,6,7,8,9），而不是（0,0,0,0,0,0,0,0,0）），

1. 然后检查其中是否有重复的下标？如果有，则不符合要求，进行下一步；如果没有，则符合要求，输出其对应的字符串；

2. 将数组中最后一个数加1，然后从后向前遍历数组，每个数（原始字符串的长度）除以62，将结果加到前一个数上，其本身对62取余；

3. 检查这个数组是否已经遍历完所有的组合（数组中所有的数都是61），没有，则返回（i）步开始执行，否则程序结束




2. 代码

3. public class Main {
   
   	private static final String originalStr = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
   
   	
   	public static void main(String[] args) {
   		int[] charArr = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 61};
   		while(notTheEnd(charArr)) {
   			if(isOK(charArr)) {
   				System.out.println(getString(charArr));
   			}
   			addOne(charArr);
   		}
   	}
   	
   	/**
   	 * 查看charArr是否已经查找到最后一个值，即所有的值都是61
   	 * @param charArr
   	 * @return
   	 */
   	private static boolean notTheEnd(int[] charArr) {
   		for(int i = 0; i < charArr.length; i++) {
   			if(charArr[i] < 61)
   				return true;
   		}
   		return false;
   	}
   	
   	/**
   	 * 将charArr的最后一个值加1，超过61，要对62取余，并向前一个数进位
   	 * @param charArr
   	 */
   	private static void addOne(int[] charArr) {
   		int len = originalStr.length();
   		charArr[charArr.length - 1]++;
   		
   		int carry = 0;
   		for(int i = charArr.length - 1; i >= 0; i--) {
   			charArr[i] += carry;
   			carry = charArr[i] / len;
   			charArr[i] %= len;
   		}
   	}
   	
   	/**
   	 * 查看charArr中是否有重复值
   	 * @param charArr
   	 * @return
   	 */
   	private static boolean isOK(int[] charArr) {
   		for(int i = 0; i < charArr.length; i++) {
   			for(int j = i + 1; j < charArr.length; j++) {
   				if(charArr[i] == charArr[j])
   					return false;
   			}
   		}
   		return true;
   	}
   	
   	/**
   	 * 将charArr中数字所对应的字符，组成字符串返回
   	 * @param charArr
   	 * @return
   	 */
   	private static String getString(int[] charArr) {
   		StringBuffer sb = new StringBuffer();
   		for(int i = 0; i < charArr.length; i++) {
   			sb.append(originalStr.charAt(charArr[i]));
   		}
   		
   		return sb.toString();
   	}
   }

4. 总结

   总体思想还是进制的问题。算法还是有些幼稚，还有很多地方可以优化，如：

1. 如何判断数组中是否有重复值；

2. 如果有重复值出现，如何快速跳动到下一个不包含重复值的数组；

一道笔试题

原文：http://my.oschina.net/lovewxm/blog/519613