编程C++

【STL】bitset

字数统计: 780字   |   阅读时长: 3分
, , , ,

摘要: 本文介绍在 C++ STL 中的 bitset

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

《C++标准库》 第2版，作者 Nicolai M. josuttis，侯捷 译 $12.5

std::bitset 入门

有时候我们经常用整数来表示集合，整数的对应的二进制位为 1 和 0 分别表示该元素是否在集合中。状态压缩DP 就是这种思路的应用。

在 C++ 中我们经常用 int 或者 long long 当做状态压缩的集合使用，配合 &, |, ^ 等操作符，实现集合的运算。

但有的时候集合中的元素很多，超过了 64 个，用 int 和 long long 就不好表示了。此时 std::bitset 就是一种解决方案，它的好处是可以容纳任意个数的元素。

参考以下代码，可容纳的元素个数由模板参数指定。

1
2
3
4
namespace std {
    template <size_t Bits>
    class bitset;
}

这里模板参数不是类型，而是一个无符号整数。如果模板实参不同，实例化所得模板类型就不同。

C++11 的重要新特性

在 c++11 中，bitset 的特性有一些更新：

  • bitset 可以被 string 字面值常量初始化
  • 增加 to_ullong()，实现与 unsigned long long 的转换
  • 增加 all() 检查是否所有 bit 均已置位
  • 为了能够用在 unordered 容器中，bitset 提供了一个默认的 hash 函数, Ref $7-9-2

std::bitset 使用

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

提示：

1
2
0 <= s.length <= 5 * 1e4
s 由英文字母、数字、符号和空格组成

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

算法：双指针 + bitset

用 hashset 维护双指针中的元素，如果仅有小写字母，可以用状态压缩的方式用一个 int 维护集合信息。这里字符不止小写字母，因此可以用 bitset<128> 代替。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.empty()) return 0;
        int n = s.size();
        int i = 0, j = 0;
        bitset<128> state;
        int ans = 0;
        while(i < n && j < n)
        {
            // 推进 j
            while(j < n && !state[(int)s[j]])
            {
                state.set((int)s[j]);
                ++j;
            }
            // [i..j-1] 为候选答案
            ans = max(ans, j - i);
            // 推进 i
            if(j == n) break;
            char target = s[j];
            while(s[i] != target)
            {
                state.reset((int)s[i]);
                ++i;
            }
            state.reset((int)s[i]);
            ++i;
        }
        return ans;
    }
};
Share