leetcodeブラシ問題記録481-490 python版

前言
leetcodeブラシの生涯を続けてここに記録されているのは、筆者が少し面白いと思っている方法です.何人かの大物の問題解を参考にしました.特にpowcai大物とlabuladong大物、ありがとうございました.
481.不思議な文字列

class Solution:
    def magicalString(self, n: int) -> int:
        if n==0:return 0
        string = '122'
        i = 2
        char = 2
        ones=1
        while len(string) < n:
            char = 2 - char // 2
            if char==1:
                ones+=int(string[i])
            string += int(string[i])*str(char)
            i+=1
        return ones-1 if char==1 and len(string)>n else ones

482.鍵のフォーマット

class Solution:
    def licenseKeyFormatting(self, S: str, K: int) -> str:
        S = ''.join(S.upper().split('-'))
        m, n = len(S) % K, len(S) // K
        sl = '-'.join([S[m+i*K:m+(i+1)*K] for i in range(n)])
        if m == 0:
            return sl
        if n == 0:
            return S[:m]
        return S[:m] + '-' + sl

483.最小好進法

import math
class Solution:
    def smallestGoodBase(self, n: str) -> str:
        if n == 1: return '1'
        n = int(n)
        max_k = int(math.log2(n) + 1)
        for k in range(max_k, 1, -1):
            x = int(n ** (1/(k-1)))
            while x >= 2:
                if x ** k - 1 == (x - 1) * n and x != 1:
                    return str(x)
                if (x**k -1) / (x-1) < n:
                    break
                x -= 1
        # k    2  x   ，x     n-1 
        return str(n-1)

485.最大連続1の個数

class Solution:
    def findMaxConsecutiveOnes(self, nums: List[int]) -> int:
        res, cnt = 0, 0
        for num in nums + [0]:
            if num == 0:
                res = max(cnt, res)
                cnt = 0
            else:
                cnt += 1
        return res

486.予測勝者

# dp
class Solution:
    def PredictTheWinner(self, nums) -> bool:
        n = len(nums)
        if n<= 2:
            return True
        dp = [[0] * n for _ in range(n)]
        for i in range(n):
            dp[i][i] = nums[i]  #         
        for k in range(1, n):  #k  j-i   
            for i in range(0, n - k):
                dp[i][i + k] = max(sum(nums[i + 1:i + k + 1]) - dp[i + 1][i + k] + nums[i],
                                   sum(nums[i:i + k]) - dp[i][i + k - 1] + nums[i + k])
        if dp[0][n - 1] >=(0.5 * sum(nums)):
            return True
        else:
            return False
# dp
class Solution:
    def PredictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [[0]*n for _ in range(n)]
        #         1   ，      nums[i]，      0，            nums[i]
        for i in range(n):
            dp[i][i] = nums[i]
        # i   i+1,    
        for i in range(n-2, -1, -1):
            # j   j-1,    ，  j>i
            for j in range(i+1, n, 1):
                dp[i][j] = max( nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])
        return dp[0][n-1] >= 0

488.ズマゲーム

#   +  
import functools
class Solution:
    def findMinStep(self, board: str, hand: str) -> int:
        codes = {"R": 10000, "Y": 1000, "B": 100, "G": 10, "W": 1}
        def encode(char_count):
            result = 0
            for c in char_count:
                result += codes[c] * char_count[c]
            return result
        def decode(value):
            chars = "WGBYR"
            idx = 0
            result = {"W": 0, "G": 0, "B": 0, "Y": 0, "R": 0}
            while value > 0:
                result[chars[idx]] = value % 10
                value //= 10
                idx += 1
            return result
        @functools.lru_cache(None)
        def findMin(board, hand_code):
            if not board:
                return 0
            steps = float("inf")
            hand_count = decode(hand_code)
            same_count = 1
            idx = 1
            while idx <= len(board):
                if idx == len(board) or board[idx] != board[idx - 1]:
                    last_char = board[idx - 1]
                    if same_count + hand_count[last_char] >= 3:
                        #   same_count    3，         ，shoot 0
                        shoot = max(0, 3 - same_count)
                        # last_char                
                        hand_count[last_char] -= shoot
                        #     + shoot =       
                        steps = min(steps, findMin(board[:idx - same_count] + board[idx:], encode(hand_count)) + shoot)
                        #   
                        hand_count[last_char] += shoot
                    same_count = 1
                else:
                    same_count += 1
                idx += 1
            return steps
        hand_code = 0
        for c in hand:
            hand_code += codes[c]
        result = findMin(board, hand_code)
        return -1 if result == float("inf") else result
#        ，       ，