介紹

總而言之是時(shí)候利用暑假鍛煉一下算法技術(shù)，一提算法面試就面露難色的情形總不能一直持續(xù)下去。本欄目面向有一定基礎(chǔ)的編程愛好者，每天（如果up不鴿）分享并解析一道LeetCode中高難度題目（通常是hard）。有興趣的小伙伴可以一起跟著做并且討論解法。目前的教材是花花醬的Leetcode Problem List【1】.

適合人群：

有一定算法基礎(chǔ)，但是還未能順利通過筆試/面試，總覺得算法題目想不明白的你。

(相關(guān)資料圖)

不適合人群：

算法入門級選手（一上來就做難題可能并不合適，建議首先專注簡單/中等題目）

非常不適合人群：

算法競賽選手（這種小兒科的問題完全是在浪費(fèi)您的時(shí)間）

過往題目在這里！

在二叉樹中分配硬幣

題目看這里，leetcode第979題，hard難度：/problems/distribute-coins-in-binary-tree/

強(qiáng)烈建議讀者自己先做（不過真的會有讀者嗎，笑），有任何問題歡迎在評論區(qū)討論，up看到了會及時(shí)回復(fù)。做完了歡迎在評論區(qū)打卡～

解析

久違的難題！首先的observation是，可以用一個(gè)變量表示當(dāng)前樹需要多少硬幣/能給出多少硬幣。這里我們左右兩邊先分別計(jì)算出這個(gè)值。比如說左邊樹要5個(gè)硬幣，右邊要-3個(gè)。那么此時(shí)根節(jié)點(diǎn)的硬幣數(shù)應(yīng)該是多少？有聰明的同學(xué)可以得出，5-3+1 = 3。+1是因?yàn)楦?jié)點(diǎn)也需要一個(gè)硬幣。如果根節(jié)點(diǎn)的硬幣數(shù)不夠或者有余，那么就把這個(gè)值上報(bào)給更上一級的節(jié)點(diǎn)，這是個(gè)遞歸的過程。

在這個(gè)過程中，每層我們都會以根節(jié)點(diǎn)為連接，把硬幣從左右子樹之間移動。最小的移動次數(shù)即為積累的移動次數(shù)的和。

思考樂園

計(jì)算移動次數(shù)的時(shí)候，為什么用了abs函數(shù)？歡迎將答案寫在評論區(qū)～

音樂推薦

究竟是要做的事情太多導(dǎo)致博得之門變得好玩，還是已經(jīng)焦頭爛額的我沒有興趣去玩博得之門，這是一個(gè)很好的問題。今天要推薦的歌曲是來自輕鸞軸心的我愛你就像拖拉機(jī)下山叮鈴哐當(dāng)叮鈴，不知道為什么是ktv版本的，送給兩眼一黑的你。

教材鏈接

【1】/blog/leetcode-problem-categories/

標(biāo)簽：