C++学习笔记——位操作的妙用由leetcode318题想到的

先放题目：

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0. Example 1: Given [“abcw”, “baz”, “foo”, “bar”, “xtfn”, “abcdef”] Return 16 The two words can be “abcw”, “xtfn”. Example 2: Given [“a”, “ab”, “abc”, “d”, “cd”, “bcd”, “abcd”] Return 4 The two words can be “ab”, “cd”. Example 3: Given [“a”, “aa”, “aaa”, “aaaa”] Return 0 No such pair of words.

现附上自己的time limit exceed解法

class Solution { public: int maxProduct(vector<string>& words) { if(words.size()==0) return 0; vector<int> Max_len; for(int i=0;i<words.size();i++) sort(words[i].begin(),words[i].end()); for(int i=0;i<words.size();i++) { vector<int> m; for(int j=0;j<words.size();j++) { char int_sec[100000]; if(j==i) continue; char *int_sec_end=set_intersection(words[i].begin(),words[i].end(),words[j].begin(),words[j].end(),int_sec); //或者使用 string int_sec; //set_intersection(words[i].begin(),words[i].end(),words[j].begin(),words[j].end(),back_inserter(int_sec)); if(int_sec_end-int_sec==0) m.push_back(words[j].size()); } sort(m.begin(),m.end()); if(m.size()>0) Max_len.push_back(words[i].size()*m[m.size()-1]); else Max_len.push_back(0); } sort(Max_len.begin(),Max_len.end()); return Max_len[Max_len.size()-1]; } };

再附上某大神的位操作解法

int maxProduct(vector<string>& words) { vector<int> mask(words.size()); int result = 0; for (int i=0; i<words.size(); ++i) { for (char c : words[i]) mask[i] |= 1 << (c - 'a'); for (int j=0; j<i; ++j) if (!(mask[i] & mask[j])) result = max(result, int(words[i].size() * words[j].size())); } return result; }

其中

mask[i] |= 1 << (c - 'a');

由于之前接触位操作较少，所以把这句变得更通俗一点

mask[i] =mask[i]| 1 << (c - 'a');

这句话的意思是这样的： 原来初始化的mask值为

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

当进来一个a时 a-a=0，所以在1的右侧添加 0 个 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

按位或后为：

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

当进来一个b时 b-a=1，所以在1的右侧添加 1 个 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0

与上面的结果取按位或为

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1

所以只有当两个字符都有 a b 的时候 他们在取按位与的时候该位才会为1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1

所以当字符有重复数字的时候，二者的按位与必然有1，所以他们的十进制数一定大于0

if (!(mask[i] & mask[j]))

if 里面的数则必然非0，取！后必然为0 反之 if 中的数必然为0 取！后为1，执行计算字符串二者长度的乘积操作

result = max(result, int(words[i].size() * words[j].size()));

mask是vector int 型的，所以mask[i]是 int 型的，而英文字符是26位的，32位机器下的 int 型为4个字节 32 位正好可以存放，而leetcode的编译器确实也是32位 可以 sizeof（int）

由于博主的学识有限，难免会出现错误，欢迎大家在评论区批评，指正，交流，也欢迎大家对博文的内容上的继续补充