【LeetCode】1178. 猜字谜

发表于 更新于 分类于 Valine：
本文字数： 525 阅读时长 ≈ 1 分钟

1178. 猜字谜

思路

  1. 位运算
    • 移位运算
      • >> 右移
      • << 左移
    • 或 | or
    • 与 & and
    • 异或 ^ xor
1
2
3
4
101010      101010      101010
011100 &    011100 |	011100 ^
--------------------------------
001000      111110      110110

第一步：

1
2
3
4
5
6
7
8
9
for (const string& word: words) {
    int mask = 0;
    for (char ch: word) {
        mask |= (1 << (ch - 'a'));
    }
    if (__builtin_popcount(mask) <= 7) {
        ++frequency[mask];
    }
}

枚举words的每个word，将出现过的字母放在一个最大长度为26的二进制数上，出现过的第 $i$ 个字母，则将它所在的位置标记1，通过或运算除重。利用__builtin_popcount统计这个二进制数mask上有多少个1，因为puzzles[i].length == 7，所以mask出现1的次数最多不能超过7次。

第二步：
枚举所有子集作为谜面的谜底数量

1
2
3
4
int sub = k;
do {
    sub = (sub - 1) & k;
} while(sub != k);

判断条件sub!=k ，最后一次循环时sub=-1而-1&k=k
因为负数用补码储存
1的二进制 是0000 0001
-1的原码:1000 0001
反码:1111 1110
补码:1111 1111
所以-1使用的时候为1111 1111

例如k = 10101的二进制子集有:
10101
10100
10001
10000
00101
00100
00001
00000

1
2
3
4
5
6
7
int sub = k;
do {
    sub = (sub - 1) & k;
    // 首字母必须出现
    if ((1 << (puzzle[0] - 'a')) & sub)
        ret[i] += count[sub];
} while (sub != k);

count为上一步的frequency，sub为当前枚举的子集，如果words中有这个子集，ans+=count[sub]，否则相当于ans+=0，输出ans

拓展

  1. 位运算
  2. __builtin_popcount函数手动实现 338. 比特位计数

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        unordered_map<int, int> frequency;

        for (const string& word: words) {
            int mask = 0;
            for (char ch: word) {
                mask |= (1 << (ch - 'a'));
            }
            if (__builtin_popcount(mask) <= 7) {
                ++frequency[mask];
            }
        }

        vector<int> ans;
        for (const string& puzzle: puzzles) {
            int total = 0;

            // 枚举子集方法一
            // for (int choose = 0; choose < (1 << 6); ++choose) {
            //     int mask = 0;
            //     for (int i = 0; i < 6; ++i) {
            //         if (choose & (1 << i)) {
            //             mask |= (1 << (puzzle[i + 1] - 'a'));
            //         }
            //     }
            //     mask |= (1 << (puzzle[0] - 'a'));
            //     if (frequency.count(mask)) {
            //         total += frequency[mask];
            //     }
            // }

            // 枚举子集方法二
            int mask = 0;
            for (int i = 1; i < 7; ++i) {
                mask |= (1 << (puzzle[i] - 'a'));
            }
            int subset = mask;
            do {
                int s = subset | (1 << (puzzle[0] - 'a'));
                if (frequency.count(s)) {
                    total += frequency[s];
                }
                subset = (subset - 1) & mask;
            } while (subset != mask);
            
            ans.push_back(total);
        }
        return ans;
    }
};

题解2

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
class Solution {
public:
    vector<int> findNumOfValidWords(vector<string>& words, vector<string>& puzzles) {
        unordered_map<int, int> count;
        for (string &word: words) {
            int mask = 0;
            for (char ch : word)
                mask |= (1 << (ch - 'a'));
            ++count[mask];
        }
        
        int n = puzzles.size();
        vector<int> ret(n, 0);
        for (int i = 0; i < n; i++) {
            string &puzzle = puzzles[i];
            int k = 0;
            for (char ch: puzzle) {
                k |= (1 << (ch - 'a'));
            }

            int sub = k;
            do {
                sub = (sub - 1) & k;
                // 首字母必须出现
                if ((1 << (puzzle[0] - 'a')) & sub)
                    ret[i] += count[sub];
            } while (sub != k);
        }
        return ret;
    }
};