2021年6月底,拼多多搜索廣告算法暑假實(shí)習(xí)面試題2道
文 | 七月在線
編 | 小七
目錄
FIGHTING
問題1：算法題:leetcode 687.最長同值路徑
問題2：算法題:leetcode 322.零錢兌換
問題1：算法題:leetcode 687.最長同值路徑
方法：遞歸
可以將任何路徑（具有相同值的節(jié)點(diǎn)）看作是最多兩個從其根延伸出的箭頭。具體地說，路徑的根將是唯一節(jié)點(diǎn)，因此該節(jié)點(diǎn)的父節(jié)點(diǎn)不會出現(xiàn)在該路徑中，而箭頭將是根在該路徑中只有一個子節(jié)點(diǎn)的路徑。然后，對于每個節(jié)點(diǎn)，我們想知道向左延伸的最長箭頭和向右延伸的最長箭頭是什么？我們可以用遞歸來解決這個問題。
令 arrow_length(node) 為從節(jié)點(diǎn) node 延伸出的最長箭頭的長度。如果 node.Left 存在且與節(jié)點(diǎn) node 具有相同的值，則該值就會是 1 + arrow_length(node.left)。在 node.right 存在的情況下也是一樣。
當(dāng)我們計(jì)算箭頭長度時，候選答案將是該節(jié)點(diǎn)在兩個方向上的箭頭之和。我們將這些候選答案記錄下來，并返回最佳答案。
代碼如下：
時間復(fù)雜度：O(N)，其中 N 是樹中節(jié)點(diǎn)數(shù)。
空間復(fù)雜度：O(H)，其中 H 是樹的高度。
問題2：算法題:leetcode 322.零錢兌換
完全背包問題——填滿容量為amount的背包最少需要多少硬幣
dp[j]代表含義：填滿容量為j的背包最少需要多少硬幣
初始化dp數(shù)組：因?yàn)橛矌诺臄?shù)量一定不會超過amount，而amount <= 10^4，因此初始化數(shù)組值為10001；dp[0] = 0
轉(zhuǎn)移方程：dp[j] = min(dp[j], dp[j - coin] + 1)
當(dāng)前填滿容量j最少需要的硬幣 = min( 之前填滿容量j最少需要的硬幣, 填滿容量 j - coin 需要的硬幣 + 1個當(dāng)前硬幣）
返回dp[amount]，如果dp[amount]的值為10001沒有變過，說明找不到硬幣組合，返回-1
代碼如下：
時間復(fù)雜度：O(n * amount)
空間復(fù)雜度：O(amount)
推薦閱讀??點(diǎn)擊標(biāo)題可跳轉(zhuǎn)
4、百度機(jī)器學(xué)習(xí)/NLP算法面試題8道
戳↓↓“閱讀原文”了解更多！