题目来源:https://leetcode.com/problems/repeated-dna-sequences/description/

标记难度:Medium

提交次数:2/3

代码效率:

  • 普通的map:84.31%
  • bitset+Rolling hash:99.74%

题意

有一个只包含ATGC的字符串序列,求其中全部长度为10的且出现了不止一次的序列。

分析

初步的想法

只要使用unordered_map作为Hash表,那就很简单了:只要依次遍历所有长度为10的字符串,然后把它们加入到unordered_map中,最后统计unordered_map中出现长度多于1次的序列即可。显然这个方法是可行的。

交上去之后我居然还写错了一次长度为10的子串的边界条件,所以wa了。

如何加速?

上述做法存在几个显而易见的问题:

  • 最后需要多遍历一次unordered_map,能否节省这一次遍历?
  • unordered_map<string, int>的速度是否太慢?
  • 是否存在对string的更好的hash方法?

所以可以进行如下改进:

  • 用两个Hash表来存储序列,一个存储的是所有出现过的序列,另一个只存储至少出现了两次的序列,这样就可以节省最后的一次遍历了。
  • 改为采用Rolling Hash的方法滚动计算Hash值,并利用位运算进一步减少计算所需的时间。
  • 由于对Hash值的范围进行了限定,因此可以改用其他的数据结构(如bitset)作为Hash表。

至于Rolling Hash如何和位运算结合起来,我见到的一种比较好的平衡了编写难度和运行时间的写法[1]是这样的:

  • 把4个字符分别映射为0、1、2、3
  • 对每一个新的序列计算Hash值时,先令hash = (hash << 2) | charMap[ch]
  • 显然hash的长度固定为20bit,其最大值为(1 << 20) - 1(全为1),因此可以通过hash &= (1 << 20) - 1的方法来去掉最前面的项

此处使用的应该是Polynomial rolling hash,很类似于四进制的一种想法(也因此能保证hash函数是双射的)。


从中至少可以学到几点:

  1. 位运算是个很好用的东西(前提是没有写错)
  2. bitset在适当的时候可以拿来代替Hash表或者大数组,但一般来说并不是一个关键数据结构

代码

普通的map

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
int n = s.length();
unordered_map<string, int> mmap;
vector<string> ans;

for (int i = 0; i <= n - 10; i++) {
string str = s.substr(i, 10);
mmap[str]++;
}
for (const auto& k: mmap) {
if (k.second > 1)
ans.push_back(k.first);
}
return ans;
}
};

bitset+Rolling hash

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
33
34
35
36
37
38
// 参考了https://leetcode.com/submissions/detail/180202097/
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
int n = s.length();
if (n < 11) return {};

// cheap mapping
int charToInt[200];
charToInt['A'] = 0;
charToInt['C'] = 1;
charToInt['G'] = 2;
charToInt['T'] = 3;

const int MASK = (1 << 20) - 1;
int rhash = 0;
for (int i = 0; i < 9; i++)
rhash = (rhash << 2) | charToInt[s[i]];

// use bitset as hash table
bitset<(1 << 20)> onceSet;
bitset<(1 << 20)> twiceSet;
vector<string> ans;
for (int i = 9; i < n; i++) {
rhash = (rhash << 2) | charToInt[s[i]];
rhash &= MASK;
// 简化代码逻辑
if (twiceSet[rhash]) continue;
if (onceSet[rhash]) {
ans.push_back(s.substr(i - 9, 10));
twiceSet.set(rhash);
}
else
onceSet.set(rhash);
}
return ans;
}
};

  1. sample 4 ms submission

题目来源:https://leetcode.com/problems/bitwise-ors-of-subarrays/description/

标记难度:Medium

提交次数:1/2

代码效率:

  • 暴力:过不了
  • 优化过的暴力:796ms

题意

给定一个正整数数组,求其中(连续)子序列的总共有多少种可能取值。

分析

我也不知道这道题做了多久,总之首先就看错题了(把“或”看成了“异或”),做出来是不太可能的了。其次当时Leetcode服务器大概比较爆炸,平均5分钟才能运行一次。


