[数据结构与算法]Java 每日一题(20210906)

Java 每日一题(20210906)

大家好，我是青空。快来和青空看看今天的Java每日一题吧

题目

实现一个算法，确定一个字符串的所有字符是否全都不同。假使不允许使用额外的数据结构，又该如何处理?

解法

第一种

构建一个布尔值的数组，索引值i对应的标记指示该字符串是否含有字母表第i 个字符。若这个字符第二次出现，则立即返回false

public boolean isUniqueChars2(String str) {
    if (str.length() > 256) {
    		return false;
    }

    boolean[] char_set = new boolean[256];
    for (int i = 0; i < str.length(); i++) {
        int val = str.charAt(i);
        if (char_set[val]) {
            return false;
        }
        char_set[val] = true;
    }
    return true;
}

第二种

使用位向量(bit vector)，可以将空间占用减少为原先的1/8。下面的代码假定字符串只含有 小写字母a到z。这样一来，我们只需使用一个int型变量

public boolean isUniqueChars(String str) {
    if (str.length() > 256) {
    		return false;
    }

    int checker = 0;
    for (int i = 0; i < str.length(); i++) {
    		int val = str.charAt(i) - 'a';
        if ((checker & (1 << val)) > 0) {
        		return false;
        }
        checker |= (1 << val);
    }
    return true;
}