NC229 判断字符是否唯一

哈希+位运算解法。

解法一：HashSet

思路：判断是否全不同，很自然的想到用HashSet来存放遍历的字符

• 如果HashSet里不存在该字符，就加入
• 如果存在则表明重复，返回false
• 遍历结束，返回true

import java.util.*;
 
public class Solution {
    public boolean isUnique (String str) {
        //哈希解法
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (set.contains(c)) {
                return false;
            } else {
                set.add(c);
            }
        }
        return true;
    }
}

解法二：位运算

思路：假设如果题目中的字符都是字母，每一个字母对应一位，则64位long类型就可以储存所有信息。

• 创建一个long类型的flag变量（考虑到大小写共54位，64位够了）
• 遍历字符，转化为0-54的值，如果flag对应的位置已经有数，说明之前重复过，返回false
• 否则，将字符的值位移到flag变量的对应位置，储存
• 遍历结束，返回true

import java.util.*;
 
public class Solution {
    public boolean isUnique (String str) {
        //位运算解法
        //1创建一个int数，每次循环取出char再位移char个位
        //2将新的int跟原来int比较，相同则说明之前重复过
        long flag = 0;
        for (int i = 0; i < str.length(); i++) {
            if ((flag >>> getCharVal(str.charAt(i)) & 1) == 1) {
            return false;
        } else {
            flag += 1l << getCharVal(str.charAt(i));
            }
        }
        return true;
    }
  	//辅助函数，区分大小写
    private int getCharVal(char c){
        if (c >= 'A'){
            return c - 'A' + 27;
        }else{
            return c - 'a';
        }
    }
}