This is the second day of my participation in the August Text Challenge.More challenges in August

1. Algorithm problem:leetcode687. The longest path with the same value

Method: Recursion

You can think of any path (nodes with the same value) as at most two arrows extending from its root. Specifically, the root of a path will be the only node, so the parent of that node will not appear in the path, and the arrow will be a path where the root has only one child node in the path. And then, for each node, we want to know what is the longest arrow that goes left and the longest arrow that goes right? We can solve this problem recursively.

Let arrow_length(node) be the length of the longest arrow extending from node node. If node.Left exists and has the same value as node, the value will be 1 + arrow_length(node.left). The same is true in the presence of Node. right.

When we calculate the length of the arrow, the candidate answer will be the sum of the arrows of the node in both directions. We record these candidate answers and return the best answer.

The code is as follows:

class Solution(object):
    def longestUnivaluePath(self, root):
        self.ans = 0


        def arrow_length(node):
            if not node: return 0
            left_length = arrow_length(node.left)
            right_length = arrow_length(node.right)
            left_arrow = right_arrow = 0
            if node.left and node.left.val == node.val:
                left_arrow = left_length + 1
            if node.right and node.right.val == node.val:
                right_arrow = right_length + 1
            self.ans = max(self.ans, left_arrow + right_arrow)
            return max(left_arrow, right_arrow)


        arrow_length(root)
        return self.an
Copy the code

Time complexity: O(N), where N is the number of nodes in the tree.

Space complexity: O(H), where H is the height of the tree.

See more update all the interview questions, July online interview question > > > www.julyedu.com/questions/w…

2. Algorithm problem:leetcode322. Change

Full backpack problem – How many coins are required to fill a backpack of amount capacity

Dp [j] stands for: The minimum number of coins needed to fill a backpack of capacity J

Initialize the DP array: because the number of coins must not exceed amount and amount <= 10^4, initialize the array to 10001; dp[0] = 0

Transfer equation: DP [J] = min(DP [J], DP [J] + 1)

Minimum coins needed to fill capacity j = min(minimum coins needed to fill capacity J before, minimum coins needed to fill capacity J-coin + 1 current coin)

Return dp[amount]. If dp[amount] is 10001 and has not changed, no coin combination can be found and -1 is returned

The code is as follows:

class Solution: def coinChange(self, coins: List[int], amount: int) -> int: dp = [0] + [10001] * amount for coin in coins: for j in range(coin, amount + 1): dp[j] = min(dp[j], dp[j - coin] + 1) return dp[-1] if dp[-1] ! = 10001 else -1Copy the code

Time complexity: O(n * amount)

Space complexity: O(amount)