174. 地下城游戏

174. 地下城游戏

动态规划

class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        dp = [[float('inf') for i in range(len(dungeon[0]) + 1)] for j in range(len(dungeon) + 1)]
        dp[-2][-2] = dp[-1][-2] = dp[-2][-1] = 1
        for i in range(len(dungeon) - 1, -1, -1):
            for j in range(len(dungeon[i]) - 1, -1, -1):
                dp[i][j] = max(min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j], 1)
        for i in range(len(dp)):
            print(dp[i])
        return dp[0][0]

53. 最大子数组和

53. 最大子数组和

前缀和

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_val = float('-inf')
        min_val = float('inf')
        nums.insert(0, 0)
        for i in range(len(nums)):
            nums[i] = nums[i] + (nums[i - 1] if i - 1 >= 0 else 0)
            max_val = max(max_val, nums[i] - min_val)
            min_val = min(min_val, nums[i])
        # print(nums)
        return max_val

动态规划

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i] += max(nums[i - 1], 0)  # 如果前边累加后还不如自己本身大，那就把前边的都扔掉，从此自己本身重新开始累加。
        return max(nums)

605. 种花问题

605. 种花问题

贪心

class Solution:
    def canPlaceFlowers(self, flowerbed: List[int], n: int) -> bool:
        if n == 0:
            return True
        index = 0
        while index < len(flowerbed):
            if ((flowerbed[index + 1] == 0) if index + 1 < len(flowerbed) else True) and ((flowerbed[index - 1]) == 0 if index - 1 >= 0 else True) and flowerbed[index] == 0:
                n -= 1
                index += 2
                if n == 0:
                    return True
            else:
                index += 1
        return False

1079. 活字印刷

1079. 活字印刷

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        return self.recursion(tiles) - 1

    def recursion(self, s):
        ans = 1
        used = set()
        for i in range(len(s)):
            if s[i] not in used:
                ans += self.recursion(s[:i] + s[i + 1:])
                used.add(s[i])
        return ans

145. 二叉树的后序遍历

145. 二叉树的后序遍历

class Solution:
    def __init__(self):
        self.ans = []

    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        self.recursion(root)
        return self.ans

    def recursion(self, node):
        if node.left:
            self.recursion(node.left)
        if node.right:
            self.recursion(node.right)
        self.ans.append(node.val)

338. 比特位计数

338. 比特位计数

import math


class Solution:
    def countBits(self, n: int) -> List[int]:
        if n == 0:
            return [0]
        ans = [0 for i in range(n + 1)]
        ans[1] = 1
        for i in range(2, n + 1):
            x = int(math.log(i, 2))
            ans[i] = ans[i - 2 ** x] + 1
        return ans