Ukg | OAMaster

01Minimum Flips to Match Expected Binary Values in a Tree

You are given an undirected tree with tree_nodes nodes, numbered from 0 to tree_nodes - 1, and rooted at node 0. Each node initially has a binary value (0 or 1) given by the array initial[], and an expected binary value given by the array expected[]. You can perform the following operation any number of times: Pick a node u and flip its value along with all nodes v in the subtree of u where v % 2 == u % 2. Flipping a value means toggling between 0 and 1. Find the minimum number of operations needed so that the final binary values match expected[].

Example 1

Input:

tree_nodes = 4
tree_from = [0, 0, 1]
tree_to = [1, 2, 3]
initial = [1, 1, 0, 1]
expected = [0, 1, 1, 0]

Output:

Explanation: Pick node 0 and flip it → initial = [0, 1, 1, 1] Pick node 3 and flip it → initial = [0, 1, 1, 0] (matches expected)

Example 2

Input:

tree_nodes = 5
tree_from = [0, 1, 0, 1]
tree_to = [1, 2, 3, 4]
initial = [1, 0, 1, 1, 0]
expected = [1, 1, 0, 1, 1]

Output:

Explanation: :O

解法

DFS 自顶向下，按节点编号奇偶性分别累计已经施加的翻转次数 flipsEven 和 flipsOdd。当前节点真实值 = initial[v] XOR (v 偶数对应的累计 flips 奇偶)。若不等于期望值，则需要在此节点触发一次操作：把对应奇偶性的 flips 加 1，操作数 +1。复杂度 O(n)，空间 O(n)。

from typing import List
import sys

def min_flips_in_tree(tree_nodes: int, tree_from: List[int], tree_to: List[int],
                       initial: List[int], expected: List[int]) -> int:
    sys.setrecursionlimit(200000)
    g = [[] for _ in range(tree_nodes)]
    for u, v in zip(tree_from, tree_to):
        g[u].append(v); g[v].append(u)
    ans = 0
    seen = [False] * tree_nodes
    def dfs(u, parent, flips_even, flips_odd):
        nonlocal ans
        my_flips = flips_even if u % 2 == 0 else flips_odd
        cur = initial[u] ^ (my_flips & 1)
        if cur != expected[u]:
            ans += 1
            if u % 2 == 0:
                flips_even += 1
            else:
                flips_odd += 1
        for nxt in g[u]:
            if nxt != parent:
                dfs(nxt, u, flips_even, flips_odd)
    dfs(0, -1, 0, 0)
    return ans

import java.util.*;

class Solution {
    int ans = 0;
    List<List<Integer>> g;

    int minFlipsInTree(int treeNodes, int[] treeFrom, int[] treeTo, int[] initial, int[] expected) {
        g = new ArrayList<>();
        for (int i = 0; i < treeNodes; i++) g.add(new ArrayList<>());
        for (int i = 0; i < treeFrom.length; i++) {
            g.get(treeFrom[i]).add(treeTo[i]);
            g.get(treeTo[i]).add(treeFrom[i]);
        }
        dfs(0, -1, 0, 0, initial, expected);
        return ans;
    }

    private void dfs(int u, int parent, int flipsEven, int flipsOdd, int[] initial, int[] expected) {
        int myFlips = (u % 2 == 0) ? flipsEven : flipsOdd;
        int cur = initial[u] ^ (myFlips & 1);
        if (cur != expected[u]) {
            ans++;
            if (u % 2 == 0) flipsEven++;
            else flipsOdd++;
        }
        for (int v : g.get(u)) if (v != parent) dfs(v, u, flipsEven, flipsOdd, initial, expected);
    }
}

class Solution {
public:
    int ans = 0;
    vector<vector<int>> g;

    int minFlipsInTree(int treeNodes, vector<int>& treeFrom, vector<int>& treeTo,
                       vector<int>& initial, vector<int>& expected) {
        g.assign(treeNodes, {});
        for (size_t i = 0; i < treeFrom.size(); ++i) {
            g[treeFrom[i]].push_back(treeTo[i]);
            g[treeTo[i]].push_back(treeFrom[i]);
        }
        dfs(0, -1, 0, 0, initial, expected);
        return ans;
    }

private:
    void dfs(int u, int parent, int flipsEven, int flipsOdd,
             vector<int>& initial, vector<int>& expected) {
        int myFlips = (u % 2 == 0) ? flipsEven : flipsOdd;
        int cur = initial[u] ^ (myFlips & 1);
        if (cur != expected[u]) {
            ++ans;
            if (u % 2 == 0) ++flipsEven; else ++flipsOdd;
        }
        for (int v : g[u]) if (v != parent) dfs(v, u, flipsEven, flipsOdd, initial, expected);
    }
};

02Number of Duplicates

You are given a list of products, where each product has a name, price, and weight. Your task is to determine how many duplicate products are in the list. A duplicate product is defined as a product that has the same name, price, and weight as another product in the list. Function Parameters: name: A list of strings where name[i] represents the name of the product at index i. price: A list of integers where price[i] represents the price of the product at index i. weight: A list of integers where weight[i] represents the weight of the product at index i. Returns: An integer denoting the number of duplicate products in the list. Constraints

1 ≤ n ≤ 10⁵
1 ≤ price[i], weight[i] ≤ 1000
name[i] consists of lowercase English letters (a-z) and has at most 10 characters.

解法

用 (name, price, weight) 作哈希表 key 统计计数；重复个数 = 对每个 key max(0, cnt - 1) 求和(每超出 1 个就算一个重复实例)。复杂度 O(n)，空间 O(n)。

from typing import List
from collections import Counter

def num_duplicates(name: List[str], price: List[int], weight: List[int]) -> int:
    cnt = Counter(zip(name, price, weight))
    return sum(max(0, c - 1) for c in cnt.values())

import java.util.*;

class Solution {
    int numDuplicates(String[] name, int[] price, int[] weight) {
        Map<String, Integer> cnt = new HashMap<>();
        for (int i = 0; i < name.length; i++) {
            String key = name[i] + "|" + price[i] + "|" + weight[i];
            cnt.merge(key, 1, Integer::sum);
        }
        int dup = 0;
        for (int c : cnt.values()) dup += Math.max(0, c - 1);
        return dup;
    }
}

class Solution {
public:
    int numDuplicates(vector<string>& name, vector<int>& price, vector<int>& weight) {
        unordered_map<string, int> cnt;
        for (size_t i = 0; i < name.size(); ++i) {
            string key = name[i] + "|" + to_string(price[i]) + "|" + to_string(weight[i]);
            cnt[key]++;
        }
        int dup = 0;
        for (auto& [k, c] : cnt) dup += max(0, c - 1);
        return dup;
    }
};