Python brush Leetcode | Python theme on 1/30

Writing in the front

This article is participating in Python Theme Month. See the link to the event for more details

This month is Python Activity Month, and I decided to try my hand at using Python to do one question a day and one random question for 30 days. And then if I have the energy on the weekend, I want to play around with this Python-patterns

One question per day 1/30

LCP 07. Pass the message

The state dp[I][j] of dynamic programming is the number of schemes passed to the player numbered j after I round, where 0 <= I <= k, 0 <= j <= n.

Starting from the player with the number 0, the boundary case is dp[0][0] = 1, and the other dp[0][j] = 0.

Then write the state transition equation:

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

The final overall scheme is DP [k][n-1]

Then write the code:

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]

Copy the code

Emmm I will not take this language brush algorithm problem tomorrow, I will go directly to design mode, this says feel uncomfortable. Back to the point, the above code also optimizes the space because the state is always coming from the previous round. This is what it looks like after optimization

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]

Copy the code

One random problem: 1/30

919. Complete binary tree inserter

Again, a binary tree, this time a complete binary tree, this particular binary tree has some properties, such as nodes are numbered in order of hierarchical traversal, knowing that the parent node can easily derive the number of the left and right child nodes, this problem requires this property. Code can see the picture to write words.

# 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()

Copy the code

summary

A new challenge to brush with Python 3 (update design patterns tomorrow, this language brush is not interesting)

reference

There is no