【Leetcode 程序员面试金典(第六版) 01.01】判定字符是否唯一 —— 位运算|哈希表

面试题 01.01 判定字符是否唯一

实现一个算法，确定一个字符串s的所有字符是否全都不同。

示例 1：

输入: s = “leetcode”
输出: FALSE

示例 2：

输入: s = “abc”
输出: TRUE

限制：

• 0 <= len(s) <= 100
• s[i]仅包含小写字母
• 如果你不使用额外的数据结构，会很加分。

题目分析

哈希表

由题可知：s[i] 仅包含小写字母，故可以使用int[26]来标识 a-z 的出现次数，看是否存在相同字符

/**
 * 哈希表
 * @param astr
 * @return
 */
public boolean isUnique(String astr) {
    int[] tmp = new int[26];
    char[] chars = astr.toCharArray();
    for(char c : chars){
        if(tmp[c - 'a'] != 0){
            return false;
        }
        tmp[c - 'a']++;
    }
    return true;
}

位运算

由题可知：s[i] 仅包含小写字母，在 ASCII 码中，英文小写字母的序号范围是 97 到 122

• 1L << 0 即为 a 字符存储位置
• 1L << 25 即为 z 字符存储位置

算法思路:

• i & (1 << k)用于判断 i 的第 k 位数字是否为 0；实际上和数组或哈希表记录相似，相当于nums[k]
• i | (1 << k)用于将 i 的第 k 位数字赋值为 1, 相当于 nums[k] = 1

public boolean isUnique(String astr) {
    int tmp = 0;
    for (char k : astr.toCharArray()) {
        int bitIndex = 1 << (k - 97);
        if ((tmp & bitIndex) != 0) {
            return false;
        }
        tmp |= bitIndex;
    }
    return true;
}