首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

树节点的第 K 个祖先(DP,倍增)

给你一棵树,树上有 n 个节点,按从 0 到 n-1 编号。树以父节点数组的形式给出,其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。...请你设计并实现 getKthAncestor(int node, int k) 函数,函数返回节点 node 的第 k 个祖先节点。如果不存在这样的祖先节点,返回 -1 。...树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。 示例: ?...-1 因为不存在满足要求的祖先节点 提示: 1 <= k <= n <= 5*10^4 parent[0] == -1 表示编号为 0 的节点是根节点。...意思是:要想找到 node 的距离 2^j 的祖先,先找到 node 的距离 2^(j - 1) 的祖先,然后,再找这个祖先的距离 2^(j - 1) 的祖先。

77420

两个节点的最近公共祖先_今日排列三21253

大家好,又见面了,我是你们的朋友全栈君。 原题链接 题目描述 如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。...输入格式 第一行包含三个正整数 N,M,SN,M,S,分别表示树的结点个数、询问的个数和树根结点的序号。...接下来 N-1N−1 行每行包含两个正整数 x, yx,y,表示 xx 结点和 yy 结点之间有一条直接连接的边(数据保证可以构成树)。...接下来 MM 行每行包含两个正整数 a, ba,b,表示询问 aa 结点和 bb 结点的最近公共祖先。 输出格式 输出包含 MM 行,每行包含一个正整数,依次为每一个询问的结果。...: query[u]){ int y = q.x,id = q.y; if(vis[y])res[id] = Find(y); //如果之前遍历过另一个节点

21830
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    算法练习(14)-二叉树中2个节点的最近公共祖先?

    比如这颗树,给定2个节点: 4、5 ,它们的最近公共祖先节点为2。类似的,如果是3、5,它们的最近公共祖先节点为1。...left : right; } 这个代码很短, 但不太好理解 , 先分析下一颗树中的2个节点X、Y,它们最近公共祖先的情况: 只会出现这2类情况: 1、节点X在Y的某1侧子树中(反过来也一样,...Y出现在X的某1侧子树中),即:1个节点就是另1个的最近公共祖先。...|| root == n2) //在左右子树遍历过程中,如果发现当前节点就是n1或n2,直接返回,因为下面的子节点,肯定不可能再是它俩的公共祖先节点了 ) {...X与Y汇聚于当前节点,这个节点就是最近的公共祖先。

    70610

    怎么找出电脑隐藏的软件(如何清理电脑隐藏软件)

    平时时间确实太忙了,除了要研发公司项目外,写公号,写博客,录视频,写书稿,维护开源项目,几乎占据了我全部的业余时间。...目前确实没有太多的时间教大家,今天,就暂时给大家分享一个小技巧吧,如何彻底隐藏电脑中的“视频”,让你的女朋友再也不能发现你电脑中的小秘密!...实现效果:你女朋友打开文件是一张图片,你打开却是各种“视频”(你懂的)~~ 好了,我们开始吧! 首先,准备好一张图片,还有一个对你来说的很重要的“电影”文件夹,如图所示。...电影文件夹中的内容如下所示。 接下来,将电影文件夹压缩为1.rar文件,如下所示。 然后新建一个名称为copy_image.bat的脚本文件,文件内容如下所示。...如果你想看里面的“视频”,那只需要把图片的后缀名从.jpg修改为.rar,如下所示。 双击打开2.rar文件,如下所示。 可以看到,里面都是你珍藏多年的“视频”啦。

    4.6K20

    如何隐藏你的真实ip

    ✎ 阅读须知 乌鸦安全的技术文章仅供参考,此文所提供的信息只为网络安全人员对自己所负责的网站、服务器等(包括但不限于)进行检测或维护参考,未经授权请勿利用文章中的技术资料对任何计算机系统进行入侵操作。...利用此文所提供的信息而造成的直接或间接后果和损失,均由使用者本人负责。 乌鸦安全拥有对此文章的修改、删除和解释权限,如转载或传播此文章,需保证文章的完整性,未经允许,禁止转载!...在这里面大佬分析了用到的技术主要是WEBRTC,具体的原理还是直接看大佬的文章吧,以下是分析截图: 1.1 无隧道的情况 当前从138和请求ipinof.io上可以查到目前我的ip地址为真实的ip:...访问下面这个地址之后,显示的也是准确的: https://www.hackjie.com/tracking 当前显示的是我的真实ip地址。...屏蔽方法 经过另一位大佬指点,目前有浏览器插件能够防止这种情况,以下推荐两个插件(插件不唯一) 2.1 Firefox浏览器 插件名称:Disable WebRTC,允许该插件在隐私模式下使用: 点击一下即可开启

    3.1K20

    节点与其祖先之间的最大差值(二叉树DFS)

    题目 给定二叉树的根节点 root,找出存在于不同节点 A 和 B 之间的最大值 V,其中 V = |A.val - B.val|,且 A 是 B 的祖先。...(如果 A 的任何子节点之一为 B,或者 A 的任何子节点是 B 的祖先,那么我们认为 A 是 B 的祖先) ?...示例: 输入:[8,3,10,1,6,null,14,null,null,4,7,13] 输出:7 解释: 我们有大量的节点与其祖先的差值,其中一些如下: |8 - 3| = 5 |3 - 7| =...提示: 树中的节点数在 2 到 5000 之间。 每个节点的值介于 0 到 100000 之间。...解题 深度优先搜索,从根节点到每个叶子节点,记录到当前位置的最大最小值,达到叶子节点时,做差,取abs最大的 class Solution { int maxdiff = 0; public:

    77610

    【Groovy】自定义 Xml 生成器 BuilderSupport ( 构造 Xml 节点类 | 封装节点名称、节点值、节点属性、子节点 | 将封装的节点数据转为 Xml 字符串 )

    文章目录 一、构造 Xml 节点类 1、封装节点名称、节点值、节点属性、子节点 2、将封装的节点数据转为 Xml 字符串 二、Xml 节点类完整代码 一、构造 Xml 节点类 ---- 生成 Xml...Tom 18 1、封装节点名称、节点值、节点属性、子节点 定义 XmlNode 类 , 使用该类代表节点...封装 String 类型的的名称 : /** * 节点名称 */ String name 封装 String 类型的节点值 : /** * 节点值...2 种情况 , 带属性的节点和不带属性的节点 , ① 带属性的节点 Tom ② 不带属性的节点 使用给定的 Writer writer...XmlNode { /** * 节点名称 */ String name /** * 节点值 */ String value

    6.2K30

    如何优雅的给EPLAN项目规划名称

    以后用EPLAN干活注意点,别感觉你好像多上进,别人多落后似的 ——剑指工控-啤酒花生 项目名称 项目名称一般就填入此工程项目的名称就好了,这个大家一般也都不会填其他的。...规划高层代号结构层,这里指一个项目中的不同工艺段或不同的车间。 规划安装地点结构层,这里一般指项目区域的划分,比如电柜内、现场A区域、现场B区域等。...新建页 我们插入一个多线原理图页,根据刚才我们新建好的结构将各个层都选择好即可。 插入设备 我们试着插入一个三极开关,注意页右下角的层级。...这个开关被放置在了=ET001+CE001的电柜内,但是它只显示了-FC001,这是因为EPLAN默认隐藏已知的本层级结构属性。...我们双击打开这个开关,可以看到它的完整属性,可以体现出它的具体位置。 根据规划的区域和位置,可以大致插入一些页,用于原理图的绘制。 最后,导出结构标识符总览。

    86710

    【Groovy】json 序列化 ( JsonBuilder 生成器 | 生成带根节点名称的 json 字符串 | 生成不带根节点名称的 json 字符串 )

    // json 生成器 def jsonBuilder = new JsonBuilder() 然后 , 如果生成一个带根节点名称的 json 字符串 ,需要使用 jsonBuilder.根节点名称 =...{闭包} 格式的代码 , 生成 json 字符串 ; // 生成 {"student":{"name":"Tom","age":18}} // 其中 .student 表示的是根节点的名称 , 这不是一个方法名...jsonBuilder.student{ name "Tom" age 18 } 上述代码生成的 json 字符串为 {"student":{"name":"Tom","age":18..."Tom" age 18 } 代码即可 , 去掉 .根节点名称 , 直接使用 jsonBuilder{ 闭包 } 生成 json 字符串 ; 二、代码示例 ---- json 生成器代码示例...生成器 def jsonBuilder = new JsonBuilder() // 生成 {"student":{"name":"Tom","age":18}} // 其中 .student 表示的是根节点的名称

    1.6K20

    cdn节点是什么?如何理解cdn节点的作用?

    当人们在网络上遨游的时候,可能很难想象在这其中有多少服务器在为实现网络访问而繁忙不休,而cdn节点就是一种能够帮助用户提升网站访问速度的服务,那么cdn节点是什么?如何理解cdn节点的作用呢?...cdn节点是什么 虽然在网络世界中似乎并没有物理距离的问题,访问任何网站对于用户而言都只是输入一串字符,但其实不同的网站都是建立在真实的服务器中的,如果用户距离网站数据保存服务器的距离过远,那么用户访问该网站时就会出现网络延迟...而cdn节点就是映射了网站内容的边缘服务器,能够根据用户的地域为其提供距离其最近的服务器中所保存的网站内容。...cdn节点的作用 很多人对于cdn节点是什么都不是十分清楚,更不用说如何理解cdn节点的作用。...其实这种网络概念对于行业外用户而言,想要完全解释清楚是比较困难的,不过目前的cdn节点大多属于自动为用户分配的,因此对于绝大多数用户而言,只需要知道这是一种能够提升网络访问速度的服务就已经足够。

    4K40

    如何批量导入名称没有规律的图片

    图片一般都按照有规律的序列号命名,但是也有时没有规律,比如证件照片可能是按照姓名来命名的。下面我们就用一个例子详细介绍如何批量导入这样的图片。   ...首先,打开条码标签软件,新建一个标签,尺寸按照自己的需要进行设置。点击图片,选择来自文件,选择图片所在的文件夹,这里要注意,提前将所需要的图片都放到一个文件夹里。从中选择一个图片导入到软件中。...01.png   图片添加完成后,先在软件右侧勾选“打印或导出时先读取数据源的字段值作为文件名,然后从该文件中读取图片”。然后点击底部的“图片文件名整理工具”。...02.png   弹出一个界面,点击“选择”,选择存放所有图片的文件夹。点击导出到Excel,在弹出的界面中选择一个文件夹将Excel文件保存下来。...04.png   以上就是批量导入图片的操作方法,如需添加相对应的文字信息,可以将生成的图片Excel表格和其他内容的数据库整合,就可以实现图片和内容相对应了。

    1.2K20

    如何优雅地隐藏你的Webshell

    不让网站管理员或者其他的Hacker发现,网上关于隐藏后门的方法也很多,如加密、包含,解析漏洞、加隐藏系统属性等等,但大部分已经都不实用了,随便找一个查马的程序就能很快的查出来,下面分享我总结的一些经验...: 制作免杀webshell 隐藏webshell最主要的就是做免杀,免杀做好了,你可以把webshell放在函数库文件中或者在图片马中,太多地方可以放了,只要查杀工具查不到,你的这个webshell就能存活很长时间...更好的隐藏webshell一些建议 1、拿到权限以后,把网站日志中的所有关于webshell的访问记录和渗透时造成的一些网站报错记录全部删除 2、把webshell的属性时间改为和同目录文件相同的时间戳...主题目录,编辑器的图片目录以及一些临时目录 4、利用php.ini 配置文件隐藏webshell,把webshell的路径加入到配置文件中 5、尝试利用静态文件隐藏一句话,然后用.htaccess 规则进行解析...,务必把脚本找出来,crontab一般都能看见了 我这里只是根据个人经验总结了一些比较常用的,当然,肯定还有更多更好更高级的关于webshell的隐藏方法,欢迎大家留言。

    1.4K20
    领券