LeetCode Biweekly Contest 92

Problem 1#

找规律可以发现，n为奇数时，由于不对称，无法进行过圆心的切分，所以只能切n刀；n为偶数时，可以通过切n/2刀。特殊的是n=1时不需要切分。

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

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

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

Problem 2#

Problem 2

计数问题：计算每行每列的一的个数，剩下的位置就是零。对于每一个位置计算题中的公式即可。

1
class Solution:
2
    def onesMinusZeros(self, grid: List[List[int]]) -> List[List[int]]:
3
        n = len(grid)
4
        m = len(grid[0])
5
        r = [sum(grid[i]) for i in range(n)]
6
        c = [0 for _ in range(m)]
7
        for j in range(m):
8
            tmp = 0
9
            for i in range(n):
10
                tmp += grid[i][j]
11
            c[j] = tmp
12
        ans = [[0 for i in range(m)] for j in range(n)]
13
        for i in range(n):
14
            for j in range(m):
15
                ans[i][j] = r[i] + c[j] - (n + m - r[i] - c[j])
16
        return ans

时间复杂度： $O(nm)$

空间复杂度： $O(nm)$

Problem 3#

Problem 3

理解一下题意就是：如果选择在第x小时关门，则答案=1-x中的N的个数 + x-n中Y的个数，枚举x求出最小值即可。

1
class Solution:
2
    def bestClosingTime(self, customers: str) -> int:
3
        y = customers.count('Y')
4
        n = customers.count('N')
5
        ans, cost = -1, y
6
        tmp = 0
7
        cy, cn = 0, 0
8
        for i in range(len(customers)):
9
            if customers[i] == 'Y':
10
                cy += 1
11
            else:
12
                cn += 1
13
            if cost > cn + y - cy:
14
                cost = cn + y - cy
15
                ans = i
16
        return ans + 1

时间复杂度： $O(n)$

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

Problem 4#

Problem 4

如果问题中的子序列换成子数组还是非常简单的，直接枚举所有连续的长度为5的子串即可。

对于题目中的子序列，我们可以通过贡献的角度来考虑问题，首先回文串中间的字符是无所谓的，只需要前两个字符和后两个字符对称即可，因此我们可以枚举中间字符的位置pos，计算pos之前有多少个双字符ab和pos之后有多少个双字符ba，其中 $0 \leq a, b \leq 9$

灵神给出了一个优化空间复杂度的方法：Link

1
class Solution:
2
    def countPalindromes(self, s: str) -> int:
3
        suf = [0] * 10
4
        suf2 = [0] * 100
5
        for d in map(int, s[::-1]):
6
            for j, c in enumerate(suf):
7
                suf2[d * 10 + j] += c
8
            suf[d] += 1
9

10
        ans = 0
11
        prf = [0] * 10
12
        prf2 = [0] * 100
13
        for d in map(int, s):
14
            suf[d] -= 1
15
            for j, c in enumerate(suf):
16
                suf2[d * 10 + j] -= c
17
            ans += sum([c1 * c2 for c1, c2 in zip(prf2, suf2)])
18
            for j, c in enumerate(prf):
19
                prf2[d * 10 + j] += c
20
            prf[d] +=  1
21
        return ans % (10 ** 9 + 7)

时间复杂度： $O(n|\Sigma|^2)$ ， $\Sigma$ 表示字符集的大小，这里是10。

空间复杂度： $O(|\Sigma|^2)$