首页 > 其他分享 >[leetcode每日一题]6.12

[leetcode每日一题]6.12

时间:2023-06-12 12:32:04浏览次数:40  
标签:node int 6.12 每日 节点 pa TreeAncestor getKthAncestor leetcode

1483. 树节点的第 K 个祖先

提示

困难

150

相关企业

给你一棵树,树上有 n 个节点,按从 0 到 n-1 编号。树以父节点数组的形式给出,其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。

树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。

实现 TreeAncestor 类:

  • TreeAncestor(int n, int[] parent) 对树和父数组中的节点数初始化对象。
  • getKthAncestor(int node, int k) 返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点,返回 -1 。

 

示例 1:

[leetcode每日一题]6.12_LCA

输入:
["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

输出:
[null,1,0,-1]

解释:
TreeAncestor treeAncestor = new TreeAncestor(7, [-1, 0, 0, 1, 1, 2, 2]);

treeAncestor.getKthAncestor(3, 1);  // 返回 1 ,它是 3 的父节点
treeAncestor.getKthAncestor(5, 2);  // 返回 0 ,它是 5 的祖父节点
treeAncestor.getKthAncestor(6, 3);  // 返回 -1 因为不存在满足要求的祖先节点

 

提示:

  • 1 <= k <= n <= 5 * 104
  • parent[0] == -1 表示编号为 0 的节点是根节点。
  • 对于所有的 0 < i < n ,0 <= parent[i] < n 总成立
  • 0 <= node < n
  • 至多查询 5 * 104 次

Solution

第一次接触LCA算法。思想有点类似快速幂,先进行离线处理,之后按照位的思想进行运算即可。

class TreeAncestor:

    def __init__(self, n: int, parent: List[int]):
        m = n.bit_length() - 1
        pa = [[p] + [-1] * m for p in parent]
        for i in range(m):
            for j in range(n):
                if (p := pa[j][i]) != -1:
                    pa[j][i + 1] = pa[p][i]
        self.pa = pa

    def getKthAncestor(self, node: int, k: int) -> int:
        bit = 0
        while k and node != -1:
            if k & 1:
                node = self.pa[node][bit]
            bit += 1
            k >>= 1
        return node


# Your TreeAncestor object will be instantiated and called as such:
# obj = TreeAncestor(n, parent)
# param_1 = obj.getKthAncestor(node,k)

标签:node,int,6.12,每日,节点,pa,TreeAncestor,getKthAncestor,leetcode
From: https://blog.51cto.com/u_15763108/6461435

相关文章

  • 二刷Leetcode-Days10
    1.二叉树/***102.BinaryTree的层序遍历(借助辅助队列实现,递归法pass)*@paramroot*@return*/publicList<List<Integer>>levelOrder(TreeNoderoot){List<List<Integer>>resList=newArrayList<>();......
  • 2023.6.12 树节点的第k个祖先
    可以借鉴一下求LCA问题中的倍增思想。用fa[i][j]表示i号节点的第\(2^j\)个祖先。我们只需要用动态规划预处理出这个fa数组即可。求第k个祖先,可以将k用二进制拼凑的方法划分成若干个2的整数次幂,然后利用fa数组对应地进行若干次跳跃即可,单个询问的时间复杂度\(O(logn)\)。这里由......
  • 二叉搜索二叉搜索树-leetcode-700
    给定二叉搜索树(BST)的根节点root和一个整数值val。你需要在BST中找到节点值等于val的节点。返回以该节点为根的子树。如果节点不存在,则返回null。示例1:输入:root=[4,2,7,1,3],val=2输出:[2,1,3]示例2:输入:root=[4,2,7,1,3],val=5输出:[]提示:数中节点......
  • 【LeetCode.384打乱数组】Knuth洗牌算法详解
    前两天看网易面筋得知网易云的随机歌曲播放使用了这个算法,遂找题来做做学习一下打乱数组https://leetcode.cn/problems/shuffle-an-array/给你一个整数数组nums,设计算法来打乱一个没有重复元素的数组。打乱后,数组的所有排列应该是等可能的。实现Solutionclass:Solution......
  • [leetcode第349场周赛]心得
    已经连续4次周赛三题了,再这么下去肯定不行,感觉需要进行自救了。6470. 既不是最小值也不是最大值提示简单1相关企业给你一个整数数组 nums ,数组由 不同正整数 组成,请你找出并返回数组中 任一 既不是 最小值 也不是 最大值 的数字,如果不存在这样的数字,返回 -1 。返回所......
  • LeetCode hints
    通过样例得到一些通用性质,从单点出发结合要求什么,初步判断可以应用什么算法,之前见没见过类似的,见过就转换成之前会做的,怎么转换需要思考。想不出来可以先出朴素的算法,然后才考虑优化正着推不行就倒着推结果和顺序无关就可以sort数组,复杂的需要sortindex(由小到大排序且保持原......
  • 【每日一题】Problem 363B. Fence
    原题解决思路求k个木板的最小高度和,因为所有木板的高度和不超过1e9,因此计算出到当前木板j的总高度-前j-k模板的总高度并求得最小数即可#include<bits/stdc++.h>intmain(){intn,k;std::cin>>n>>k;std::vector<int>vec(n+1,0);for(in......
  • leetcode 1171. 从链表中删去总和值为零的连续节点
    给你一个链表的头节点 head,请你编写代码,反复删去链表中由总和 值为0的连续节点组成的序列,直到不存在这样的序列为止。删除完毕后,请你返回最终结果链表的头节点。你可以返回任何满足题目要求的答案。(注意,下面示例中的所有序列,都是对 ListNode 对象序列化的表示。)示例1:输入:he......
  • Leetcode 1171. 从链表中删去总和值为零的连续节点
    题目:给你一个链表的头节点 head,请你编写代码,反复删去链表中由总和 值为0的连续节点组成的序列,直到不存在这样的序列为止。删除完毕后,请你返回最终结果链表的头节点。你可以返回任何满足题目要求的答案。(注意,下面示例中的所有序列,都是对 ListNode 对象序列化的表示。)难......
  • LeetCode 双周赛 106(2023/06/10)两道思维题
    本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]加入知识星球提问。往期回顾:LeetCode单周赛第348场·数位DP模版学会了吗?双周赛106概览T1.判断一个数是否迷人(Easy)标签:计数T2.找到最长的半重复子字符串(Medium)标签:同向双指针T3.移动机......