Leetcode 第 408 场周赛题解

Leetcode 第 408 场周赛题解

题目1：3232. 判断是否可以赢得数字游戏

思路

用一个 sum1 统计个位数的和，sum2 统计十位数的和。

只要 sum1 和 sum2 不相等，Alice 拿大的就能赢得这场游戏。

代码

/*
 * @lc app=leetcode.cn id=3232 lang=cpp
 *
 * [3232] 判断是否可以赢得数字游戏
 */

// @lc code=start
class Solution
{
public:
    bool canAliceWin(vector<int> &nums)
    {
        int sum1 = 0, sum2 = 0;
        for (int &num : nums)
        {
            if (num / 10)
                sum2 += num;
            else
                sum1 += num;
        }
        return sum1 != sum2;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(n)，其中 n 是数组 nums 的长度。

空间复杂度：O(1)。

题目2：3233. 统计不是特殊数字的数字数量

思路

埃式筛 + 计数

正难则反，统计区间 [l,r] 内有多少个特殊数字。

这等价于区间 [0, r] 内的特殊数字个数，减去区间 [0, l−1] 内的特殊数字个数。

代码

/*
 * @lc app=leetcode.cn id=3233 lang=cpp
 *
 * [3233] 统计不是特殊数字的数字数量
 */

// @lc code=start
const int MX = 31622; // floor(sqrt(10^9))
bool inited = false;
vector<int> pi(MX + 5, 0);

// 埃氏筛 O(Mlog(logM))
void init()
{
    if (inited)
        return;
    for (int i = 2; i <= MX; i++)
    {
        if (pi[i] == 0)
        { // i 没有被标记，i 是质数
            pi[i] = pi[i - 1] + 1;
            for (int j = i * i; j <= MX; j += i)
            { // 标记 i 的倍数为合数
                pi[j] = -1;
            }
        }
        else
        {
            pi[i] = pi[i - 1];
        }
    }
    inited = true;
}

class Solution
{
public:
    int nonSpecialCount(int l, int r)
    {
        init();
        return r - l + 1 - (pi[(int)sqrt(r)] - pi[(int)sqrt(l - 1)]);
    }
};

// @lc code=end

复杂度分析

时间复杂度：O(1)。不计入预处理的时间。

空间复杂度：O(1)。不计入预处理的空间。

题目3：3234. 统计 1 显著的字符串的数量

思路

注意到，如果子串中的 0 非常多，多到 0 的个数的平方比 1 的个数都要大，那么这样的子串必然不是 1 显著子串。

设 cnt0 为子串中的 0 的个数，cnt1 为子串中的 1 的个数，那么必须满足：cnt0 * cnt0 <= cnt1 <= n，所以子串中的 0 的个数不会超过 sqrt(n)。

代码

/*
 * @lc app=leetcode.cn id=3234 lang=cpp
 *
 * [3234] 统计 1 显著的字符串的数量
 */

// @lc code=start
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);

        int tot1 = n - a.size();
        a.push_back(n); // 哨兵

        int ans = 0, i = 0; // >= left 的第一个 0 的下标是 a[i]

