[LeetCode周赛复盘] 第 92 场双周赛20221015

一、本周周赛总结

• 没打，但T4不会。
• T2模拟。
• T3前后缀分解。
• T4前后缀分解。

二、 [Easy] 6249. 分割圆的最少切割次数

链接: 6249. 分割圆的最少切割次数

1. 题目描述

2. 思路分析

• 1的话不用切。
• 奇数必须奇数刀。
• 偶数可以对半切。

3. 代码实现

class Solution:
    def numberOfCuts(self, n: int) -> int:
        if n == 1:
            return 0
        if n &1:
            return n
        return n//2
1
2
3
4
5
6
7

三、[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]*n
        rows = [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-n
        return diff
1
2
3
4
5
6
7
8
9
10
11
12
13

四、[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 - Y
        a =b=0
        ans = mn = inf
        for i in range(n):
            c = b+Y-a
            if c < mn:
                ans = i 
                mn = c
            
            a+=customers[i]=='Y'             
            b+=customers[i]=='N'
        c = b+Y-a
        if c < mn:
            ans = n
            mn = c 
        
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

五、[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]*10
        suf2 = [0]*100
        for v in s:
            for d,c in enumerate(suf1):
                suf2[d*10+v] += c
            suf1[v] += 1
        pre1 = [0]*10
        pre2 = [0]*100
        ans = 0
        for v in s:
            suf1[v] -= 1
            for d,c in enumerate(suf1):
                suf2[v*10+d] -= c
            for i in range(10):
                for j in range(10):
                    ans += suf2[i*10+j] * pre2[j*10+i]
                    ans %= MOD
            for d,c in enumerate(pre1):
                pre2[d*10+v] += c
            pre1[v]+=1
        return ans
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

六、参考链接