leetcode biweekly contest 92

前三题确实是太简单了，最后一题稍微有点奥数的思想。

6249. 分割圆的最少切割次数

圆内一个 有效切割 ，符合以下二者之一：

该切割是两个端点在圆上的线段，且该线段经过圆心。
该切割是一端在圆心另一端在圆上的线段。

一些有效和无效的切割如下图所示。

给你一个整数 n ，请你返回将圆切割成相等的 n 等分的最少切割次数。

示例 1：

输入：n = 4
输出：2
解释：
上图展示了切割圆 2 次，得到四等分。

示例 2：

输入：n = 3
输出：3
解释：
最少需要切割 3 次，将圆切成三等分。
少于 3 次切割无法将圆切成大小相等面积相同的 3 等分。
同时可以观察到，第一次切割无法将圆切割开。

提示：

1 <= n <= 100

地址

https://leetcode.cn/contest/biweekly-contest-92/problems/minimum-cuts-to-divide-a-circle/

题意

数学

思路

对称性的问题，如果 $n$ 能被 $2$ 整除，此时我们可以先从中切一次，将园等分为两部分，剩余的等分则刚好两遍半圆的等分次数相等即可，因此当 $n$ 为偶数时此时需要的最少此时为 $\dfrac{n}{2}$，否则为 $n$。特殊情况需要考虑，当 $n= 1$时，此时不需要任何切分。
复杂度分析：

时间复杂度：$O(1)$。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    int numberOfCuts(int n) {
        if (n == 1) {
            return 0;
        }
        if (n % 2 == 0) {
            return n / 2;
        } else {
            return n;
        }        
    }
};

6277. 行和列中一和零的差值

给你一个下标从 0 开始的 m x n 二进制矩阵 grid 。

我们按照如下过程，定义一个下标从 0 开始的 m x n 差值矩阵 diff ：

令第 i 行一的数目为 onesRowi 。
令第 j 列一的数目为 onesColj 。
令第 i 行零的数目为 zerosRowi 。
令第 j 列零的数目为 zerosColj 。
diff[i][j] = onesRowi + onesColj - zerosRowi - zerosColj

请你返回差值矩阵 diff 。

示例 1：

输入：grid = [[0,1,1],[1,0,1],[0,0,1]]
输出：[[0,0,4],[0,0,4],[-2,-2,2]]
解释：
- diff[0][0] = onesRow0 + onesCol0 - zerosRow0 - zerosCol0 = 2 + 1 - 1 - 2 = 0 
- diff[0][1] = onesRow0 + onesCol1 - zerosRow0 - zerosCol1 = 2 + 1 - 1 - 2 = 0 
- diff[0][2] = onesRow0 + onesCol2 - zerosRow0 - zerosCol2 = 2 + 3 - 1 - 0 = 4 
- diff[1][0] = onesRow1 + onesCol0 - zerosRow1 - zerosCol0 = 2 + 1 - 1 - 2 = 0 
- diff[1][1] = onesRow1 + onesCol1 - zerosRow1 - zerosCol1 = 2 + 1 - 1 - 2 = 0 
- diff[1][2] = onesRow1 + onesCol2 - zerosRow1 - zerosCol2 = 2 + 3 - 1 - 0 = 4 
- diff[2][0] = onesRow2 + onesCol0 - zerosRow2 - zerosCol0 = 1 + 1 - 2 - 2 = -2
- diff[2][1] = onesRow2 + onesCol1 - zerosRow2 - zerosCol1 = 1 + 1 - 2 - 2 = -2
- diff[2][2] = onesRow2 + onesCol2 - zerosRow2 - zerosCol2 = 1 + 3 - 2 - 0 = 2

示例 2：

输入：grid = [[1,1,1],[1,1,1]]
输出：[[5,5,5],[5,5,5]]
解释：
- diff[0][0] = onesRow0 + onesCol0 - zerosRow0 - zerosCol0 = 3 + 2 - 0 - 0 = 5
- diff[0][1] = onesRow0 + onesCol1 - zerosRow0 - zerosCol1 = 3 + 2 - 0 - 0 = 5
- diff[0][2] = onesRow0 + onesCol2 - zerosRow0 - zerosCol2 = 3 + 2 - 0 - 0 = 5
- diff[1][0] = onesRow1 + onesCol0 - zerosRow1 - zerosCol0 = 3 + 2 - 0 - 0 = 5
- diff[1][1] = onesRow1 + onesCol1 - zerosRow1 - zerosCol1 = 3 + 2 - 0 - 0 = 5
- diff[1][2] = onesRow1 + onesCol2 - zerosRow1 - zerosCol2 = 3 + 2 - 0 - 0 = 5

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 105
1 <= m * n <= 105
grid[i][j] 要么是 0 ，要么是 1 。

