周赛笔记234

一、字符串中不同整数的数目

class Solution:
    def numDifferentIntegers(self, word: str) -> int:
        s=""
        for i in word:
            if i.isalpha():
                s+=" "
            else:
                s+=i
        li=set([int(_) for _ in s.split()])
        return len(li)

二、还原排列的最少操作步数

class Solution:
    def reinitializePermutation(self, n: int) -> int:
        arr=[0]*n
        perm=[i for i in range(n)]
        
        def op(arr,perm,n):
            for i in range(n):
                if i%2: 
                    arr[i] = perm[n // 2 + (i - 1) // 2]
                else: 
                    arr[i] = perm[i // 2]
        
        cnt=0
        while 1:
            cnt+=1
            op(arr,perm,n)
            perm=arr.copy()
            if perm==[i for i in range(n)]:
                break
        
        return cnt

三、替换字符串中的括号内容

class Solution:
    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:
        dic={k:v for k,v in knowledge}
        ans=""
        n=len(s)
        i=0
        while i<n:
            if s[i]=="(":
                tmp=""
                for j in range(i+1,n):
                    if s[j]!=")":
                        tmp+=s[j]
                    else:
                        if tmp not in dic:
                            ans+="?"
                            break
                        ans+=dic[tmp]
                        break
                i=j+1
            else:
                ans+=s[i]
                i+=1
        return ans

四、好因子的最大数目

class Solution:
    def maxNiceDivisors(self, n: int) -> int:
        mod=10**9+7
        if n <= 3:
            return n
        if n % 3 == 1:
            return 4 * pow(3, (n - 4) // 3, mod) % mod
        elif n % 3 == 2:
            return 2 * pow(3, n // 3, mod) % mod
        else:
            return pow(3, n // 3, mod)

#题目意思：求n（因子个数）的拆分最大乘积【n>3】

#pow()第三个参数可以对结果取余
#不加入的话超出时间限制...

#写的时候竟然记起了：reduce(lambdax,y:x*y,nums)

一个变形：343.整数拆分
给定一个正整数 n，将其拆分为 至少两个 正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

#方法一：纯动态规划
class Solution:
    def integerBreak(self, n: int) -> int:
        dp=[0]*(n+1)
        for i in range(2,n+1):
            for j in range(i):
                dp[i]=max(dp[i],j*(i-j),j*dp[i-j])
        return dp[n]

#方法二：数学
#归纳证明得出：应拆分成尽可能多的 3
class Solution:
    def integerBreak(self, n: int) -> int:
        if n<=3: return n-1
        quotient,remainder = n//3,n%3
        if remainder==0: return 3**quotient
        elif remainder==1: return 3**(quotient-1)*4
        else: return 3**quotient*2