力扣第398场

A

很简单的模拟。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution 
{
public:
    bool isArraySpecial(vector<int>& nums) 
    {
        int n = nums.size();
        for (int i = 1; i < n; i++) 
        if (nums[i] % 2 == nums[i - 1] % 2) 
        return false;
        return true;
    }
};

B

看到这种询问很多的题目，往往是需要进行预处理，只需要获取一下区间内有没有奇数和偶数相同的做一个前缀和就可以了。

此题不难。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution 
{
public:
    vector<bool> isArraySpecial(vector<int>& nums,vector<vector<int>>& queries) {

        int n = nums.size();
        vector<int> v(n);
        for (int i = 1; i < n; i++)
            //判断奇数偶数是不是相同
            v[i] = v[i - 1] + ((nums[i] + nums[i - 1]) % 2 == 0 ? 1 : 0);
        vector<bool> ans;
        for (auto e : queries)
            ans.push_back((v[e[0]] == v[e[1]]) ? true : false);
        //没有差距就是可以

        return ans;
    }
};

灵茶山艾府这位佬提供了一种位运算加前缀和的思路，本质一样，但确实巧妙。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) 
    {
        vector<int> s(nums.size());
        for (int i = 1; i < nums.size(); i++) 
        {
            s[i] = s[i - 1] + ((nums[i] ^ nums[i - 1] ^ 1) & 1);
        }
        vector<bool> ans(queries.size());
        for (int i = 0; i < queries.size(); i++) 
        {
            auto& q = queries[i];
            ans[i] = s[q[0]] == s[q[1]];
        }
        return ans;
    }
};

C

第一眼是一个拆位，然后算贡献。

然后好像确实是这样，有点一眼了。

注意除2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution 
{
public:
    long long sumDigitDifferences(vector<int>& nums) 
    {
        int n = nums.size();
        int len = 0;
        for (int x = nums[0]; x; x /= 10) 
            len++;

        long long ans = 0;
        for (int p = 0; p < len; p++) 
        {
            int cnt[10] = {0};
            for (int i = 0; i < n; i++) 
                cnt[nums[i] % 10]++;
            for (int i = 0; i < 10; i++) 
                ans += 1LL * cnt[i] * (n - cnt[i]);
            for (int i = 0; i < n; i++) nums[i] /= 10;
        }
        return ans / 2;
    }
};

D

采用组合数的思想，假设进行了i次操作一，y次操作二，必有k=\(2^i-y\),然乎由于不相邻，可以考虑插空法，也就转化为了组合数。

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
class Solution 
{
public:
    int waysToReachStair(int k)
    {
        long long C[35][35];
        C[0][0] = C[1][0] = C[1][1] = 1;
        for(int i = 2;i <= 30;i++)
        {
            C[i][0] = 1;
            for(int j = 1;j <= 30;j++)
            {
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
            }
        }
        int ans = 0;
        for(int i = 0;i <= 29;i++)
        {
            int tmp = (1 << i) - 1;
            if(tmp + 1 >= k && tmp - i <= k) 
                ans+=C[i + 1][tmp + 1 - k];
        }
        return ans;
    }
};