力扣382周赛

力扣第382场周赛

按键变更的次数

模拟

class Solution {
public:
    bool che(char a , char b){
        char c;
        if(a >= 'a' && a <= 'z'){
            c = a - 32;
        }else c = a + 32;
        if(a == b || b == c)return true;
        return false;
    }
    int countKeyChanges(string s) {
        int n = s.size();
        int ans = 0;
        for(int i = 1 ; i < n ; i ++){
            if(che(s[i] , s[i - 1]))continue;
            ans ++;
        }
        return ans;
    }
};

子集中元素的最大数量

从小到大模拟枚举，加上特判

class Solution {
public:
    int maximumLength(vector<int>& nums) {
        int n = nums.size();
        map<long long,int>m;
        map<long long,bool>st;
        for(auto x : nums){
            m[x] ++;
        }
        sort(nums.begin() , nums.end());
        long long ans = 1;
        if(m[1]){
            if(m[1] % 2 == 0)ans = max(ans , (long long)m[1] - 1);
            else ans = max(ans , (long long)m[1]);
        }
        for(int i = 0 ; i < n ; i ++){
            long long x = nums[i] , len = 0;
            if(st[x] == true)continue;
            st[x] = true;
            while(x != 1 && m[x] >= 2){
                x *= x;
                st[x] = true;
                len += 2;
            }
            if(m[x] >= 1){
                len += 1;
                ans = max(ans , len);
            }else{
                len -= 1;
                ans = max(ans , len);
            }
        }
        return ans;
    }
};

Alice 和 Bob 玩鲜花游戏

奇偶分类

class Solution {
public:
    long long flowerGame(int n, int m) {
        long long res = 0;
        vector<int>v(3);
        for(int x = 1 ; x <= m ; x ++){
            if(x % 2)v[1] ++;
            else v[2] ++;
        }
        for (int i = 1; i <= n; ++i)
        {
            if (i % 2 == 0)
                res += v[1];
            else
                res += v[2];
        }
        return res;
    }
};

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

试填法，看答案的哪一位是否能为1

class Solution {
public:
    int minOrAfterOperations(vector<int> &nums, int k) {
        int ans = 0, mask = 0;
        for (int b = 29; b >= 0; b--) {
            mask |= 1 << b;
            int cnt = 0, and_res = -1; // -1 的二进制全为 1
            for (int x : nums) {
                and_res &= x & mask;
                if (and_res) { //这段还没完
                    cnt++; // 合并 x，操作次数加一
                } else {//这段完了
                    and_res = -1; // 准备合并下一段
                }
            }
            if (cnt > k) {
                ans |= 1 << b; // 答案的这个比特位必须是 1
                mask ^= 1 << b; // 后面不考虑这个比特位
            }
        }
        return ans;
    }
};

–