        // 枚举子串左端点
        for (int left = 0; left < n; left++)
        { // 枚举子串有多少个 0
            // 枚举 0 的下标
            for (int k = i; k < a.size() - 1; k++)
            {
                int cnt0 = k - i + 1;
                if (cnt0 * cnt0 > tot1)
                    break;
                int p = a[k], q = a[k + 1];
                int cnt1 = a[k] - left - (k - i);
                if (cnt1 >= cnt0 * cnt0)
                {
                    // p, p+1, ..., q-1 都可以作为子串的右端点
                    ans += q - p;
                }
                else
                {
                    // cnt1 的个数少，补充 cnt0 * cnt0 - cnt1 个
                    ans += max(q - p - (cnt0 * cnt0 - cnt1), 0);
                }
            }
            // 没有 0 的情况
            if (s[left] == '0')
            {
                i++; // 这个 0 后面不会再枚举到了
            }
            else
            {
                ans += a[i] - left; // 不含 0 的子串个数
                tot1--;
            }
        }
        return ans;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(n * sqrt(n))，其中 n 是字符串 s 的长度。

空间复杂度：O(n)，其中 n 是字符串 s 的长度。

题目4：3235. 判断矩形的两个角落是否可达

思路

如果从矩形【上边界/左边界】到矩形【右边界/下边界】的路被圆堵死，则无法从矩形左下角移动到矩形右上角。

怎么判断呢？

首先考虑圆心都在矩形内部的情况。如果圆和圆相交或相切，则相当于在两个圆之间架起了一座桥。如果圆和矩形边界相交或相切，则相当于在矩形边界和圆之间架起了一座桥。如果可以从矩形【上边界/左边界】通过桥到达矩形【右边界/下边界】，则说明路被堵死，无法从矩形左下角移动到矩形右上角。

也可以把桥理解成切割线，如果能把从矩形左下角到矩形右上角的路径切断，则无法从矩形左下角移动到矩形右上角。

用图论的术语来说，就是把圆抽象成节点，在相交或相切的节点之间连边，得到一张无向图。如果从与【上边界/左边界】相交的节点出发，DFS 这张图，到达与【右边界/下边界】相交的节点，则说明无法从矩形左下角移动到矩形右上角。

从与矩形【上边界/左边界】相交/相切的圆开始 DFS。

如果当前 DFS 到了圆 i：

先判断其是否与矩形【右边界/下边界】相交或相切，如果是，则 DFS 返回 true。
否则，判断其是否与其他圆 j 相交或相切，如果是，则判断点 A 是否严格在矩形内，如果在，则递归 j，如果收到了 true，则 DFS 返回 true。
最后，如果最外层调用 DFS 的地方收到了 true，则表示无法从矩形左下角移动到矩形右上角，返回 false。

代码实现时，可以在递归之前，特判圆包含矩形左下角或者矩形右上角的情况，此时可以直接返回 false。

代码

/*
 * @lc app=leetcode.cn id=3235 lang=cpp
 *
 * [3235] 判断矩形的两个角落是否可达
 */

// @lc code=start
class Solution
{
    // 判断点 (x, y) 是否在圆 (ox, oy, r) 内
    bool in_circle(long long ox, long long oy, long long r, long long x, long long y)
    {
        return (ox - x) * (ox - x) + (oy - y) * (oy - y) <= r * r;
    }

public:
    bool canReachCorner(int X, int Y, vector<vector<int>> &circles)
    {
        int n = circles.size();
        vector<int> vis(n);
        auto dfs = [&](auto &&dfs, int i) -> bool
        {
            long long x1 = circles[i][0], y1 = circles[i][1], r1 = circles[i][2];
            // 圆 i 是否与矩形右边界/下边界相交相切
            if (y1 <= Y && abs(x1 - X) <= r1 ||
                x1 <= X && y1 <= r1 ||
                x1 > X && in_circle(x1, y1, r1, X, 0))
            {
                return true;
            }
            vis[i] = true;
            for (int j = 0; j < n; j++)
            {
                long long x2 = circles[j][0], y2 = circles[j][1], r2 = circles[j][2];
                // 在两圆相交相切的前提下，点 A 是否严格在矩形内
                if (!vis[j] && (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= (r1 + r2) * (r1 + r2) &&
                    x1 * r2 + x2 * r1 < (r1 + r2) * X &&
                    y1 * r2 + y2 * r1 < (r1 + r2) * Y &&
                    dfs(dfs, j))
                {
                    return true;
                }
            }
            return false;
        };
        for (int i = 0; i < n; i++)
        {
            long long x = circles[i][0], y = circles[i][1], r = circles[i][2];
            if (in_circle(x, y, r, 0, 0) || // 圆 i 包含矩形左下角
                in_circle(x, y, r, X, Y) || // 圆 i 包含矩形右上角
                // 圆 i 是否与矩形上边界/左边界相交相切
                !vis[i] && (x <= X && abs(y - Y) <= r || y <= Y && x <= r || y > Y && in_circle(x, y, r, 0, Y)) && dfs(dfs, i))
            {
                return false;
            }
        }
        return true;
    }
};
// @lc code=end

复杂度分析

时间复杂度：O(n²)，其中 n 是数组 circles 的长度。

空间复杂度：O(n)，其中 n 是数组 circles 的长度。