算法筆試模拟題精解之“蘋果收獲程式”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

https://developer.aliyun.com/coding

本文為大家介紹其中的 第67題：蘋果收獲程式 的題目解析，具體如下：

題目描述

題目等級：容易

知識點：深度優先搜尋/DFS

檢視題目：蘋果收獲程式

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最後能收獲的蘋果數量。

示例1

輸入：

5

[1,2,2,2]

輸出：

3

注意

1、蘋果的掉落速度是相等的，即每次都會掉落到與目前節點直接相連的節點上。

2、隻要有蘋果出現在根節點1上面就會被收獲。

解題思路

蘋果收獲程式在正常情況下，有多個蘋果落到同一節點時，應該會是一個相加的情況。結合這個BUG的情況，可以猜想，這個程式的BUG也許是因為這棵樹每個節點隻能存儲一個二進制位導緻的，在這種情況下出現的BUG和題目中的相符。

因為每次下落時，蘋果樹每一層的節點都會往下掉一層。由此可以想到，如果蘋果樹某一層的節點的數目為奇數時，這一層的節點的蘋果掉落到第一層時，由于一個節點隻能存儲一個二進制位的原因，隻會剩下一個蘋果。而如果蘋果樹某一層的節點數目為偶數，這一層的節點的蘋果掉落到第一層時，剩下的蘋果數目為0。

是以可以統計每一層有多少個節點來解決這個問題，根節點1是第一層，掉落到一層的節點是第二層，以此類推，通過判斷一個節點會掉落到的層數來判斷該結點目前是第幾層。周遊數組，用一個數組count記錄每一層擁有的節點數，周遊數組，計算出一個節點所在的層之後，在count數組中将該層擁有的節點數加一。最後判斷哪些層的節點數為奇數，這些層每層可以收獲一個蘋果，累加後即可得到答案。

送出以後，發現還有一些測試用例無法通過，通過分析以後發現，還需要注意一個問題。在周遊數組計算每個節點所在的層時，需要注意，如果數組中的數字表示這個節點會掉落到自身節點的位置上，也就是這個節點的蘋果不會往下層掉，會永遠留在這個節點，是以在統計每層的節點數時，這個節點不該被統計，而掉落到這個節點的其他節點的蘋果也永遠不會掉落到第一層，是以這些節點也不能被統計，不屬于任何層，不被統計進count數組。

時間複雜度：O(n)

空間複雜度：O(n)

看完之後是不是有了想法了呢，快來練練手吧>>