LeetCode---382周赛---位运算

题目列表

3019. 按键变更的次数

3020. 子集中元素的最大数量

3021. Alice 和 Bob 玩鲜花游戏

3022. 给定操作次数内使剩余元素的或值最小

一、按键变更的次数

 题目简单明了，就是看相邻的两个字母是否相等，不区分大小写，直接遍历统计即可，这里讲一个位运算的小技巧

代码如下

class Solution {
public:
    int countKeyChanges(string s) {
        int ans=0;
        for(int i=1;i<s.size();i++){
            ans+=(s[i-1]&31)!=(s[i]&31);//用后五个比特位判断字母是否相同
        }
        return ans;
    }
};

class Solution {
public:
    int countKeyChanges(string s) {
        int ans=0;
        for(int i=1;i<s.size();i++){
            ans+=(s[i-1]|32)!=(s[i]|32);//全部转成小写看是否相等
        }
        return ans;
    }
};

class Solution {
public:
    int countKeyChanges(string s) {
        int ans=0;
        for(int i=1;i<s.size();i++){
            ans+=((s[i-1]&(~32))!=(s[i]&(~32)));//全部转成大写看是否相等
        }
        return ans;
    }
};

二、子集中元素的最大数量

这题不是很难，只要暴力枚举出所有子集的长度，取最大长度就行。但是这题的坑比较多，要注意很多细节，具体看代码

class Solution {
public:
    int maximumLength(vector<int>& nums) {
        unordered_map<int,int>cnt;
        for(auto x:nums) cnt[x]++;//统计数字出现的次数
        int ans=1;
        for(auto [x,y]:cnt){//枚举哈希表，即枚举每个数为子集的第一个数的情况
            if(x==1) ans=max(ans,y-(y%2==0));//如果第一个数为1，需要特判
            else{
                int tmp=x,k=0;
                while(cnt.count(tmp)){
                    k+=2;
                    //注意超int范围和数只出现一次的情况
                    if(cnt[tmp]==1||1LL*tmp*tmp>INT_MAX){
                        k--;
                        break;
                    }
                    tmp*=tmp;
                }
                if(k%2==0) k--;//注意tmp不存在的情况
                ans=max(ans,k);
            }
        }
        return ans;
    }
};

三、Alice和Bob玩鲜花游戏

这题就是阅读理解找规律，我们先来只考虑两人拿一条边上的鲜花的情况，如果是奇数，Alice必赢，如果是偶数，Alice必输，现在我们来想想，两条边呢，为了保证Alice必赢，我们只要保证一条边的鲜花为偶数，另外一条边的鲜花为奇数即可，为什么？

因为Alice只要从奇数中拿掉一个，剩下的两条边上鲜花的个数都是偶数，无论Bob如何选择，都无法获胜，那么胜者只能是Alice。其他的情况，只要Alice拿掉一朵鲜花，Bob面对的情况就和刚刚说的一样，即Bob必胜

代码如下

class Solution {
public:
    long long flowerGame(int n, int m) {
        long long l=(n+1)/2,r=(m+1)/2;//求出左边的数的奇数个数和右边数的奇数个数
        return r*(n-l)+l*(m-r);//奇偶配对
    }
};

四、给定操作次数内使剩余元素的或值最小

又是一个位运算的题目，像这类的题目一般可以用拆位的方法来做，即一个个比特位的考虑。这题也是同理，我们可以从高位开始枚举一直枚举到低位，看看答案每个比特位是否能取到1。本质是在构造一个符合条件的最小值。

先来简单解释一下为什么是从高位向低位枚举，而不是从低位向高位枚举。这个可以看作是贪心的策略，本质是比特位的权重不同，举个例子 (1<<4) > (1<<4)-1 ，从二进制的角度看，第四位上的1，比后三位上的1 加起来还大。具体证明就不说了，如果想不明白，可以结合示例多想想。

如何判断比特位上的1能否去掉呢？

class Solution {
public:
    int minOrAfterOperations(vector<int>& nums, int k) {
        int ans=0,mask=0;
        for(int i=31;i>=0;i--){
            mask|=(1<<i);
            int cnt=0,flag=-1;
            for(auto x:nums){
                flag&=(x&mask);
                if(flag)
                    cnt++;
                else
                    flag=-1;
            }
            //这里需要说明一点：我们没有判断不能让flag=0的情况，是因为如果flag不能为0，那么cnt=n>k，题目数据范围限定了n>k，n=nums.size()
            if(cnt>k){
                ans|=(1<<i);
                mask^=(1<<i);
            }
        }
        return ans;
    }
};