力扣第407场周赛

A

image-20240721141339142

由于要把n->k，而且只能是1->0，那么显而易见的如果n的二进制位是0，而k得二进制位是1的话，那么永远没有办法实现。

也就是说n的二进制位是1的话，k可以是0或1，但n是0,k也必须是0。

因此推理得到第一个要求n&k==k，不然不满足。

满足上述条件之后，只需要计算n和k不一样的位数即可，这里很自然用到^运算即可。

C++中__builtin_popcount()的使用

这个函数功能：返回输入数据中，二进制中‘1’的个数。

对于不同的使用类型，可以采用采用以下函数：

1
2
3
__builtin_popcount = int
__builtin_popcountl = long int
__builtin_popcountll = long long

例子：

1
2
3
4
5
6
7
8
9
10
11
// C++ code to demonstrate the
// __builtin_popcount function
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n = 4;
    // Printing the number of set bits in n
    cout << __builtin_popcount(n);
    return 0;
}

输出

1
1

时间复杂度(b)，其中b是位数。 辅助空间：O(1)

1
2
3
4
5
6
7
class Solution {
public:
    int minChanges(int n, int k) {
        if ((n & k) != k) return -1;
        return __builtin_popcount(n ^ k);
    }
};

B

image-20240721142121739

感觉操作次数一定不会很多。

冷静分析一下：

如果元音是奇数：直接拿完，先手赢。

如果元音是偶数的话，直接拿剩下一个元音，那也是先手赢。

因此只有当没有元音时候，后手才有可能赢得比赛。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution 
{
    public: 
    bool doesAliceWin(string s) 
    {
        for(int i = 0; i < s.length(); i ++)
            if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
                return true;
        
        return false;
    }
};

C

image-20240721143206825

优先操作左边的车会更加优秀。

具体枚举过程见代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxOperations(string s) {
        int n = s.size();
        int res = 0;
        int ans = 0;  
        for (int i = 0; i < n; ++i) {
            if (s[i] == '1') 
            {
                ans++;
            } 
            else if (i && s[i - 1] == '1') 
            {      
                    res += ans;
            }
        }

        return res;
    }
};

D

image-20240721144701602

在本题之前还有一道典型例题：

1526. 形成目标数组的子数组最少增加次数

image-20240721145402178

为本题的简单版本：

只需要五行代码，即：

求出数组 target 中相邻两元素的差值，保留大于 0 的部分，累加即为答案。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int minNumberOperations(vector<int>& target) {
        int n = target.size();
        int ans = target[0];
        for (int i = 1; i < n; ++i) {
            ans += max(target[i] - target[i - 1], 0);
        }
        return ans;
    }
};

而本题同理：

只需要把每一段正数和负数提取出来采取上述方法加起来即可，因为包含符号相同的数字一定不最优。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
    long long minimumOperations(vector<int>& nums, vector<int>& target) {
        int n = nums.size();
        long long det[n];
        for (int i = 0; i < n; i++)
            det[i] = target[i] - nums[i];
        auto sgn = [&](long long x)
        {
            if (x == 0) return 0;
            if (x > 0) return 1;
            return -1;
        };
        auto jisuan = [&](int l, int r) {
            long long ret = 0, last = 0;
            for (int i = l; i <= r; i++)
        {
            if(i==l)
            {
                ret+=abs(det[i]);
            }
            else
            {
                ret += max((long long)(abs(det[i]) - abs(det[i - 1])), 0ll);   
            }
        }

            return ret;
        };

        long long ans = 0;
        for (int i = 0, j = 0; i < n; i++)
        {
            if (i == n - 1 || sgn(det[i + 1]) != sgn(det[j]))
            {
                ans += jisuan(j, i);
                j = i + 1;
            }
        }
        return ans;
    }
};