记数组为A,显然我们的目标就是求出所有or(i, j) = A[i] | ... | A[j] (i <= j)的可能取值。如果直接暴力计算,则复杂度为O(N^3)。一个显而易见的优化是,对于当前的j,我们可以维护一个数组,其中保存了所有以j结尾的子序列的取值;or(0, j), or(1, j), ..., or(j, j)的值;对于j+1,我们可以通过这些值递推出所有以j+1结尾的子序列的取值:or(0, j+1)=or(0, j)|A[j+1], or(1, j+1)=or(1, j)|A[j+1], ... or(j, j+1)=or(j, j)|A[j+1], or(j+1, j+1)=A[j+1]。于是复杂度降低到O(N^2)

(也许我可以推导到这一步,但是后来我信心丧失直接去看题解了)

然后是一个信仰之跃:我们要利用一下或操作的性质,在一个或和中不断或上新的数值,其二进制表示中1的数量不会减少。刚才维护的子序列除了能够递推之外,还满足一个很好的性质:or(0, j) = or(1, j) | A[0] = ... = or(j, j) | A[0] | A[1] | .. | A[j-1];因此,cnt1(or(0, j)) >= cnt1(or(1, j)) >= ... >= cnt1(or(j, j)),且同一位置上的1出现后就不会消失。而题目给定了0 <= A[i] <= 10^9,所以这些数的二进制位最多只有30个。

这也就说明,以j结尾的所有子序列的或和的取值最多只有30种。

所以只需把上述保存以j结尾的子序列的或和的数组改成HashSet,然后维护这个HashSet中的值,就可以得到O(30N)的复杂度。

(上述内容基本参考的都是[1]。)

代码

暴力

过了八十多个测试点中的七十多个,果然O(N^2)暴力还是不可取。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int subarrayBitwiseORs(vector<int>& A) {
int n = A.size();
int ends[n + 1];
unordered_set<int> allSet;

for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++)
ends[j] |= A[i];
ends[i] = A[i];
for (int j = 0; j <= i; j++)
allSet.insert(ends[j]);
}

return allSet.size();
}
};

优化过的暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int subarrayBitwiseORs(vector<int>& A) {
unordered_set<int> sums;
unordered_set<int> all;
int n = A.size();
sums.insert(0);
for (int i = 0; i < n; i++) {
unordered_set<int> sums2 = {A[i]};
for (const auto& j: sums)
sums2.insert(j | A[i]);
for (const auto& j: sums2)
all.insert(j);
sums = sums2;
}
return all.size();
}
};

  1. O(30N)

题目来源:https://leetcode.com/problems/binary-watch/description/

标记难度:Easy

提交次数:1/1

代码效率:100%

题意

有一个二进制LED表,用6个LED灯(1, 2, 4, 8, 16, 32)表示分钟(0-59),4个LED灯(1, 2, 4, 8)表示小时(0-11)。给定共有多少个LED灯是亮的,求所有可能表示的时间。

分析

显然我们可以用搜索来解决这个问题:枚举小时表示中有多少个LED灯是亮的,然后找出所有可能的组合,最后拼在一起。3ms Java Solution Using Backtracking and Idea of "Permutation and Combination"使用的就是这一解法,非常直接。

但是由于时间表示本身的性质(就像在Leetcode 539中说的那样,一天其实只有24*60=1440分钟,24*600*60=86400秒),我们可以写出一种更简单的枚举方法:直接枚举每天的所有时间,然后计算该时间表示中1的数量是否符合要求就可以了。

于是我们又可以用__builtin_popcount了。除此之外,在Straight-forward 6-line c++ solution, no need to explain中,我看到了另一种计算方法:

1
int num = bitset<10>(x).count();

类模板bitset表示一个N位的固定大小序列。可以用标准逻辑运算符操作位集,并将它与字符串和整数相互转换。[1]

