TBNv2
Senior Member
code này bị leak mem mà.10 năm rồi chưa code C++, viết vầy không rõ có bị leak không
code này bị leak mem mà.10 năm rồi chưa code C++, viết vầy không rõ có bị leak không
var removeLeafNodes = function(root, target) {
function recursion(node) {
if (!node) return false;
if (node.left && recursion(node.left)) node.left = null;
if (node.right && recursion(node.right)) node.right = null;
return !node.left && !node.right && node.val === target;
}
if (recursion(root)) {
return null;
}
return root;
};
Code:class Solution { public: TreeNode* removeLeafNodes(TreeNode*& root, int target) { if (!root) return root; removeLeafNodes(root->left, target); removeLeafNodes(root->right, target); if (!root->left && !root->right && root->val == target) { root = nullptr; } return root; } };
/**
* Example:
* var ti = TreeNode(5)
* var v = ti.`val`
* Definition for a binary tree node.
* class TreeNode(var `val`: Int) {
* var left: TreeNode? = null
* var right: TreeNode? = null
* }
*/
class Solution {
fun removeLeafNodes(root: TreeNode?, target: Int): TreeNode? {
if (root == null) {
return null
}
root.left = removeLeafNodes(root.left, target)
root.right = removeLeafNodes(root.right, target)
return if (root.left == null && root.right == null && root.`val` == target) {
null
} else {
root
}
}
}
C-like:/** * Example: * var ti = TreeNode(5) * var v = ti.`val` * Definition for a binary tree node. * class TreeNode(var `val`: Int) { * var left: TreeNode? = null * var right: TreeNode? = null * } */ class Solution { fun removeLeafNodes(root: TreeNode?, target: Int): TreeNode? { if (root == null) { return null } root.left = removeLeafNodes(root.left, target) root.right = removeLeafNodes(root.right, target) return if (root.left == null && root.right == null && root.`val` == target) { null } else { root } } }
Mỗi node 1 coin nên chỉ cần so sánh số coin nó hold với số nodes của mỗi sub tree là ra được số lượng move đến root của sub tree đó. Làm tương tự, đệ quy với các subtree nhỏ hơn. => Bài này chỉ cần viết đệ quy bt thôiNhìn AC xong hí hửng, đọc đề xong ko có ý tưởng gì luôn đệt mẹ
Bài này giải bằng backtracking thì đơn giản cơ mà constrain này thì ko backtracking được rồi
class Solution:
def distributeCoins(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if not node:
return 0,0,0
l_num_nodes, l_num_coins, l_num_move = dfs(node.left)
r_num_nodes, r_num_coins, r_num_move = dfs(node.right)
num_nodes = l_num_nodes + r_num_nodes + 1
num_coins = l_num_coins + r_num_coins + node.val
num_move = abs(l_num_nodes - l_num_coins) + abs(r_num_nodes - r_num_coins) + l_num_move + r_num_move
return num_nodes, num_coins, num_move
return dfs(root)[2]
class Solution:
def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
@lru_cache(None)
def dp(i, mask):
if i == n:
return 0
ans = inf
for j in range(n):
if (mask >> j) & 1 == 0:
current = nums1[i]^nums2[j]
ans = min(ans, current + dp(i + 1, mask|(1 << j)))
return ans
return dp(0, 0)
class Solution:
def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
@lru_cache(None)
def dp(i, mask):
if i == n:
return 0
ans = inf
for j in range(n):
if (mask >> j) & 1 == 0:
ans = min(ans, nums1[i]^nums2[j] + dp(i + 1, mask|(1 << j)))
return ans
return dp(0, 0)
Hay quá fence, mình nghĩ ko ra xem solution luôn rồiMỗi node 1 coin nên chỉ cần so sánh số coin nó hold với số nodes của mỗi sub tree là ra được số lượng move đến root của sub tree đó. Làm tương tự, đệ quy với các subtree nhỏ hơn. => Bài này chỉ cần viết đệ quy bt thôi
Python:class Solution: def distributeCoins(self, root: Optional[TreeNode]) -> int: def dfs(node): if not node: return 0,0,0 l_num_nodes, l_num_coins, l_num_move = dfs(node.left) r_num_nodes, r_num_coins, r_num_move = dfs(node.right) num_nodes = l_num_nodes + r_num_nodes + 1 num_coins = l_num_coins + r_num_coins + node.val num_move = abs(l_num_nodes - l_num_coins) + abs(r_num_nodes - r_num_coins) + l_num_move + r_num_move return num_nodes, num_coins, num_move return dfs(root)[2]
class Solution {
public int[] divideAndConquer(TreeNode root) {
if (root == null)
return new int[]{0, 1};
int[] lt = divideAndConquer(root.left);
int[] rt = divideAndConquer(root.right);
int[] res = new int[2];
int leftVal = root.left == null ? 1 : root.left.val;
int rightVal = root.right == null ? 1 : root.right.val;
res[0] = lt[0] + rt[0] + Math.abs(lt[1] - leftVal) + Math.abs(rt[1] - rightVal);
res[1] = lt[1] + rt[1] - leftVal - rightVal + 1;
return res;
}
public int distributeCoins(TreeNode root) {
int[] res = divideAndConquer(root);
return res[0];
}
}
class Solution {
int move =0;
public int distributeCoins(TreeNode root) {
dfs(root);
return move;
}
private int dfs(TreeNode node){
if(node == null ) return 0;
int left =dfs(node.left);
int right=dfs(node.right);
move+= Math.abs(left);
move+= Math.abs(right);
return node.val - (1-left-right) ;
}
}
def distribute_coins(root)
node_count_tree = node_count(root)
coin_count_tree = coin_count(root)
distribute_coins_helper(root, node_count_tree, coin_count_tree)
end
def distribute_coins_helper(node, node_count_tree, coin_count_tree)
transfer_count = 0
if node.left
transfer_count += (coin_count_tree.left.val - node_count_tree.left.val).abs
transfer_count += distribute_coins_helper(node.left, node_count_tree.left, coin_count_tree.left)
end
if node.right
transfer_count += (coin_count_tree.right.val - node_count_tree.right.val).abs
transfer_count += distribute_coins_helper(node.right, node_count_tree.right, coin_count_tree.right)
end
transfer_count
end
def node_count(node)
return nil if node.nil?
left = node_count(node.left)
right = node_count(node.right)
TreeNode.new(
(left&.val || 0) + (right&.val || 0) + 1,
left,
right
)
end
def coin_count(node)
return nil if node.nil?
left = coin_count(node.left)
right = coin_count(node.right)
TreeNode.new(
(left&.val || 0) + (right&.val || 0) + node.val,
left,
right
)
end
def distribute_coins(node)
_, _, transfers = distribute_coins_helper(node)
transfers
end
def distribute_coins_helper(node)
return [0, 0, 0] if node.nil?
left_count, left_coins, left_transfers = distribute_coins_helper(node.left)
right_count, right_coins, right_transfers = distribute_coins_helper(node.right)
return [
left_count + right_count + 1,
left_coins + right_coins + node.val,
left_transfers + right_transfers + (left_coins - left_count).abs + (right_coins - right_count).abs
]
end
object Solution {
def distributeCoins(root: TreeNode): Int = {
val (_, moves) = dfs(root)
moves
}
def dfs(node: TreeNode): (Int, Int) = {
if (node == null) (0, 0)
else {
val (leftExcess, leftMoves) = dfs(node.left)
val (rightExcess, rightMoves) = dfs(node.right)
val totalExcess = node.value + leftExcess + rightExcess - 1
val totalMoves = leftMoves + rightMoves + Math.abs(leftExcess) + Math.abs(rightExcess)
(totalExcess, totalMoves)
}
}
}
class Solution:
def distributeCoins(self, root: Optional[TreeNode]) -> int:
moves = 0
def distribute(root):
if not root:
return 0
nonlocal moves
leftCoins = distribute(root.left)
rightCoins = distribute(root.right)
moves += abs(leftCoins) + abs(rightCoins)
return leftCoins + rightCoins + root.val - 1
distribute(root)
return moves
class Solution:
def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
ret, count_xor, diff = 0, 0, inf
for num in nums:
num_xor = num ^ k
ret += max(num, num_xor)
count_xor += int(num_xor > num)
diff = min(diff, abs(num - num_xor))
return ret if count_xor%2 == 0 else ret - diff