[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]