地址

https://leetcode.cn/contest/biweekly-contest-92/problems/difference-between-ones-and-zeros-in-row-and-column/

题意

直接模拟

思路

直接模拟即可，我们求出每一行与每一列中 $1$ 的个即可，然后按照题目要求进行模拟即可。
$$
res[i][j] = 2 * onesRow[i] + 2 * onesCol[j] - m - n
$$
复杂度分析：

时间复杂度：$O(m\times n)$，其中 $m,n$ 为矩阵的行数与列数。
空间复杂度：$O(m + n)$，其中 $m,n$ 为矩阵的行数与列数。

代码

class Solution {
public:
    vector<vector<int>> onesMinusZeros(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<int> onesRow(m);
        vector<int> onesCol(n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                onesRow[i] += grid[i][j];
                onesCol[j] += grid[i][j];
            }
        }
        vector<vector<int>> res(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res[i][j] =  2 * onesRow[i] + 2 * onesCol[j] - m - n;
            }
        }
        return res;
    }
};

6250. 商店的最少代价

给你一个顾客访问商店的日志，用一个下标从 0 开始且只包含字符 'N' 和 'Y' 的字符串 customers 表示：

如果第 i 个字符是 'Y' ，它表示第 i 小时有顾客到达。
如果第 i 个字符是 'N' ，它表示第 i 小时没有顾客到达。

如果商店在第 j 小时关门（0 <= j <= n），代价按如下方式计算：

在开门期间，如果某一个小时没有顾客到达，代价增加 1 。
在关门期间，如果某一个小时有顾客到达，代价增加 1 。

请你返回在确保代价最小的前提下，商店的最早关门时间。

注意，商店在第 j 小时关门表示在第 j 小时以及之后商店处于关门状态。

示例 1：

输入：customers = "YYNY"
输出：2
解释：
- 第 0 小时关门，总共 1+1+0+1 = 3 代价。
- 第 1 小时关门，总共 0+1+0+1 = 2 代价。
- 第 2 小时关门，总共 0+0+0+1 = 1 代价。
- 第 3 小时关门，总共 0+0+1+1 = 2 代价。
- 第 4 小时关门，总共 0+0+1+0 = 1 代价。
在第 2 或第 4 小时关门代价都最小。由于第 2 小时更早，所以最优关门时间是 2 。

示例 2：

输入：customers = "NNNNN"
输出：0
解释：最优关门时间是 0 ，因为自始至终没有顾客到达。

示例 3：

输入：customers = "YYYY"
输出：4
解释：最优关门时间是 4 ，因为每一小时均有顾客到达。

提示：

1 <= customers.length <= 105
customers 只包含字符 'Y' 和 'N' 。

地址

https://leetcode.cn/contest/biweekly-contest-92/problems/minimum-penalty-for-a-shop/

题意

滑动窗口

思路

我们设商店营业到小时 $i$ 的开门代价为 $cost_1[i]$，我们设商店从小时 $i$ 开始关门的关门代价为 $cost_2[i]$。我们知道当商店从 $i$ 开始关门的总代价为 $cost[i] = cost_1[i-1] + cost_2[i]$，我们找到最小的 $cost$ 即可，本质为一个前缀和的问题，可以将空间复杂度优化到 $O(1)$
复杂度分析

时间复杂度：时间复杂度为 $O(n)$，$n$ 数组的长度。
空间复杂度：空间复杂度为 $O(1)$ 。

代码

class Solution {
public:
    int bestClosingTime(string customers) {
        int cost = 0;
        for (auto c : customers) {
            cost += c == 'Y' ? 1 : 0;
        }
        int res = 0;
        int minCost = cost;
        for (int i = 0; i < customers.size(); i++) {
            if (customers[i] == 'N') {
                cost += 1;
            } else {
                cost -= 1;
            }
            if (cost < minCost) {
                res = i + 1;
                cost = minCost;
            }
        }
        return res;
    }
};

6251. 统计回文子序列数目

给你数字字符串 s ，请你返回 s 中长度为 5 的 回文子序列 数目。由于答案可能很大，请你将答案对 109 + 7 取余后返回。

提示：

