[LeetCode周赛复盘] 第 92 场双周赛20221015
- 一、本周周赛总结
- 二、 [Easy] 6249. 分割圆的最少切割次数
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 三、[Medium] 6277. 行和列中一和零的差值
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 四、[Medium] 6250. 商店的最少代价
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 五、[Hard] 6251. 统计回文子序列数目
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
- 六、参考链接
一、本周周赛总结
- 没打,但T4不会。
- T2模拟。
- T3前后缀分解。
- T4前后缀分解。
二、 [Easy] 6249. 分割圆的最少切割次数
链接: 6249. 分割圆的最少切割次数
1. 题目描述
2. 思路分析
- 1的话不用切。
- 奇数必须奇数刀。
- 偶数可以对半切。
3. 代码实现
class Solution:def numberOfCuts(self, n: int) -> int:if n == 1:return 0if n &1:return nreturn n//2
三、[Medium] 6277. 行和列中一和零的差值
链接: 66277. 行和列中一和零的差值
1. 题目描述
2. 思路分析
按题意模拟即可。
3. 代码实现
class Solution:def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]:m,n = len(grid),len(grid[0])cols = [0]*nrows = [sum(r) for r in grid]for i in range(m):for j in range(n):cols[j] += grid[i][j]diff = [[0]*n for _ in range(m)]for i in range(m):for j in range(n):diff[i][j] = rows[i]*2-m + cols[j]*2-nreturn diff
四、[Medium] 6250. 商店的最少代价
链接: 6250. 商店的最少代价
1. 题目描述
2. 思路分析
- 枚举在每个时间点关门前后的代价。
- 显然前边的代价就是前缀里N的个数。
- 后边的代价就是Y所有的个数-前缀里Y的个数。
3. 代码实现
class Solution:def bestClosingTime(self, customers: str) -> int:n = len(customers)Y = customers.count('Y')N = n - Ya =b=0ans = mn = inffor i in range(n):c = b+Y-aif c < mn:ans = i mn = ca+=customers[i]=='Y' b+=customers[i]=='N'c = b+Y-aif c < mn:ans = nmn = c return ans
五、[Hard] 6251. 统计回文子序列数目
链接: 6251. 统计回文子序列数目
1. 题目描述
2. 思路分析
- 由于长度是5,所以可以枚举所有位置作为中心点,左右各两个值。用乘法原理计算两边相同的值数量累加到答案中即可。
- 问题转化成对每个位置,前缀的2位组合以及后缀2位组合的数目快速求解。这可以用哈希表然后跟着枚举递推。
- 由于只有两位,用因此100长度的数组即可。
3. 代码实现
MOD = 10**9+7
class Solution:def countPalindromes(self, s: str) -> int:s = list(map(int,s))suf1 = [0]*10suf2 = [0]*100for v in s:for d,c in enumerate(suf1):suf2[d*10+v] += csuf1[v] += 1pre1 = [0]*10pre2 = [0]*100ans = 0for v in s:suf1[v] -= 1for d,c in enumerate(suf1):suf2[v*10+d] -= cfor i in range(10):for j in range(10):ans += suf2[i*10+j] * pre2[j*10+i]ans %= MODfor d,c in enumerate(pre1):pre2[d*10+v] += cpre1[v]+=1return ans