这也是个不错的方法(特别是记不住__builtin_popcount的全名的时候),不过我猜测效率会慢一些,毕竟是STL。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<string> readBinaryWatch(int num) {
if (num > 8)
return {};

int hours[4] = {1, 2, 4, 8};
int minutes[6] = {1, 2, 4, 8, 16, 32};

vector<string> times;
for (int hour = 0; hour < 12; hour++)
for (int minute = 0; minute < 60; minute++) {
if (__builtin_popcount(hour) + __builtin_popcount(minute) == num) {
string time = to_string(hour) + ":";
if (minute < 10)
time += "0";
time += to_string(minute);
times.push_back(time);
}
}

return times;
}
};

  1. std::bitset

题目来源:https://leetcode.com/problems/counting-bits/description/

标记难度:Medium

提交次数:2/2

代码效率:

  • naive算法:99.67%
  • 动态规划:99.67%

题意

分别计算出[0, N]中每个数字的二进制表示中1的数量。(注意是分别计算,返回的结果是一个vector,而不是总和。)

进阶:

  • 想出时间复杂度为O(N * sizeof(integer))的算法是很容易的。你能否尝试用O(N)的时间和空间复杂度解决这个问题?
  • 请不要使用类似于C++中的__builtin_popcount的函数。

分析

navie算法

好吧,其实我之前从未听说过__builtin_popcount这个函数,所以我立即去查了一下,并用到了我的naive版本的算法中。事实上,这是一个GCC编译器内置的函数(而不是属于C或C++标准),利用特定CPU的指令(比如x86的LZCNT)完成计算二进制数中1的个数的操作。未来版本的C++可能也会加入相应的支持

所以这么做差不多可以达到时间复杂度为O(N)的要求。

动态规划

但是如果不用这种指令呢……?我开始时只能想到把一个32位数分成4或者8份然后分别去查表,但这样只是减少了一点常数,并不能摆脱sizeof(integer)的限制。于是我去看了题解——

事实上,因为题目要求统计所有数的二进制表示中1的数量,这反而为我们提供了很大的便利。虽然统计一个数的代价很难降低,但显然,一个数的二进制表示和它之前的数是相关的:binary(x) = binary(floor(x/2)) || lastbit(x)。因此我们可以采用类似于动态规划的方法直接推导出当前的数的二进制表示中1的数量。

代码

naive算法

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
vector<int> countBits(int num) {
// naive的算法想都不用想。但是不naive的……
// 我感觉二进制表示已经是很fundamental的了,不知道怎么优化比较好。
// 突然想到一个简单的方法:把每个32位数分成4或8份,然后直接查表。但是这并没有突破sizeof...
vector<int> ans;
for (int i = 0; i <= num; i++)
ans.push_back(__builtin_popcount(i));
return ans;
}
};

动态规划法

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
vector<int> countBits(int num) {
vector<int> ans;
ans.push_back(0);
for (int i = 1; i <= num; i++)
ans.push_back(ans[i >> 1] + (i & 1));
return ans;
}
};

题目来源:https://leetcode.com/problems/total-hamming-distance/description/

标记难度:Easy

提交次数:1/1

代码效率:39.56%

题意

给定若干个数,计算其中所有数对的海明(Hamming)距离之和。

分析

如果直接计算的话,O(N^2)的代价是不可忍受的。然后就很自然地想到,我们把这个问题横向转化一下:既然海明距离计算的只是每个对应二进制位的差异,那么,我们可以直接对所有数的这一位进行统计,得到01的个数,然后计算这一位对整体距离的贡献:count(0) * count(1)

我感觉这种思路的转换方法很常见,但是我一时想不起来其他的例子了,大概最近刷题太少了吧。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int totalHammingDistance(vector<int>& nums) {
int zeroBits[31];
memset(zeroBits, 0, sizeof(zeroBits));
for (int num: nums) {
for (int i = 0; i < 31; i++) {
if ((num & (1 << i)) == 0)
zeroBits[i]++;
}
}
int ans = 0, n = nums.size();
for (int i = 0; i < 31; i++)
ans += zeroBits[i] * (n - zeroBits[i]);

return ans;
}
};