关于位操作和掩码（字符串查重）

X_Monster 收录于类别开发

2021-06-15 2022-02-11 约 1116 字预计阅读 3 分钟

关于位操作和掩码（字符串查重）

0.1 背景

今天在 “力扣cn” 做了一道给字符串查重的题。

我的做法：

逐个字符地，把字符串转换成 HashSet（利用HashSet中元素不重复的特性）。
比较 “原字符串” 和 “HashSet” 的长度：
- 如果相同，说明没有重复；
- 如果不同，说明重复了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


public boolean isUnique(String astr) {

    int stringLength = astr.length();
    HashSet<Character> stringSet = new HashSet<>();

    for (int i = 0; i < stringLength; i++) {
        stringSet.add(astr.charAt(i));
    }

    // 比较二者长度，返回结果
    if (stringLength == stringSet.size()) {
        return true;
    } else {
        return false;
    }
}

比起用暴力双循环是好很多，自己还挺满意的，做完题看看解析，又发现了新天地：

虽然这样做，也能通过，而且执行效率排名还挺高；
但是，这其实并不是题目最初设计的考点，或者说还有更好的解法。

0.2 位移运算、位运算和掩码

这个解法还有一个重要前提，就是“只使用小写字母”（全大写字母也行。 “力扣cn” 在搬运的时候，忘了把这点加上）。

当我弄明白这个解法的时候，就像第一次写出 Hello World 时一样兴奋😮

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


public boolean bestSolution(String astr) {

    int resultMask = 0;
    // 初始化结果集（每一位全0：000...00）

    for (int i = 0; i < astr.length(); i++) {
        // 循环取出每个字符
        char t = astr.charAt(i);
        int offset = t - 'a';
        // 算出该字符相对于字符'a'的偏移
        int charMask = 1 << offset;
        // 将"1"按照该偏移量左移，生成该字符对应的哪个位置是1（类似这样：0001...0000）

        if ((resultMask & charMask) != 0) {
            // 将 结果集 和 字符掩码 按位与运算（如果结果不等于0，则存在同为1的位，说明存在重复）
            return false;
        }
        // resultBit |= charBit;
        resultMask = resultMask | charMask;
        // 将 结果集 和 字符掩码 按位或运算，结果赋值给结果集，相当于更新了结果集
    }
    return true;
}

可以把结果集理解为一个与 “a ~ z” 按顺序对应的布尔类型的数组 boolean[] ，有助于理解。

0.3 再谈前提

然后我们再回头看这个重要前提，真实的限制，其实是 “字符串中，使用的字符，其 ASCII 码必须连续，且字符种类不能超过32”（但这样出题就太暴露意图了）。

如果使用33个连续字符，比如用 “ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`a” 进行测试，会得到 false 的结果。

原因是：由于溢出，a 使用了和 A 一样的掩码位，于是被程序判为重复。

所以，如果换成 long 类型，就可以支持到 64 种ASCII码连续的字符（然并卵）。

0.4 举一反三

这里其实用到一个很重要的概念：掩码

其实很多地方都会用到，比如：

数通网络里的 “子网掩码” ¹，如果学过这块，理解起来应该更得心应手。
Linux 文件夹权限也用到了掩码²。
这篇文章做了不错的拓展³：3鼠8瓶问题，和应用的权限控制（去年我写一个PHP项目的时候有类似想法，现在更通透了）。

位操作真是不简单，这是我第二次被位操作惊艳到了，上一次是 “不使用中间变量，交换两个变量的值”（我知道用加法，但不知道可以用位异或）。

目录

关于位操作和掩码（字符串查重）

关于位操作和掩码（字符串查重）

0.1 背景

0.2 位移运算、位运算和掩码

0.3 再谈前提

0.4 举一反三

0.5 参考

相关内容

目录

关于位操作和掩码（字符串查重）

关于位操作和掩码（字符串查重）

0.1 背景

0.2 位移运算、位运算 和 掩码

0.3 再谈前提

0.4 举一反三

0.5 参考

相关内容

在 MyBatis 中动态修改 JDBC 属性

一个在多线程中使用 java.util.logging.Logger 类时应注意的问题

在 Windows 上运行 MapReduce 所需的权限

JAVA Web 工程，从创建到部署

Maven 基础及 IDEA 创建 Maven 项目范例

0.2 位移运算、位运算和掩码