[Python3] 领扣第23场周赛 题解

P1 滑动数独

描述 给定一个$3\times n$ 的矩阵 number，并且该矩阵只含有1到9的正整数。 考虑有一个大小为 $3\times 3$ 滑动窗口，从左到右遍历该矩阵 number， 那么该滑动窗口在遍历整个矩阵的过程中会有n-2个。

现在你的任务是找出这些滑动窗口是否含有1到9的所有正整数 请返回一个长度为n-2的答案数组，如果第i个滑动窗口含有1到9的所有正整数，那么答案数组的第i个元素为true，否则为false

from functools import reduce class Solution: """ @param number: an only contains from 1 to 9 array @return: return whether or not each sliding window position contains all the numbers for 1 to 9 """ def SlidingWindows(self, number): # write your code here n, m = len(number), len(number[0]) pattern = (1 << 9) - 1 def fetch(i): ans = 0 for j in range(3): for x in number[j][i:i+3]: ans = ans | (1 << (x - 1)) return ans == pattern return [*map(fetch, range(m - 2))]

P2 字符串划分

描述 给出一个字符串，均为大写字母，将这个字符串划分成尽可能多的部分，使每种字母只会出现一个部分中。返回一个数组包含每个部分的长度。

import collections class Solution: """ @param s: a string @return: an array containing the length of each part """ def splitString(self, s): # write your code here. start = collections.defaultdict(int) end = collections.defaultdict(int) for i, ch in enumerate(s): end[ch] = i if ch not in start: start[ch] = i n, L, R = len(s), 0, end[s[0]] pre, ret = -1, [] while L < n: while L < R: L += 1 R = max(R, end[s[L]]) ret.append(L - pre) pre = L L += 1 if L < n: R = end[s[L]] return ret

P3 递增的数

描述 给你一个数字N,返回最大的比N小的且每一位是连续递增的数字 S.length $\le 1000$

class Solution: """ @param N: a positive integer N @return: return a maximum integer less than N, each digit of which must be monotonically increasing. """ def getIncreasingNumber(self, N): # write your code here if N > 123456789: return 123456789 if N < 10: return N - 1 s = list(map(lambda x: ord(x) - ord('0'), list(str(N)))) A = [x for x in range(1, 10)] def output(A): return int("".join(map(str, A))) def valid(A): return A == sorted(A) and len(set(A)) == len(A) # keep prefix as much as possible n = len(s) for i in range(n - 1, -1, -1): for dx in range(1, 10): B = s[0:i] + [s[i] - dx] + A[max(0, 10 - (n - i)):10] if valid(B): return output(B) return output(A[max(0, 10 - (n - 1)):10])

P4 恢复数组

描述 小九有一个长为 nn 的整型数组，数组中的每个数都在 ll 和 rr 之间，而且数组的和是 33 的整数倍。 请帮小九计算出这个数组一共有多少种不同的可能。 输出要对 $10^9+7$取模

class Solution: """ @param n: thne length of the array. @param l: the least limit for element. @param r: the largest limit for element. @return: return the ways to restore the array. """ def restoreArray(self, n, L, R): # write your code here. A = [0, 1, 2, 0, 1, 2] A = A[L % 3 :] N = R - L + 1 k = N % 3 mod = 10 ** 9 + 7 dp = [[0] * 3 for _ in range(n)] for i in range(3): dp[0][i] = N // 3 for k_ in range(k): dp[0][A[k_]] += 1 for i in range(1, n): dp[i][0] = dp[i - 1][0] * dp[0][0] + dp[i-1][1] * dp[0][2] + dp[i-1][2] * dp[0][1] dp[i][1] = dp[i - 1][0] * dp[0][1] + dp[i-1][1] * dp[0][0] + dp[i-1][2] * dp[0][2] dp[i][2] = dp[i - 1][0] * dp[0][2] + dp[i-1][1] * dp[0][1] + dp[i-1][2] * dp[0][0] for j in range(3): dp[i][j] = dp[i][j] % mod return dp[-1][0]