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

    xiaoxiao2025-02-04  16

    先放题目:

    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)

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

    转载请注明原文地址: https://ju.6miu.com/read-1296076.html
    最新回复(0)