程序员面试金典【1 】-- 判断字符是否唯一

• 💻   剑指Offer & LeetCode刷题仓库：https://github.com/Damaer/CodeSolution
• 文档地址：https://damaer.github.io/CodeSolution/
• 仓库介绍：刷题仓库：CodeSolution
  
• 📒   编程知识库：https://github.com/Damaer/Coding
• 文档地址：https://damaer.github.io/Coding/#/

1题目

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

示例 1：

输入: s = "leetcode" 输出: false

示例 2：

输入: s = "abc" 输出: true

限制：

0 <= len(s) <= 100 如果你不使用额外的数据结构，会很加分。

2思路与解答

bool数组或者 hashset 统计

第一反应，想到的是用空间换时间，用一个HashSet
统计里面字符是否出现过，只需要遍历一次字符串的字符，没有出现过的，添加到 set
里面，已经出现过的，则直接返回 false
，重拳出击：

import java.util.HashSet;

public class Solution1 {
    public boolean isUnique(String astr) {
        if (astr == null) {
            return false;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < astr.length(); i++) {
            if (set.contains(astr.charAt(i))) {
                return false;
            } else {
                set.add(astr.charAt(i));
            }
        }
        return true;
    }
}

上面的空间复杂度其实算是 O(1)
，因为我们知道，字符的种类其实是有限的，时间复杂度为 O(n)
。

既然字符都是有限的，最多也就 128
个，那我们不如用个数组，表示字符是否出现过，就可以了，注意 a
是ASCII
码最小的，使用相对位置即可，比如 a
的表示位是数组第 0 个，b
则是第一个，依次类推。

public class Solution1 {
    public boolean isUnique(String astr) {
        if (astr == null) {
            return false;
        }
        boolean[] isExisted = new boolean[128];
        for (int i = 0; i < astr.length(); i++) {
            int index = astr.charAt(i) - 'a';
            if (isExisted[index]) {
                return false;
            }
            isExisted[index] = true;
        }
        return true;
    }

}

上面一搞，其实本质上时间复杂度和空间复杂度没有变化，boolean
数组更加轻量级。

位运算

既然要优化，那就优化到底，boolean
数组还是太重了，计算机世界是 0 和 1 的时间，表示字符是否出现过，其实用 0 和 1 就足够了，于是我想到了位运算。

128
种字符，那需要 128
位 ,可是我们不能用数组去搞，只能用 long
类型，long
类型在计算机里，是 64 位，一个不够，用两个，一个表示高 64 位，另外一个表示低 64 位。

那位运算怎么搞？

首先对每个字符区分为两类，大于 64
的，在高位判断，小于 64
的，在低位计算。

然后用下面的位运算判断：

• left = left & (1<<k) 可以判断 left 的第 k 位数字是 0 还是1，与运算，必须两个都为1，才能为1，所以决定权在 left 的 第k位上。

• right = right | (1<<k) 用于将 right 的第 k 位数字赋值为1，因为或运算，只要有一个为1，结果必定为 1

代码如下：

public class Solution1 {
    public boolean isUnique(String astr) {
        if (astr == null) {
            return false;
        }
        long left = 0;
        long right = 0;
        for (char c : astr.toCharArray()) {
            if (c >= 64) {
                long bit = 1L << (c - 64);
                if ((left & bit) != 0) {
                    return false;
                }
                left |= bit;
            } else {
                long bit = 1L << c;
                if ((right & bit) != 0) {
                    return false;
                }
                right |= bit;
            }
        }
        return true;
    }
}

在这里，位运算可能没能优化很多，但是作为程序员，怎么能不苛刻于自己的代码呢？