package codinginterview;/** *  * 实现一个算法来判断一个字符串中的字符是否唯一(即没有重复).  * 不能使用额外的数据结构。 (即只使用基本的数据结构) * @author mingdong.cheng *  */public class CheckUniqueChar {	/**	 * 对于ASCII字符，我们需要256位	 * 该算法的时间复杂度为O(n)	 * @param s	 * @return	 */	public static boolean isUnique(String s) {		final boolean[] a = new boolean[256];		int len = s.length();		for (int i = 0; i < len; i++) {			int v = (int) s.charAt(i);			if (a[v])return false;			a[v] = true;		}		return true;	}	/**	 * 通过位运算来减少空间的使用量。 	 * 用每一位表征相应位置字符的出现。	 * 对于ASCII字符，我们需要256位，即一个大小为8的int 数组a即可。	 * 这里的关键是要把字符对应的数字，映射到正确的位上去。	 * 比如字符'b'对应的 代码是98，那么我们应该将数组中的哪一位置为1呢？	 * 用98除以32，得到对应数组a的下标:3。	 * 98对32取模得到相应的位:2。	 * 该算法的时间复杂度为O(n)，需要的内存空间更小	 * @param s	 * @return	 */	public static boolean isUnique2(String s) {		final int[] a = new int[8];//位运算时，256个字符需要8个整型数来表征存储位：256/32=8		int len = s.length();		for (int i = 0; i < len; i++) {			int v = (int) s.charAt(i);			int idx=v/32,shift=v%32;		    int b=a[idx]&(1 << shift);			if (b!=0)return false;			a[idx]|=(1 << shift);		}				return true;	}			/**	 * 如果字符集只是a－z(或是A－Z)仅26个字符，那就更好办了，用位运算只需要一个整型数即可。	 * @param s	 * @return	 */	public static boolean isUnique3(String s) {		int check=0;//位运算可映射表征32位		int len = s.length();		for (int i = 0; i < len; i++) {			int v = (int) s.charAt(i);		    int b=check&(1 << v);			if (b!=0)return false;			check|=(1 << v);		}				return true;	}		public static void main(String[] args) {		String s1 = "i am daniel cheng.";		String s2 = "abcdefghijklmnopqrstuvwxyzABCD1234567890";		String s3 = "abcdefghijklmnopqrstuvwxyz";		String s4 = "01234567892";		System.out.println(isUnique(s1));		System.out.println(isUnique2(s2));		System.out.println(isUnique3(s3));		System.out.println(isUnique3(s4));	}}