开发者社区> 问答> 正文

遇到一个苹果收获程序问题,求解答。

Alice和Bob在春天的时候种下了一棵苹果树,为了吃到苹果,他们每天都会去给苹果树浇水。一眨眼到了苹果成熟的时候,但是他们却因为平时照顾苹果树太累了,没有更多的精力去收获苹果。身为程序猿的 Bob 灵机一动,写了一个自动收获苹果的程序。这个程序把苹果树简化成了一个拥有 n 个节点,根节点为 1 的树,每个节点有 1个苹果,苹果会在程序的作用下同时往根节点的方向掉落。但是这个程序有一个致命的Bug:每当有两个苹果同时掉落到同一个节点的时候,这两个苹果会在 Bug 的作用下消失。每当 1 苹果落到根节点 1 的时候,Bob 就可以收获 1 个苹果。Bob 想要预测他们最后可以通过程序收获多少个苹果。输入内容有两行。第一行有一个正整数 n(2<=n<=10^5),表示树有 n 个节点。 第二行有 n-1 个数 p2,p3,...,pn,(1<=pi 滚落到节点 2 上面的苹果会因为 bug而消失的只剩一个。)输出一个数字,表示 Bob 最后能收获的苹果数量.

展开
收起
游客4skzfvnrxrzbi 2021-12-23 16:56:45 504 0
1 条回答
写回答
取消 提交回答
  • 苹果收获程序在正常情况下,有多个苹果落到同一节点时,应该会是一个相加的情况。结合这个 BUG 的情况,可以猜想,这个程序的 BUG 也许是因为这棵树每个节点只能存储一个二进制位导致的,在这种情况下出现的 BUG 和题目中的相符。因为每次下落时,苹果树每一层的节点都会往下掉一层。由此可以想到,如果苹果树某一层的节点的数目为奇数时,这一层的节点的苹果掉落到第一层时,由于一个节点只能存储一个二进制位的原因,只会剩下一个苹果。而如果苹果树某一层的节点数目为偶数,这一层的节点的苹果掉落到第一层时,剩下的苹果数目为 0。因此可以统计每一层有多少个节点来解决这个问题,根节点 1 是第一层,掉落到一层的节点是第二层,以此类推,通过判断一个节点会掉落到的层数来判断该结点当前是第几层。遍历数组,用一个数组 count 记录每一层拥有的节点数,遍历数组,计算出一个节点所在的层之后,在 count 数组中将该层拥有的节点数加一。最后判断哪些层的节点数为奇数,这些层每层可以收获一个苹果,累加后即可得到答案。提交以后,发现还有一些测试用例无法通过,通过分析以后发现,还需要注意一个问题。在遍历数组计算每个节点所在的层时,需要注意,如果数组中的数字表示这个节点会掉落到自身节点的位置上,也就是这个节点的苹果不会往下层掉,会永远留在这个节点,因此在统计每层的节点数时,这个节点不该被统计,而掉落到这个节点的其他节点的苹果也永远不会掉落到第一层,因此这些节点也不能被统计,不属于任何层,不被统计进 count 数组。 输入:5 [1,2,2,2] 输出:3 注:1. 苹果的掉落速度是相等的,即每次都会掉落到与当前节点直接相连的节点上。 2.只要有苹果出现在根节点 1 上面就会被收获。

    2021-12-23 18:47:48
    赞同 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
PHP安全开发_从白帽角度做安全 立即下载
PHP安全开发:从白帽角度做安全 立即下载
分身大师那些事儿 立即下载