LeetCode：第 407 场周赛

总结

因为早上要开会，所以并没有参加该场周赛，有点可惜，下面就来做一下。

前三题还是比较简单的，但是前两题做的时候都先错了一遍非常的可惜，说明自己代码能力还是不够的熟练需要继续锻炼。

第四题差分数组题目，之前没有见过，但是感觉是一个模板可以记忆一下。

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

题目传送门：100372. 使两个整数相等的位更改次数 - 力扣（LeetCode）

锻炼一下二进制能力，签到题目。

最后实现代码如下：

class Solution {
public:
    int minChanges(int n, int k) {
        int ans = 0;
        while(n||k){
            int a = n&1, b = k&1;
            if (a^b){
                if (a==0) return -1;
                ans++;
            }
            n = n>>1; k = k>>1;
        }
        return ans;
    }
};

Q2：100335. 字符串元音游戏

题目传送门：100335. 字符串元音游戏 - 力扣（LeetCode）

脑筋急转弯，做的时候还错了一次😂，

最后实现代码如下：

class Solution {
public:
    bool doesAliceWin(string s) {
        int ans = 0;
        for(char c : s){
            if (c=='a'||c=='e'||c=='i'||c=='o'||c=='u') ans++;
        }
        if (ans==0) return false;
        if (ans==1) return true;
        if (ans==2) return true;
        return true;
    }
};

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

题目传送门：100360. 将 1 移动到末尾的最大操作次数 - 力扣（LeetCode）

模拟题，从头开始遍历，记录1的个数，碰到0时，就要把前面所有的1往后移动直到碰到下一个1或者末尾。

最后实现代码如下：

class Solution {
public:
    int maxOperations(string s) {
        int cnt=0, ans=0;
        bool flag = true;
        for (char c : s) {
            if(c=='1') flag=true, cnt++;
            if(c=='0'&&flag) flag=false, ans += cnt;
        }
        return ans;
    }
};

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

题目传送门：100329. 使数组等于目标数组所需的最少操作次数 - 力扣（LeetCode）

这个题做出来运气成分比较大，观察题目发现是对子数组（具有连续性）进行操作，就将差分数组就直接拿来用了。

核心思想：通过差分数组，把对子数组的操作，转换成两个位置的变化，计算target[i]-nums[i]的差分数组，分析这个差分数组需要的操作次数

整体步骤分为如下3步：

计算target[i]-nums[i]得到一个数组a，相当于我需要一个全为0的数组，操作成数组a
求a的差分数组，原来的每次子数组操作（一堆）转化成每次两个位置的操作
从左到右遍历差分数组，统计操作次数（统计相同符号的和即可）

为什么只统计相同符号的和即可？

由于每次操作会产生一个 +1 和一个 −1，所以操作次数就等于所有正数 d[i] 之和。

最后实现的代码如下：

class Solution {
public:
    long long minimumOperations(vector<int>& nums, vector<int>& target) {
        int n = nums.size();
        vector<int> op_nums(n), op_diff(n+1,0); 
        for (int i=0; i<n; ++i) { op_nums[i] = target[i] - nums[i]; }op_diff[0] = op_nums[0];
        for(int i=1;i<n;++i) op_diff[i] = op_nums[i] - op_nums[i-1];
        op_diff[n] = 0 - op_nums[n-1];
        long long ans = 0;
        for(int i=0;i<=n;++i){
            if (op_diff[i]>0) ans += op_diff[i];
        }
        return ans;
    }
};