Leetcode第344场周赛解题报告

时隔一年，开始重新关注LC，进行复健活动

题目比较简单，宝刀未老只能说

100372. 使两个整数相等的位更改次数

知识点：模拟、位运算
复杂度：$O(1)$

class Solution {
public:
    int minChanges(int n, int k) {
        int cnt = 0;
        for(int i = 0;i < 32;i++) {
            //cout << i << " " << ((n >> i) & 1) << " " << ((k >> i) & 1) << endl;
            if((((n >> i) & 1) == 1) && (((k >> i) & 1) == 0)) { 
                n ^= 1 << i;
                cnt += 1;
            }
        }
        if(n==k){
            return cnt;
        }
        return -1;
    }
};

反思：

1. 语法上，优先级忘了
2. 常用的位运算，符号含义忘了

100335. 字符串元音游戏

知识点：归纳
复杂度：$O(n)$
对不同情况进行模拟，脑内简化

class Solution {
public:
    bool doesAliceWin(string s) {
        //偶数
        int cnt = 0;
        for(char x : s) {
            if(x == 'a' || x == 'e' || x=='i' || x=='o' || x=='u') cnt++;
        }
        return cnt > 0;
    }
};

反思：

1. 归纳速度较慢，少算了情况（数据集中没有给出）

100360. 将 1 移动到末尾的最大操作次数

知识点：前缀/后缀和
复杂度：$O(n)$
进行contribution后，发现从后往前扫，每遇到一个0,对答案的贡献为前面1的个数

class Solution {
public:
    int maxOperations(string s) {
        int ans = 0;
        int cnt = 0;
        bool lft = false;
        for(char x : s){
            if(x=='1') cnt++;
        }
        for(int i = s.size()-1;i >= 0;i--) {
            if(s[i]=='0' && !lft) ans += cnt, lft = true;
            if(s[i]=='1') cnt--, lft = false;
        }
        return ans;
    }
};

100329. 使数组等于目标数组所需的最少操作次数

知识点：归纳、单调栈
复杂度：$O(n)$
首先，明确操作的对象，即两者之差
其次，利用类似“接雨水”的方式思考贡献，问题转换为求山峰之间最低的pos，作为能够“复用”的点，然后剩下的每个山峰只能自己消自己的，代价为最高点

class Solution {
public:
    long long minimumOperations(vector<int>& nums, vector<int>& target) {
        int n = nums.size();
        vector<long long> diff(n,0);
        for(int i = 0;i < n;i++) {
            diff[i] = target[i] - nums[i];
            //cout << diff[i] << " ";
        }
        long long ans = abs(diff[0]);
        int lst = diff[0];
        for(int i = 1; i < diff.size();i++) {
            int x = diff[i];
            if(x > 0) {
                if(x > lst) {
                    ans += x - max(0,lst); //如果小于 0，只管 0
                }
            }else{
                if(x < lst) {
                    ans += -x - max(0,-lst); //如果大于 0，只管 0
                }
            }
            lst = x;
        }
        //cout << endl;
        return ans;
    }
};