Python 刷 Leetcode 1/30 | Python 主题月

写在前面

本文正在参加「Python主题月」，详情查看活动链接

这个月是 Python 活动月，我决定尝试用 Python 来刷这 30 天的每日一题和随机一题。然后如果周末有精力，我想捣鼓捣鼓这个python-patterns

每日一题 1/30

LCP 07. 传递信息

动态规划的状态 dp[i][j] 为经过 i 轮传递到编号 j 的玩家的方案数，其中 0 <= i <= k, 0 <= j <= n。

从编号 0 的玩家开始传递，边界情况就是 dp[0][0] = 1，其他的 dp[0][j] = 0。

然后来写状态转移方程：

dp[i + 1][dst] = dp[i][src_1] + dp[i][src_2] + dp[i][src_3] + ...

最后总方案是 dp[k][n - 1]

然后来写代码：


class Solution:
    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:
        dp = [[0] * (n + 1) for _ in range(k + 1)]
        dp[0][0] = 1
        for i in range(k):
            for edge in relation:
                src = edge[0]
                dst = edge[1]
                dp[i + 1][dst] += dp[i][src]
        return dp[k][n - 1]

复制代码

emmm 我明天不拿这个语言刷算法题了，我直接进设计模式了，这个写着感觉不舒服。回归正题，上面的代码还能优化空间，因为状态总是从上一轮传来。优化以后是这样的


class Solution:
    def numWays(self, n: int, relation: List[List[int]], k: int) -> int:
        dp = [0 for _ in range(n + 1)]
        dp[0] = 1
        for i in range(k):
            next = [0 for _ in range(n + 1)]
            for edge in relation:
                src = edge[0]
                dst = edge[1]
                next[dst] += dp[src]
            dp = next
        return dp[n - 1]

复制代码

随机一题 1/30

919. 完全二叉树插入器

又是二叉树，这次是完全二叉树，这种特殊的二叉树有一些性质，比如说节点按照层次遍历顺序编号，知道了父亲节点可以很容易推出左右孩子节点的编号，这道题就需要这个性质。代码看图写话即可。


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class CBTInserter:

    def __init__(self, root: TreeNode):
        self.node_list = [None]
        queue = [root]
        while queue:
            node = queue.pop(0)
            self.node_list.append(node)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    def insert(self, v: int) -> int:
        self.node_list.append(TreeNode(v))
        idx = len(self.node_list) - 1
        father = self.node_list[idx//2]
        if idx % 2 == 0:
            father.left = self.node_list[-1]
        else:
            father.right = self.node_list[-1]
        return father.val

    def get_root(self) -> TreeNode:
        return self.node_list[1]

# Your CBTInserter object will be instantiated and called as such:
# obj = CBTInserter(root)
# param_1 = obj.insert(v)
# param_2 = obj.get_root()

复制代码