列表

详情

2445. 值为 1 的节点数

有一个 无向 树，有 n 个节点，节点标记为从 1 到 n ，还有 n - 1 条边。给定整数 n。标记为 v 的节点的父节点是标记为 floor (v / 2) 的节点。树的根节点是标记为 1 的节点。

你还得到一个整数数组 queries。最初，每个节点的值都是 0。对于每个查询 queries[i]，您应该翻转节点标记为 queries[i] 的子树中的所有值。

在 处理完所有查询后，返回值为 1 的节点总数。

注意:

 

示例 1:

输入: n = 5 , queries = [1,2,5]
输出: 3
解释: 上图显示了执行查询后的树结构及其状态。蓝色节点表示值 0，红色节点表示值 1。
在处理查询之后，有三个红色节点 (值为 1 的节点): 1、3、5。

示例 2:

输入: n = 3, queries = [2,3,3]
输出: 1
解释: 上图显示了执行查询后的树结构及其状态。蓝色节点表示值 0，红色节点表示值 1。
在处理查询之后，有一个红色节点 (值为 1 的节点): 2。

 

提示:

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int numberOfNodes(int n, vector<int>& queries) { } };

golang 解法, 执行用时: 128 ms, 内存消耗: 8.3 MB, 提交时间: 2023-10-16 23:23:31 

func numberOfNodes(n int, queries []int) int {
    nodes := make([]bool, n+1)
    for i := range queries{
        nodes[queries[i]] = !nodes[queries[i]]
    }
    ans := 0
    for i := range nodes{
        if i == 0{
            continue
        }
        if i == 1{
            if nodes[i]{
                ans++
            }
            continue
        }
        // 需要更新状态
        if (!nodes[i/2] && nodes[i]) || (nodes[i/2] && !nodes[i]){
            nodes[i] = true
            ans++
        }else{
            nodes[i] = false
        }
    }
    return ans
}

rust 解法, 执行用时: 8 ms, 内存消耗: 3.5 MB, 提交时间: 2023-10-16 23:23:04 

impl Solution {
    pub fn number_of_nodes(n: i32, queries: Vec<i32>) -> i32 {
        use std::collections::HashMap;
        fn dfs(q: &Vec<i32>, node: usize, father_val: i32) -> i32 {
            if node < q.len() {
                let val = (father_val + q[node]) & 1;
                let mut ans = dfs(q, 2 * node, val);
                ans += dfs(q, 2 * node + 1, val);
                ans + val
            } else {
                0
            }
        }
        let mut q = vec![0; n as usize + 1];
        queries.into_iter().for_each(|x| q[x as usize] += 1);
        dfs(&q, 1, 0)
    }

    pub fn number_of_nodes2(n: i32, mut queries: Vec<i32>) -> i32 {
        fn dfs(t: &mut Vec<i32>, i: usize) {
            let len = t.len();
            t[i] ^= 1;
            if 2 * i < len {
                dfs(t, 2 * i);
            }
            if 2 * i + 1 < len {
                dfs(t, 2 * i + 1);
            }
        }
        let mut t = vec![0; n as usize + 1];
        let mut i = 0;
        queries.sort_unstable();
        for j in 0..queries.len() {
            if queries[i] == queries[j] {
                continue;
            }
            if (j - i) & 1 != 0 {
                dfs(&mut t, queries[i] as usize);
            }
            i = j;
        }
        if (queries.len() - i) & 1 != 0 {
            dfs(&mut t, queries[i] as usize);
        }
        t.into_iter().sum()
    }
}

java 解法, 执行用时: 8 ms, 内存消耗: 59.2 MB, 提交时间: 2023-10-16 23:22:18 

class Solution {
    public int numberOfNodes(int n, int[] queries) {
        int m = n % 2 == 1 ? n : n + 1, ans = 0;
        int[] nodes = new int[m + 1];
        for(int i : queries) nodes[i]++; 
        for(int i = 1; i <= m / 2; i++){ // for处理结束后，nodes[query]: 标号为 query 的结点的反转次数
            if(nodes[i] % 2 == 1) ans++; // 边推送边累计，如果反转次数是奇数，累计“1”
            nodes[i * 2] += nodes[i];
            nodes[i * 2 + 1] += nodes[i];
        } 
        for(int i = m / 2 + 1; i <= n; i++){ // 继续累积 m/2+1 之后的结点
            if(nodes[i] % 2 == 1) ans++; // 如果反转次数是奇数，累计“1”
        }
        return ans;
    }
}

cpp 解法, 执行用时: 612 ms, 内存消耗: 155.6 MB, 提交时间: 2023-10-16 23:21:54 

class Solution {
public:
    int numberOfNodes(int n, vector<int>& queries) {
        map<int, int> cnt;
        for (auto& q: queries) cnt[q]++;
        function<int(int, int)> dfs = [&] (int node, int c) -> int {
            if (node > n) return 0;
            int nc = (c + cnt[node]) % 2;
            int ans = nc;
            ans += dfs(node * 2, nc);
            ans += dfs(node * 2 + 1, nc);
            return ans;
        };
        return dfs(1, 0);
    }
};

python3 解法, 执行用时: 1020 ms, 内存消耗: 55 MB, 提交时间: 2023-10-16 23:21:42 

class Solution:
    def numberOfNodes(self, n: int, queries: List[int]) -> int:
        cnt = Counter(queries)
        
        def dfs(node: int, c: int) -> int:
            if node > n: return 0
            nc = (c + cnt[node]) % 2
            ans = nc
            ans += dfs(node * 2, nc)
            ans += dfs(node * 2 + 1, nc)
            return ans
            
        return dfs(1, 0)

上一题

© 2024 leetcode.cn