力扣第 408 场周赛

A

判断个位数和两位数是否相等即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean canAliceWin(int[] nums) {
        int sum1 = 0;
        int sum2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 10) {
                sum1 += nums[i];
            } else {
                sum2 += nums[i];
            }
        }
        return sum1 != sum2;

    }
}

B

经过一通猜测，质数的平方就是特殊数字，毫无疑问。

那么只需要预处理出来即可。

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
const int N=1e5+10;
bool inited = false, flag[N + 10];
vector<long long> vec;
void init() 
{
    if (inited) 
        return;
    inited = true;
    memset(flag, 0, sizeof(flag));
    for (int i = 2; i <= N; i++) if (!flag[i]) 
    {
        vec.push_back(1LL * i * i);
        //质数的平方
        for (int j = i * 2; j <= N; j += i) 
            flag[j] = true;
    }
}
class Solution 
{
public:
    int nonSpecialCount(int l, int r) 
    {
        init();
        int R = upper_bound(vec.begin(), vec.end(), r) - vec.begin();
        int L = lower_bound(vec.begin(), vec.end(), l) - vec.begin();
        //二分出特殊数字
        return (r - l + 1) - (R - L);//正难则反
    }
};

C

灵神太优雅了。

考虑到有一个平方性质，因此可以考虑枚举0的个数。

记作cnt0表示0的个数，cnt1表示1的个数，那么显然有cnt0<=cnt1<=n

因此就有cnt0<=\(\sqrt{n}\)

枚举左端点left，然后枚举子串0的个数/

p 为从 left*开始的第 cnt0个 0 的下标，q为从 left 开始的第cnt0+1 个 0 的下标。

计算方式具体见代码解释：

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
43
44
45
46
47
48
49
50
class Solution 
{
public:
    int numberOfSubstrings(string s)
    {
        int n = s.length();
        vector<int> a;
        for (int i = 0; i < n; i++) 
        {
            if (s[i] == '0') 
            {
                a.push_back(i);
                //放入每个0的下标
            }
        }

        int tot1 = n - a.size();
        //所有1的个数，方便在1永远没有办法比0大的时候 break
        a.push_back(n); // 哨兵

        int ans = 0, i = 0; // >= left 的第一个 0 的下标是 a[i]
        for (int left = 0; left < n; left++) 
        {
            if (s[left] == '1') 
            {
                ans += a[i] - left; // 不含 0 的子串个数
                //注意a[i]表示left后第一个0出现的位置
            }
            for (int k = i; k < a.size() - 1; k++) 
            {
                int cnt0 = k - i + 1;
                if (cnt0 * cnt0 > tot1) 
                {
                    break;
                    //上面提到的break
                }
                int cnt1 = a[k] - left - (k - i);
                ans += max(a[k + 1] - a[k] - max(cnt0 * cnt0 - cnt1, 0), 0);
            }
            if (s[left] == '0') 
            {
                i++; 
                // 这个 0 后面不会再枚举到了
            }
        }
        return ans;
    }
};