☘前言☘
今天是算法零基础打卡的第45天，题目本身不难，主要是为了理解位运算的。上链接：
《算法零基础100讲》(第45讲) 位运算 (位或) 进阶
🧑🏻作者简介：一个从工业设计改行学嵌入式的年轻人
✨联系方式：2201891280(QQ)
⏳全文大约阅读时间： 20min
全文目录
☘前言☘
🎁主要知识点
位或运算的运用
📓课后习题
318. 最大单词长度乘积
1318. 或运算的最小翻转次数
1318. 或运算的最小翻转次数
898. 子数组按位或操作
📑写在最后
🎁主要知识点
位或运算的运用
给你三个正整数 a、b 和 c。
你可以对 a 和 b 的二进制表示进行位翻转操作，返回能够使按位或运算 a OR b == c 成立的最小翻转次数。
「位翻转操作」是指将一个数的二进制表示任何单个位上的 1 变成 0 或者 0 变成 1 。
a b c 最小反转次数 操作方式
0 0 0 0 无需翻转
0 0 1 1 a变1(或者b变1)
0 1 0 1 b变0
0 1 1 0 无需翻转
好了 真值表我不弄完了 ，其实可以看到
假如直接满足就是0次
假如c是0 需要把a和b都变成0 需要的就是a+b的值
假如c是1 需要把a和b都变成1 需要的就是 一次 因为只要有一个1就好了
int getbit(int v, int i) { return (v & (1<<i)) ? 1 : 0; // 取出第i位 } int minFlips(int a, int b, int c){ int i; int ans = 0; int ai, bi, ci; for(i = 0; i < 31; ++i) { ai = getbit(a, i); bi = getbit(b, i); ci = getbit(c, i); if( (ai | bi) == ci ) { // 直接满足无需翻转 continue; }else if(ci == 0) { ans += (ai + bi); // 需要将a和b都变成0 }else if(ci == 1) { ans += 1; // 只需要把一个变成1就好了 } } return ans; }
📓课后习题
318. 最大单词长度乘积
318. 最大单词长度乘积
给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
解题思路
这道题比较综合，我的做法是将所有的单词用了一个26位的数字进行记录。然后用与操作进行判断是否交叉。
typedef struct { //定义结构体 int len; int bit; }def; void setdef(char *s,def * a){ //拿到位的hash表 同时顺带拿到长度 int ans = 0,i = 0; for(i = 0;s[i];i++) ans |= (1 << (s[i] - 'a'));//对应位置1 a->bit = ans; a->len = i; } int maxProduct(char ** words, int wordsSize){ def hash[wordsSize]; int ans= 0; for(int i = 0;i < wordsSize;i++) //拿到每个元素的长度和位hash setdef(words[i],&hash[i]); int max =0; for(int i = wordsSize - 1;i >=0 ;i--) for(int j = i - 1;j >= 0;j--) //遍历 if((hash[i].bit & hash[j].bit) == 0) //如果没重叠 if(hash[i].len*hash[j].len > max) max = hash[i].len*hash[j].len; //更新最大值 return max; }
1318. 或运算的最小翻转次数
1318. 或运算的最小翻转次数
给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
解题思路
看上面那道题0.0
1318. 或运算的最小翻转次数
1318. 或运算的最小翻转次数
给你三个正整数 a、b 和 c。
你可以对 a 和 b 的二进制表示进行位翻转操作，返回能够使按位或运算 a OR b == c 成立的最小翻转次数。
「位翻转操作」是指将一个数的二进制表示任何单个位上的 1 变成 0 或者 0 变成 1 。
解题思路
看最上面的知识点0.0
int getbit(int v, int i) { return (v & (1<<i)) ? 1 : 0; } int minFlips(int a, int b, int c){ int i; int ans = 0; int ai, bi, ci; for(i = 0; i < 31; ++i) { ai = getbit(a, i); bi = getbit(b, i); ci = getbit(c, i); if( (ai | bi) == ci ) { continue; }else if(ci == 0) { ans += (ai + bi); // 需要全变成0 }else if(ci == 1) { ans += 1; } } return ans; }
898. 子数组按位或操作
898. 子数组按位或操作
我们有一个非负整数数组 A。
对于每个（连续的）子数组 B = [A[i], A[i+1], …, A[j]] （ i <= j），我们对 B 中的每个元素进行按位或操作，获得结果 A[i] | A[i+1] | … | A[j]。
返回可能结果的数量。 （多次出现的结果在最终答案中仅计算一次。）
解题思路
我们知道，或操作是单调并不减的，所以可能或的最大值就是把数组所有元素进行或。所以一开始可以设定max值。
扫描连续子集的适合到达最小值就可以跳出。
利用hash表来存储已经扫描过的值防止重复计算。
有几个重要的点：
hash表一定要用bool类型 因为省空间 233
hash表不能全部初始化，会超时0.0
bool hash[1100000001]; int subarrayBitwiseORs(int* arr, int arrSize){ int max = 0,ans = 0; for(int i = 0;i < arrSize;i++) max |= arr[i]; //算出最大的或值 for(int i = 0;i < arrSize;i++){ //初始化hash表 int temp = 0; for(int j = i;j < arrSize;j++){ temp |= arr[j]; hash[temp] = 0; if(temp == max) break; } } hash[max] = 1,ans++; for(int i = 0;i < arrSize;i++){ //统计 int temp = 0; for(int j = i;j < arrSize;j++){ temp |= arr[j]; if(!hash[temp]) ans++,hash[temp] = 1; if(temp == max) break; } } return ans; }
