link: https://leetcode.com/problems/distribute-coins-in-binary-tree/
定義dfs函數,計算以node為root的subtree,扣掉每個child node需要的1枚硬幣後,總共會多(或少)幾枚硬幣。
如果硬幣有多,回傳值就是正的;如果硬幣有缺,回傳值就是負的;剛剛好不多不缺的情況,回傳值為0。
dfs函數顯示,node最少還需要幾枚硬幣(缺硬幣的情況),或著node至少要給出幾枚硬幣(多硬幣的情況),才能達成題目要求的硬幣分布。
假設parent node會滿足node的這個最低需求,通過計算parent node <-> node的硬幣流量,就能得知最少的移動步數。
# 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 Solution:
def distributeCoins(self, root: Optional[TreeNode]) -> int:
self.moves = 0
def dfs(node):
if node is None:
return 0
coins = dfs(node.left) + dfs(node.right) + node.val - 1
self.moves += abs(coins)
return coins
dfs(root)
return self.moves
官方解答。
前一個方法是計算自己到parent node的硬幣流量,這個方法是計算小孩到自己的硬幣流量,考慮到邊界case:dfs(root)和dfs(None)都為0,兩個方法等效。
# 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 Solution:
def distributeCoins(self, root: Optional[TreeNode]) -> int:
self.ans = 0
def dfs(node):
if not node: return 0
L, R = dfs(node.left), dfs(node.right)
self.ans += abs(L) + abs(R)
return node.val + L + R - 1
dfs(root)
return self.ans
leetcode
link: https://leetcode.com/problems/
Feb 9, 2024Difficulty: Easy link: https://leetcode.com/problems/linked-list-cycle/ 1. Hash table $O(n)$ runtime, $O(n)$ space 用set紀錄看過的node,如果有重複就代表有cycle。 python # Definition for singly-linked list. # class ListNode:
Dec 28, 2022Difficulty: Medium link: https://leetcode.com/problems/permutations/ 1. Backtracking $O(n!)$ runtime, $O(n)$ space 需要列出所有排列數,可以用backtracking。用take紀錄有沒有拿過nums的第i個元素。 python class Solution: def permute(self, nums: List[int]) -> List[List[int]]:
Nov 26, 2022Difficulty: Medium link: https://leetcode.com/problems/permutations-ii/ 1. Backtracking $O(n!)$ runtime, $O(n)$ space 用Counter記錄每個數字出現了幾次,在排列時同個數字就會當成同一類。 python class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]:
Nov 26, 2022or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up