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
class Solution {
public long maximumValueSum(int[] nums, int k, int[][] edges) {
int n = nums.length;
int[] diff = new int[n];
long sum = 0;
for (int i = 0; i < n; i++) {
sum += nums[i];
diff[i] = (nums[i] ^ k) - nums[i];
}
Arrays.sort(diff);
int index = n - 1;
while (index >= 1 && diff[index] + diff[index - 1] > 0) {
sum += diff[index] + diff[index - 1];
index -= 2;
}
return sum;
}
}
class Solution:
def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
n = len(nums)
even = 0
odd = -math.inf
for num in nums:
xorNum = num ^ k
newOdd = max(odd + num, even + xorNum)
newEven = max(even + num, odd + xorNum)
even, odd = newEven, newOdd
return even
k
trên hai phần tử kia, do tính chất của phép XORk
với hai phần tử bất kỳ trong cây là phép toán mở rộng, dựa vào những điểm trên, ta có thể tìm max bằng việc tìm ra cách ghép đôi các phần tử trong cây để sao cho với mỗi đôi chuyện áp dụng phép toán mở rộng luôn làm tăng tổng giá trị các phần tử trong đôi, và từ đó mà làm tăng tổng tất cả các phần tửk
giá trị đó lớn hơn so với giá trị đầu, tức là nums[i] < nums[i] ^ k
, và ghép những phần tử như vậy lại với nhau, ngoài ra phải chú ý thêm logic để xử lý khi tổng số những phần tử thỏa mãn tính chất đó là số lẻimpl Solution {
pub fn maximum_value_sum(nums: Vec<i32>, k: i32, edges: Vec<Vec<i32>>) -> i64 {
let n = nums.len();
let xor_diffs: Vec<i32> = nums.iter().map(|&num| (num ^ k) - num).collect();
let gain_count = xor_diffs.iter().filter(|&&val| val > 0).count();
let mut max =
nums.iter().zip(xor_diffs.iter()).fold(0i64, |mut acc, (&num, &gain)| {
if gain > 0 {
acc += (num + gain) as i64;
} else {
acc += num as i64;
}
acc
});
if gain_count % 2 == 0 {
return max;
}
let min_gain = *xor_diffs.iter().filter(|&&val| val > 0).min().unwrap() as i64;
if gain_count == n {
return max - min_gain;
}
let min_loss = *xor_diffs.iter().filter(|&&val| val <= 0).max().unwrap() as i64;
max = (max + min_loss).max(max - min_gain);
return max;
}
}