2020-2-23 刷题记录

0X00 leetcode 做了 4 道

• leetcode 338. Counting Bits
• leetcode 265. Paint House II
• leetcode 198. House Robber
• leetcode 213. House Robber II

0X01 每道题的小小总结

338. Counting Bits

一个与位运算相关的动态规划

转移方程: f(x) = f(x >> 1) + (x & 1)

意思是当前数字的含 1 的个数 = 左移一位的个数 + 最后一位是不是 1

class Solution:
    def countBits(self, num: int) -> List[int]:
        nums = [0] * (num + 1)

        for i in range(num + 1):
            if i == 0: continue
            nums[i] = nums[i>>1] + (i & 1)

        return nums

265. Paint House II

Paint House 的进阶版有 K 种颜色

里面有一个 trick 就是来记录最小值和次小值

class Solution:
    def minCostII(self, costs: List[List[int]]) -> int:
        # 应该用模板去做题
        # 应该用最简单的办法掏出来

        if len(costs) < 1: return 0

        # 记录每一层的最小花费
        m, n = len(costs), len(costs[0])
        record = [[0] * n for _ in range(m+1)]

        for x in range(m+1):
            if x == 0: continue
            # 寻找上一层的最小和次小
            min1, min2 = float("inf"), float("inf")
            id1, id2 = 0, 0
            for y in range(n):
                if record[x-1][y] < min1:
                    min1, min2 = record[x-1][y], min1
                    id1, id2 = y, id1
                elif record[x-1][y] < min2:
                    min2 = record[x-1][y]
                    id2 = y
            if min2 == float("inf"):
                min2 = 0
            # 计算本层的最小 cost
            for y in range(n):
                if y != id1:
                    record[x][y] = costs[x-1][y] + min1
                else:
                    record[x][y] = costs[x-1][y] + min2
            
        
        return min(record[m])

一遍历找最小值和次小值

nums = [1]
min1 = min2 = float("inf")
for n in range(nums):
    if n < min1:
        min1, min2 = n, min1
    elif n < min2:
        min2 = n
if len(nums) == 1:
    min2 = min1

198. House Robber

一道需要记录状态的动态规划

class Solution:
    def rob(self, nums: List[int]) -> int:
        # 动态规划
        # 如果不打劫 f(x, 0) = f(x-1, 1)
        # 如果打劫 f(x, 1) = f(x-1, 0) + money(x)
        # 最后返回 max
        m, n = len(nums), 2
        record = [[0] * n for _ in range(m+1)]

        for i in range(m+1):
            if i == 0: continue
            record[i][0] = max(record[i-1][0], record[i-1][1]) 
            record[i][1] = record[i-1][0] + nums[i-1]
        

        return max(record[m])

213. House Robber II

将这道题转换成上面那道题

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 0:return 0
        if len(nums) == 1: return nums[0]
    
        # 分两种情况
        # 偷 0 与不偷 0
        m, n = len(nums), 2
        ans = 0
        record = [[0]*n for _ in range(m)]

        # 选择可以偷 0
        for x in range(m):
            if x == 0: continue
            record[x][0] = max(record[x-1][0], record[x-1][1])
            record[x][1] = record[x-1][0] + nums[x-1]
        
        ans = max(ans, record[m-1][0], record[m-1][1])

        record = [[0]*n for _ in range(m)]
        # 不选择偷 0
        for x in range(m):
            if x == 0: continue
            record[x][0] = max(record[x-1][0], record[x-1][1])
            record[x][1] = record[x-1][0] + nums[x]

        ans = max(ans, record[m-1][0], record[m-1][1])

        return ans