2020-2-25 刷题总结

0X00 leetcode 做了 4 道

• leetcode 279. Perfect Squares
• leetcode 132. Palindrome Partitioning II
• leetcode 292. Nim Game
• leetcode 322. Coin Change

0X01 每道题的小小记录

今天主要做了「划分型动态规划」两道,一道「博弈型动态规划」一道 比较简单的动态规划

279. Perfect Squares

像这种划分数字的,划分字符串的,可以考虑「划分型动态规划」

class Solution:
    def numSquares(self, n: int) -> int:
        # 划分形动态规划
        # f(x) = min[f(x - 1 * 1), f(x - 2 * 2), ..., f(x- j * j)] + 1

        record = [0] * (n+1)

        for x in range(1, n+1):
            t = float("inf")
            j = 1
            while j*j <= x:
                if t > record[x - j*j]:
                    t = record[x - j*j]
                j += 1

            record[x] = t + 1 

        return record[x]

132. Palindrome Partitioning II

class Solution:
    def minCut(self, s: str) -> int:
        # 用动态规划做
        # 最后状态
        # 长度为 n 的字符串,所用的最少回文 f(n) = 
        # 其中 j 是 n-j~n 是回文的字符 min(f(n-1), min(n-j), ...) + 1
        
        if s == "": return 0
        m, n  = len(s), len(s)
        self.isPalin = [[False for _ in range(m)] for _ in range(n)]
        self.findAll(s)
        record = [0] * (m+1)

        for x in range(1, m+1):
            record[x] = float("inf")
            for j in range(x):
                if self.isPalin[j][x-1]:
                    record[x] = min(record[x], record[j] + 1)
        
        return record[-1] - 1

    def findAll(self, s):
        m = len(s)
        # odd 
        for c in range(m):
            i = j = c
            while i > -1 and j < m and s[i] == s[j]:
                self.isPalin[i][j] = True
                i -= 1
                j += 1
        
        # even
        for c in range(m-1):
            i = c
            j = c + 1
            while i > -1 and j < m and s[i] == s[j]:
                self.isPalin[i][j] = True
                i -= 1
                j += 1

这里积累一个找所有回文的模板:

def findAll(self, s):
        m = len(s)
        # odd 
        for c in range(m):
            i = j = c
            while i > -1 and j < m and s[i] == s[j]:
                self.isPalin[i][j] = True
                i -= 1
                j += 1
        
        # even
        for c in range(m-1):
            i = c
            j = c + 1
            while i > -1 and j < m and s[i] == s[j]:
                self.isPalin[i][j] = True
                i -= 1
                j += 1

292. Nim Game

博弈型动态规划,关键在于:找到让对手必败的状态.而且思考的方式不是最后一步,而是第一步

但是用过动态规划做超时了...

class Solution:
    def canWinNim(self, n: int) -> bool:
        # 动态规划去做这个题目
        # 初始状态 1, 2, 3 都是 True
        # 接下来的状态看能不能转换到必败的状态
        # 如果不能,那么自己必败
        
        if n<= 3: return True
        a = b = c = True
        for i in range(4, n+1):
            t = False if a and b and c else True
            a, b, c = b, c, t

        return c

因为有一个数学规律,所以写成:

class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0

322. Coin Change

一道比较简单的动态规划

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if len(coins) == 0: return -1

        record = [0] * (amount+1)

        def helper(idx):
            if idx == 0: return 0
            if idx < 0: return float("inf")
            return record[idx]

        for i in range(1, amount+1):
            record[i] = min([helper(i - v) for v in coins]) + 1
        
        return -1 if record[amount] == float("inf") else record[amount]