如果一个字符串从前往后和从后往前读相同，那么它是 回文字符串 。
子序列是一个字符串中删除若干个字符后，不改变字符顺序，剩余字符构成的字符串。

示例 1：

输入：s = "103301"
输出：2
解释：
总共有 6 长度为 5 的子序列："10330" ，"10331" ，"10301" ，"10301" ，"13301" ，"03301" 。
它们中有两个（都是 "10301"）是回文的。

示例 2：

输入：s = "0000000"
输出：21
解释：所有 21 个长度为 5 的子序列都是 "00000" ，都是回文的。

示例 3：

输入：s = "9999900000"
输出：2
解释：仅有的两个回文子序列是 "99999" 和 "00000" 。

提示：

1 <= s.length <= 104
s 只包含数字字符。

地址

https://leetcode.cn/contest/biweekly-contest-92/problems/count-palindromic-subsequences/

题意

动态规划

思路

典型的动态规划，重点在于题目的提示如下：

回文字符串的长度为 $5$;
字符串中只包含数字；
枚举每个字符作为回文字符串中心，则左右两遍的字符串的范围为 $\text{00}-\text{99}$，此时最多只有 $100$ 种可能，因此我们只需要统计以每个字符串左右两遍能构成字符串 $x, x \in [0,99]$ 的数目即可。此时我们可以利用动态规划:

设 $dp_1[i][j]$ 表示前 $i$ 个字符中含有的字符 $j$ 的数目，$dp_2[i][a\times 10 + b]$ 表示前 $i$ 个字符中含有的形成的字符串 $\text{ab}$ 的数目，则此时我们可以得到递推公式:
$$
dp_1[i][j] = dp_1[i-1][j] + 1 \quad if \quad nums[i] = j \
dp_1[i][j] = dp_1[i-1][j] \quad if \quad nums[i] \neq j \
dp_2[i][a\times 10 + b] = dp_2[i-1][a\times 10 + b] + dp_2[i-1][a] \quad if \quad nums[i] = b \
dp_2[i][a\times 10 + b] = dp_2[i-1][a\times 10 + b]\quad if \quad nums[i] \neq b \
$$

非常容易理解的动态规划即可求的左右两遍构成字符串 $x$ 的数目，设 $l(i-1, x)$ 表示从 $i$ 的左边构成字符串 $x$ 的数目，设 $r(i-1, x)$ 表示从 $i$ 的右边边构成字符串 $x$ 的数目，则此时我们可以得到递推公式如下:
$$
tot = \sum_{i=2}^{n-3}\sum_{j = 0}^{99}l(i-1,j) \times r(i+1,j)
$$
3. 复杂度分析：

时间复杂度：$O(n \times |\Sigma|^2)$，其中 $n$ 表示给定的字符串的长度, $|\Sigma|$ 表示给定的字符集的大小，在这里字符集为数字，此时 $|\Sigma| = 10$。
空间复杂度：$O(n \times |\Sigma|^2)$，其中 $n$ 表示给定的字符串的长度, $|\Sigma|$ 表示给定的字符集的大小，在这里字符集为数字，此时 $|\Sigma| = 10$。

代码

class Solution {
public:
    int countPalindromes(string s) {
        long long mod = 1e9 + 7;
        int n = s.size();
        vector<long long> L1(10), R1(10);
        vector<vector<long long>> L2(n + 1, vector<long long>(100));
        vector<vector<long long>> R2(n + 1, vector<long long>(100));
        for (int i = 0; i < n; i++) {
            L2[i + 1] = L2[i];
            for (int j = 0; j <= 9; j++) {
                L2[i + 1][j * 10 + s[i] - '0'] = (L2[i + 1][j * 10 + s[i] - '0'] + L1[j]) % mod;
            }
            L1[s[i] - '0']++;
        }
        for (int i = n - 1; i >= 0; i--) {
            R2[i] = R2[i + 1];
            for (int j = 0; j <= 9; j++) {
                R2[i][j * 10 + s[i] - '0'] = (R2[i][j * 10 + s[i] - '0'] + R1[j]) % mod;
            }
            R1[s[i] - '0']++;
        }
        long long res = 0;
        for (int i = 2; i <= n - 3; i++) {
            for (int j = 0; j < 100; j++) {
                res = (res + L2[i][j] * R2[i + 1][j]) % mod;
            }
        }
        return res;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛

← leetcode contest 319 leetcode contest 321 →

扫描二维码，分享此文章