點(diǎn)擊藍(lán)色“力扣加加”關(guān)注我喲

加個(gè)“星標(biāo)”，帶你揭開算法的神秘面紗！

字節(jié)跳動(dòng)的算法面試題是什么難度？(第二彈)

第一彈地址：字節(jié)跳動(dòng)的算法面試題是什么難度？

由于 lucifer 我是一個(gè)小前端， 最近也在準(zhǔn)備寫一個(gè)《前端如何搞定算法面試》的專欄，因此最近沒(méi)少看各大公司的面試題。都說(shuō)字節(jié)跳動(dòng)算法題比較難，我就先拿 ta 下手，做了幾套 。這次我們就拿一套?字節(jié)跳動(dòng)2017秋招編程題匯總來(lái)看下字節(jié)的算法筆試題的難度幾何。地址：https://www.nowcoder.com/test/6035789/summary

這套題一共 11 道題， 三道編程題， 八道問(wèn)答題。本次給大家?guī)?lái)的就是這三道編程題。更多精彩內(nèi)容，請(qǐng)期待我的搞定算法面試專欄。

其中有一道題《異或》我沒(méi)有通過(guò)所有的測(cè)試用例， 小伙伴可以找找茬，第一個(gè)找到并在公眾號(hào)力扣加加留言的小伙伴獎(jiǎng)勵(lì)現(xiàn)金紅包 10 元。

1. 頭條校招

題目描述

頭條的 2017 校招開始了！為了這次校招，我們組織了一個(gè)規(guī)模宏大的出題團(tuán)隊(duì)，每個(gè)出題人都出了一些有趣的題目，而我們現(xiàn)在想把這些題目組合成若干場(chǎng)考試出來(lái)，在選題之前，我們對(duì)題目進(jìn)行了盲審，并定出了每道題的難度系統(tǒng)。一場(chǎng)考試包含 3 道開放性題目，假設(shè)他們的難度從小到大分別為 a,b,c，我們希望這 3 道題能滿足下列條件：
a<=b<=c
b-a<=10
c-b<=10
所有出題人一共出了 n 道開放性題目?，F(xiàn)在我們想把這 n 道題分布到若干場(chǎng)考試中（1 場(chǎng)或多場(chǎng)，每道題都必須使用且只能用一次），然而由于上述條件的限制，可能有一些考試沒(méi)法湊夠 3 道題，因此出題人就需要多出一些適當(dāng)難度的題目來(lái)讓每場(chǎng)考試都達(dá)到要求，然而我們出題已經(jīng)出得很累了，你能計(jì)算出我們最少還需要再出幾道題嗎？

輸入描述:
輸入的第一行包含一個(gè)整數(shù) n，表示目前已經(jīng)出好的題目數(shù)量。

第二行給出每道題目的難度系數(shù) d1,d2,...,dn。

數(shù)據(jù)范圍

對(duì)于?30%的數(shù)據(jù)，1?≤?n,di?≤?5;

對(duì)于 100%的數(shù)據(jù)，1 ≤ n ≤ 10^5,1 ≤ di ≤ 100。

在樣例中，一種可行的方案是添加 2 個(gè)難度分別為 20?和 50?的題目，這樣可以組合成兩場(chǎng)考試：（20 20 23）和（35,40,50）。

輸出描述:
輸出只包括一行，即所求的答案。
示例?1
輸入
4
20?35?23?40
輸出
2

思路

這道題看起來(lái)很復(fù)雜， 你需要考慮很多的情況。，屬于那種沒(méi)有技術(shù)含量，但是考驗(yàn)編程能力的題目，需要思維足夠嚴(yán)密。這種「模擬的題目」，就是題目讓我干什么我干什么。類似之前寫的囚徒房間問(wèn)題，約瑟夫環(huán)也是模擬，只不過(guò)模擬之后需要你剪枝優(yōu)化。

這道題的情況其實(shí)很多， 我們需要考慮每一套題中的難度情況， 而不需要考慮不同套題的難度情況。題目要求我們滿足：a<=b<=c b-a<=10 c-b<=10，也就是題目難度從小到大排序之后，相鄰的難度不能大于 10 。

因此我們的思路就是先排序，之后從小到大遍歷，如果滿足相鄰的難度不大于 10 ，則繼續(xù)。如果不滿足， 我們就只能讓字節(jié)的老師出一道題使得滿足條件。

由于只需要比較同一套題目的難度，因此我的想法就是「比較同一套題目的第二個(gè)和第一個(gè)，以及第三個(gè)和第二個(gè)的 diff」。

• 如果 diff 小于 10，什么都不做，繼續(xù)。
• 如果 diff 大于 10，我們必須補(bǔ)充題目。

這里有幾個(gè)點(diǎn)需要注意。

對(duì)于第二題來(lái)說(shuō)：

• 比如 1?「20」?30 這樣的難度。我可以在 1，20 之間加一個(gè) 11，這樣 1，11，20 就可以組成一一套。
• 比如 1?「30」?60 這樣的難度。我可以在 1，30 之間加 11， 21 才可以組成一套，自身（30）是無(wú)論如何都沒(méi)辦法組到這套題中的。

不難看出， 第二道題的臨界點(diǎn)是 diff = 20 。小于等于 20 都可以將自身組到套題，增加一道即可，否則需要增加兩個(gè)，并且自身不能組到當(dāng)前套題。

對(duì)于第三題來(lái)說(shuō)：

• 比如 1 20?「40」。我可以在 20，40 之間加一個(gè) 30，這樣 1，20，30 就可以組成一一套，自身（40）是無(wú)法組到這套題的。
• 比如 1 20?「60」。也是一樣的，我可以在 20，60 之間加一個(gè) 30，自身（60）同樣是沒(méi)辦法組到這套題中的。

不難看出， 第三道題的臨界點(diǎn)是 diff = 10 。小于等于 10 都可以將自身組到套題，否則需要增加一個(gè)，并且自身不能組到當(dāng)前套題。

這就是所有的情況了。

有的同學(xué)比較好奇，我是怎么思考的。我是怎么「保障不重不漏」的。

實(shí)際上，這道題就是一個(gè)決策樹， 我畫個(gè)決策樹出來(lái)你就明白了。

?

圖中紅色邊框表示自身可以組成套題的一部分， 我也用文字進(jìn)行了說(shuō)明。#2 代表第二題， #3 代表第三題。

?

從圖中可以看出， 我已經(jīng)考慮了所有情況。如果你能夠像我一樣畫出這個(gè)決策圖，我想你也不會(huì)漏的。當(dāng)然我的解法并不一定是最優(yōu)的，不過(guò)確實(shí)是一個(gè)非常好用，具有普適性的思維框架。

需要特別注意的是，由于需要湊整， 因此你需要使得題目的總數(shù)是 3 的倍數(shù)向上取整。

代碼

n?=?int(input())
nums?=?list(map(int,?input().split()))
cnt?=?0
cur?=?1
nums.sort()
for?i?in?range(1,?n):
????if?cur?==?3:
????????cur?=?1
????????continue
????diff?=?nums[i]?-?nums[i?-?1]
????if?diff?<=?10:
????????cur?+=?1
????if?10?20:
????????if?cur?==?1:
????????????cur?=?3
????????if?cur?==?2:
????????????cur?=?1
????????cnt?+=?1
????if?diff?>?20:
????????if?cur?==?1:
????????????cnt?+=?2
????????if?cur?==?2:
????????????cnt?+=?1
????????cur?=?1
print(cnt?+?3?-?cur)

「復(fù)雜度分析」

• 時(shí)間復(fù)雜度：由于使用了排序， 因此時(shí)間復(fù)雜度為?。（假設(shè)使用了基于比較的排序）
• 空間復(fù)雜度：

2. 異或

題目描述

給定整數(shù) m 以及 n 各數(shù)字 A1,A2,..An，將數(shù)列 A 中所有元素兩兩異或，共能得到 n(n-1)/2 個(gè)結(jié)果，請(qǐng)求出這些結(jié)果中大于 m 的有多少個(gè)。

輸入描述:
第一行包含兩個(gè)整數(shù)?n,m.

第二行給出 n 個(gè)整數(shù) A1，A2，...，An。

數(shù)據(jù)范圍

對(duì)于?30%的數(shù)據(jù)，1?<=?n,?m?<=?1000

對(duì)于?100%的數(shù)據(jù)，1?<=?n,?m,?Ai?<=?10^5

輸出描述:
輸出僅包括一行，即所求的答案

輸入例子?1:
3?10
6?5?10

輸出例子?1:
2

前置知識(shí)

• 異或運(yùn)算的性質(zhì)
• 如何高效比較兩個(gè)數(shù)的大?。◤母呶坏降臀唬?/section>

首先普及一下前置知識(shí)。第一個(gè)是異或運(yùn)算：

異或的性質(zhì)：兩個(gè)數(shù)字異或的結(jié)果 a^b 是將 a 和 b 的二進(jìn)制每一位進(jìn)行運(yùn)算，得出的數(shù)字。運(yùn)算的邏輯是如果同一位的數(shù)字相同則為 0，不同則為 1

異或的規(guī)律：

1. 任何數(shù)和本身異或則為 0

2. 任何數(shù)和 0 異或是本身

3. 異或運(yùn)算滿足交換律，即：a ^ b ^ c = a ^ c ^ b

同時(shí)建議大家去看下我總結(jié)的幾道位運(yùn)算的經(jīng)典題目。?位運(yùn)算系列^[1]

其次要知道一個(gè)常識(shí)， 即比較兩個(gè)數(shù)的大小， 我們是從高位到低位比較，這樣才比較高效。

比如：

123
456
1234

這三個(gè)數(shù)比較大小， 為了方便我們先補(bǔ) 0 ，使得大家的位數(shù)保持一致。

0123
0456
1234

先比較第一位，1 比較 0 大， 因此 1234 最大。再比較第二位， 4 比 1 大， 因此 456 大于 123，后面位不需要比較了。這其實(shí)就是剪枝的思想。

有了這兩個(gè)前提，我們來(lái)試下暴力法解決這道題。

思路

暴力法就是枚舉??中組合， 讓其兩兩按位異或，將得到的結(jié)果和 m 進(jìn)行比較， 如果比 m 大， 則計(jì)數(shù)器 + 1， 最后返回計(jì)數(shù)器的值即可。

暴力的方法就如同題目描述的那樣， 復(fù)雜度為?。一定過(guò)不了所有的測(cè)試用例， 不過(guò)大家實(shí)在沒(méi)有好的解法的情況可以兜底。不管是?？凸P試還是實(shí)際的面試都是可行的。

接下來(lái)，讓我們來(lái)「分析一下暴力為什么低效，以及如何選取數(shù)據(jù)結(jié)構(gòu)和算法能夠使得這個(gè)過(guò)程變得高效?！?/strong>?記住這句話， 幾乎所有的優(yōu)化都是基于這種思維產(chǎn)生的，除非你開啟了上帝模式，直接看了答案。只不過(guò)等你熟悉了之后，這個(gè)思維過(guò)程會(huì)非常短， 以至于變成條件反射， 你感覺(jué)不到有這個(gè)過(guò)程， 這就是「有了題感。」

其實(shí)我剛才說(shuō)的第二個(gè)前置知識(shí)就是我們優(yōu)化的關(guān)鍵之一。

我舉個(gè)例子， 比如 3 和 5 按位異或。

3 的二進(jìn)制是 011， 5 的二進(jìn)制是 101，

011
101

按照我前面講的異或知識(shí)， 不難得出其異或結(jié)構(gòu)就是 110。

上面我進(jìn)行了三次異或：

1. 第一次是最高位的 0 和 1 的異或， 結(jié)果為 1。
2. 第二次是次高位的 1 和 0 的異或， 結(jié)果為 1。
3. 第三次是最低位的 1 和 1 的異或， 結(jié)果為 0。

那如何 m 是 1 呢？我們有必要進(jìn)行三次異或么？實(shí)際上進(jìn)行第一次異或的時(shí)候已經(jīng)知道了一定比 m（m 是 1） 大。因?yàn)榈谝淮萎惢虻慕Y(jié)構(gòu)導(dǎo)致其最高位為 1，也就是說(shuō)其最小也不過(guò)是 100，也就是 4，一定是大于 1 的。這就是「剪枝」， 這就是算法優(yōu)化的關(guān)鍵。

?

看出我一步一步的思維過(guò)程了么？所有的算法優(yōu)化都需要經(jīng)過(guò)類似的過(guò)程。

?

因此我的算法就是從高位開始兩兩異或，并且異或的結(jié)果和 m 對(duì)應(yīng)的二進(jìn)制位比較大小。

• 如果比 m 對(duì)應(yīng)的二進(jìn)制位大或者小，我們提前退出即可。
• 如果相等，我們繼續(xù)往低位移動(dòng)重復(fù)這個(gè)過(guò)程。

這雖然已經(jīng)剪枝了，但是極端情況下，性能還是很差。比如：

m:?1111
a:?1010
b:?0101

a，b 表示兩個(gè)數(shù)，我們比較到最后才發(fā)現(xiàn)，其異或的值和 m 相等。因此極端情況，算法效率沒(méi)有得到改進(jìn)。

這里我想到了一點(diǎn)，就是如果一個(gè)數(shù) a 的前綴和另外一個(gè)數(shù) b 的前綴是一樣的，那么 c 和 a 或者 c 和 b 的異或的結(jié)構(gòu)前綴部分一定也是一樣的。比如：

a:?111000
b:?111101
c:?101011

a 和 b 有共同的前綴 111，c 和 a 異或過(guò)了，當(dāng)再次和 b 異或的時(shí)候，實(shí)際上前三位是沒(méi)有必要進(jìn)行的，這也是重復(fù)的部分。這就是算法可以優(yōu)化的部分， 這就是剪枝。

「分析算法，找到算法的瓶頸部分，然后選取合適的數(shù)據(jù)結(jié)構(gòu)和算法來(lái)優(yōu)化到。」?這句話很重要， 請(qǐng)務(wù)必記住。

在這里，我們用的就是剪枝技術(shù)，關(guān)于剪枝，91 天學(xué)算法也有詳細(xì)的介紹。

回到前面講到的算法瓶頸， 多個(gè)數(shù)是有共同前綴的， 前綴部分就是我們浪費(fèi)的運(yùn)算次數(shù)， 說(shuō)到前綴大家應(yīng)該可以想到前綴樹。如果不熟悉前綴樹的話，看下我的這個(gè)前綴樹專題^[2]，里面的題全部手寫一遍就差不多了。

因此一種想法就是建立一個(gè)前綴樹，?「樹的根就是最高的位」。由于題目要求異或， 我們知道異或是二進(jìn)制的位運(yùn)算， 因此這棵樹要存二進(jìn)制才比較好。

反手看了一眼數(shù)據(jù)范圍：m, n<=10^5 。10^5 = 2 ^ x，我們的目標(biāo)是求出 滿足條件的 x 的 ceil（向上取整），因此 x 應(yīng)該是 17。

樹的每一個(gè)節(jié)點(diǎn)存儲(chǔ)的是：「n 個(gè)數(shù)中，從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)形成的前綴有多少個(gè)是一樣的」，即多少個(gè)數(shù)的前綴是一樣的。這樣可以剪枝，提前退出的時(shí)候，就直接取出來(lái)用了。比如異或的結(jié)果是 1， m 當(dāng)前二進(jìn)制位是 0 ，那么這個(gè)前綴有 10 個(gè)，我都不需要比較了， 計(jì)數(shù)器直接 + 10 。

?

我用 17 直接復(fù)雜度過(guò)高，目前僅僅通過(guò)了 70 % - 80 % 測(cè)試用例， 希望大家可以幫我找找毛病，我猜測(cè)是語(yǔ)言的鍋。

?

代碼

class?TreeNode:
????def?__init__(self):
????????self.cnt?=?1
????????self.children?=?[None]?*?2
def?solve(num,?i,?cur):
????if?cur?==?None?or?i?==?-1:?return?0
????bit?=?(num?>>?i)?&?1
????mbit?=?(m?>>?i)?&?1
????if?bit?==?0?and?mbit?==?0:
????????return?(cur.children[1].cnt?if?cur.children[1]?else?0)?+?solve(num,?i?-?1,?cur.children[0])
????if?bit?==?1?and?mbit?==?0:
????????return?(cur.children[0].cnt?if?cur.children[0]?else?0)?+?solve(num,?i?-?1,?cur.children[1])
????if?bit?==?0?and?mbit?==?1:
????????return?solve(num,?i?-?1,?cur.children[1])
????if?bit?==?1?and?mbit?==?1:
????????return?solve(num,?i?-?1,?cur.children[0])

def?preprocess(nums,?root):
????for?num?in?nums:
????????cur?=?root
????????for?i?in?range(16,?-1,?-1):
????????????bit?=?(num?>>?i)?&?1
????????????if?cur.children[bit]:
????????????????cur.children[bit].cnt?+=?1
????????????else:
????????????????cur.children[bit]?=?TreeNode()
????????????cur?=?cur.children[bit]

n,?m?=?map(int,?input().split())
nums?=?list(map(int,?input().split()))
root?=?TreeNode()
preprocess(nums,?root)
ans?=?0
for?num?in?nums:
????ans?+=?solve(num,?16,?root)
print(ans?//?2)

「復(fù)雜度分析」

• 時(shí)間復(fù)雜度：
• 空間復(fù)雜度：

3. 字典序

題目描述

給定整數(shù) n 和 m, 將 1 到 n 的這 n 個(gè)整數(shù)按字典序排列之后, 求其中的第 m 個(gè)數(shù)。
對(duì)于?n=11,?m=4,?按字典序排列依次為?1,?10,?11,?2,?3,?4,?5,?6,?7,?8,?9,?因此第?4?個(gè)數(shù)是?2.
對(duì)于?n=200,?m=25,?按字典序排列依次為?1?10?100?101?102?103?104?105?106?107?108?109?11?110?111?112?113?114?115?116?117?118?119?12?120?121?122?123?124?125?126?127?128?129?13?130?131?132?133?134?135?136?137?138?139?14?140?141?142?143?144?145?146?147?148?149?15?150?151?152?153?154?155?156?157?158?159?16?160?161?162?163?164?165?166?167?168?169?17?170?171?172?173?174?175?176?177?178?179?18?180?181?182?183?184?185?186?187?188?189?19?190?191?192?193?194?195?196?197?198?199?2?20?200?21?22?23?24?25?26?27?28?29?3?30?31?32?33?34?35?36?37?38?39?4?40?41?42?43?44?45?46?47?48?49?5?50?51?52?53?54?55?56?57?58?59?6?60?61?62?63?64?65?66?67?68?69?7?70?71?72?73?74?75?76?77?78?79?8?80?81?82?83?84?85?86?87?88?89?9?90?91?92?93?94?95?96?97?98?99?因此第?25?個(gè)數(shù)是?120…

輸入描述:
輸入僅包含兩個(gè)整數(shù) n 和 m。

數(shù)據(jù)范圍:

對(duì)于?20%的數(shù)據(jù),?1?<=?m?<=?n?<=?5?;

對(duì)于?80%的數(shù)據(jù),?1?<=?m?<=?n?<=?10^7?;

對(duì)于?100%的數(shù)據(jù),?1?<=?m?<=?n?<=?10^18.

輸出描述:
輸出僅包括一行,?即所求排列中的第?m?個(gè)數(shù)字.
示例?1
輸入
11?4
輸出
2

前置知識(shí)

• 十叉樹
• 完全十叉樹
• 計(jì)算完全十叉樹的節(jié)點(diǎn)個(gè)數(shù)
• 字典樹

思路

和上面題目思路一樣， 先從暴力解法開始，嘗試打開思路。

暴力兜底的思路是直接生成一個(gè)長(zhǎng)度為 n 的數(shù)組， 排序，選第 m 個(gè)即可。代碼：

n,?m?=?map(int,?input().split())

nums??=?[str(i)?for?i?in?range(1,?n?+?1)]
print(sorted(nums)[m?-?1])

「復(fù)雜度分析」

• 時(shí)間復(fù)雜度：取決于排序算法， 不妨認(rèn)為是?
• 空間復(fù)雜度:?

這種算法可以 pass 50 % case。

上面算法低效的原因是開辟了 N 的空間，并對(duì)整 N 個(gè) 元素進(jìn)行了排序。

一種簡(jiǎn)單的優(yōu)化方法是將排序換成堆，利用堆的特性求第 k 大的數(shù)， 這樣時(shí)間復(fù)雜度可以減低到?。

我們繼續(xù)優(yōu)化。實(shí)際上，你如果把字典序的排序結(jié)構(gòu)畫出來(lái)， 可以發(fā)現(xiàn)他本質(zhì)就是一個(gè)十叉樹，并且是一個(gè)完全十叉樹。

接下來(lái)，我?guī)憷^續(xù)分析。

如圖， 紅色表示根節(jié)點(diǎn)。節(jié)點(diǎn)表示一個(gè)十進(jìn)制數(shù)，?「樹的路徑存儲(chǔ)真正的數(shù)字」，比如圖上的 100，109 等。這不就是上面講的前綴樹么？

如圖黃色部分， 表示字典序的順序，注意箭頭的方向。因此本質(zhì)上，「求字典序第 m 個(gè)數(shù)， 就是求這棵樹的前序遍歷的第 m 個(gè)節(jié)點(diǎn)?！?/strong>

因此一種優(yōu)化思路就是構(gòu)建一顆這樣的樹，然后去遍歷。構(gòu)建的復(fù)雜度是?，遍歷的復(fù)雜度是?。因此這種算法的復(fù)雜度可以達(dá)到??，由于 n >= m，因此就是?。

實(shí)際上， 這樣的優(yōu)化算法依然是無(wú)法 AC 全部測(cè)試用例的，會(huì)超內(nèi)存限制。因此我們的思路只能是不使用 N 的空間去構(gòu)造樹。想想也知道， 由于 N 最大可能為 10^18，一個(gè)數(shù)按照 4 字節(jié)來(lái)算， 那么這就有 400000000 字節(jié)，大約是 381 M，這是不能接受的。

上面提到這道題就是一個(gè)完全十叉樹的前序遍歷，問(wèn)題轉(zhuǎn)化為求完全十叉樹的前序遍歷的第 m 個(gè)數(shù)。

?

十叉樹和二叉樹沒(méi)有本質(zhì)不同， 我在二叉樹專題部分， 也提到了 N 叉樹都可以用二叉樹來(lái)表示。

?

對(duì)于一個(gè)節(jié)點(diǎn)來(lái)說(shuō)，第 m 個(gè)節(jié)點(diǎn)：

• 要么就是它本身
• 要么其孩子節(jié)點(diǎn)中
• 要么在其兄弟節(jié)點(diǎn)
• 要么在兄弟節(jié)點(diǎn)的孩子節(jié)點(diǎn)中

究竟在上面的四個(gè)部分的哪，取決于其孩子節(jié)點(diǎn)的個(gè)數(shù)。

• count > m ，m 在其孩子節(jié)點(diǎn)中，我們需要深入到子節(jié)點(diǎn)。
• count <= m ，m 不在自身和孩子節(jié)點(diǎn), 我們應(yīng)該跳過(guò)所有孩子節(jié)點(diǎn)，直接到兄弟節(jié)點(diǎn)。

這本質(zhì)就是一個(gè)遞歸的過(guò)程。

需要注意的是，我們并不會(huì)真正的在樹上走，因此上面提到的「深入到子節(jié)點(diǎn)」， 以及?「跳過(guò)所有孩子節(jié)點(diǎn)，直接到兄弟節(jié)點(diǎn)」如何操作呢？

你仔細(xì)觀察會(huì)發(fā)現(xiàn)：如果當(dāng)前節(jié)點(diǎn)的前綴是 x ，那么其第一個(gè)子節(jié)點(diǎn)（就是最小的子節(jié)點(diǎn)）是 x * 10，第二個(gè)就是 x * 10 + 1，以此類推。因此：

• 深入到子節(jié)點(diǎn)就是 x * 10。
• 跳過(guò)所有孩子節(jié)點(diǎn)，直接到兄弟節(jié)點(diǎn)就是 x + 1。

ok，鋪墊地差不多了。

接下來(lái)，我們的重點(diǎn)是「如何計(jì)算給定節(jié)點(diǎn)的孩子節(jié)點(diǎn)的個(gè)數(shù)」。

這個(gè)過(guò)程和完全二叉樹計(jì)算節(jié)點(diǎn)個(gè)數(shù)并無(wú)二致，這個(gè)算法的時(shí)間復(fù)雜度應(yīng)該是?。如果不會(huì)的同學(xué)，可以參考力扣原題：?222. 完全二叉樹的節(jié)點(diǎn)個(gè)數(shù)^[3]?，這是一個(gè)難度為中等的題目。

?

因此這道題本身被劃分為 hard，一點(diǎn)都不為過(guò)。

?

這里簡(jiǎn)單說(shuō)下，計(jì)算給定節(jié)點(diǎn)的孩子節(jié)點(diǎn)的個(gè)數(shù)的思路， 我的 91 天學(xué)算法里出過(guò)這道題。

一種簡(jiǎn)單但非最優(yōu)的思路是分別計(jì)算左右子樹的深度。

• 如果當(dāng)前節(jié)點(diǎn)的左右子樹高度相同，那么左子樹是一個(gè)滿二叉樹，右子樹是一個(gè)完全二叉樹。
• 否則（左邊的高度大于右邊），那么左子樹是一個(gè)完全二叉樹，右子樹是一個(gè)滿二叉樹。

如果是滿二叉樹，當(dāng)前節(jié)點(diǎn)數(shù) 是 2 ^ depth，而對(duì)于完全二叉樹，我們繼續(xù)遞歸即可。

class?Solution:
????def?countNodes(self,?root):
????????if?not?root:
????????????return?0
????????ld?=?self.getDepth(root.left)
????????rd?=?self.getDepth(root.right)
????????if?ld?==?rd:
????????????return?2?**?ld?+?self.countNodes(root.right)
????????else:
????????????return?2?**?rd?+?self.countNodes(root.left)

????def?getDepth(self,?root):
????????if?not?root:
????????????return?0
????????return?1?+?self.getDepth(root.left)

「復(fù)雜度分析」

• 時(shí)間復(fù)雜度：
• 空間復(fù)雜度：

而這道題， 我們可以更簡(jiǎn)單和高效。

比如我們要計(jì)算 1 號(hào)節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)。

• 它的孩子節(jié)點(diǎn)個(gè)數(shù)是 。。。
• 它的孫子節(jié)點(diǎn)個(gè)數(shù)是 。。。
• 。。。

全部加起來(lái)即可。

它的孩子節(jié)點(diǎn)個(gè)數(shù)是?20 - 10 = 10?。也就是它的「右邊的兄弟節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)」?減去 它的「第一個(gè)子節(jié)點(diǎn)」。

由于是完全十叉樹，而不是滿十叉樹 。因此你需要考慮邊界情況，比如題目的 n 是 15。那么 1 的子節(jié)點(diǎn)個(gè)數(shù)就不是 20 - 10 = 10 了， 而是 15 - 10 + 1 = 16。

其他也是類似的過(guò)程， 我們只要：

• Go deeper and do the same thing

或者：

• Move to next neighbor and do the same thing

不斷重復(fù)，直到 m 降低到 0 。

代碼

def?count(c1,?c2,?n):
????steps?=?0
????while?c1?<=?n:
????????steps?+=?min(n?+?1,?c2)?-?c1
????????c1?*=?10
????????c2?*=?10
????return?steps
def?findKthNumber(n:?int,?k:?int)?->?int:
????cur?=?1
????k?=?k?-?1
????while?k?>?0:
????????steps?=?count(cur,?cur?+?1,?n)
????????if?steps?<=?k:
????????????cur?+=?1
????????????k?-=?steps
????????else:
????????????cur?*=?10
????????????k?-=?1
????return?cur
n,?m?=?map(int,?input().split())
print(findKthNumber(n,?m))

「復(fù)雜度分析」

• 時(shí)間復(fù)雜度：
• 空間復(fù)雜度：

總結(jié)

其中三道算法題從難度上來(lái)說(shuō)，基本都是困難難度。從內(nèi)容來(lái)看，基本都是力扣的換皮題，且都或多或少和樹有關(guān)。如果大家一開始沒(méi)有思路，建議大家先給出暴力的解法兜底，再畫圖或舉簡(jiǎn)單例子打開思路。

我也刷了很多字節(jié)的題了，還有一些難度比較大的題。如果你第一次做，那么需要你思考比較久才能想出來(lái)。加上面試緊張，很可能做不出來(lái)。這個(gè)時(shí)候就更需要你冷靜分析，先暴力打底，慢慢優(yōu)化。有時(shí)候即使給不了最優(yōu)解，讓面試官看出你的思路也很重要。比如小兔的棋盤^[4]?想出最優(yōu)解難度就不低，不過(guò)你可以先暴力 DFS 解決，再 DP 優(yōu)化會(huì)慢慢幫你打開思路。有時(shí)候面試官也會(huì)引導(dǎo)你，給你提示， 加上你剛才“發(fā)揮不錯(cuò)”，說(shuō)不定一下子就做出最優(yōu)解了，這個(gè)我深有體會(huì)。

另外要提醒大家的是， 刷題要適量，不要貪多。要完全理清一道題的來(lái)龍去脈。多問(wèn)幾個(gè)為什么。這道題暴力法怎么做？暴力法哪有問(wèn)題？怎么優(yōu)化？為什么選了這個(gè)算法就可以優(yōu)化？為什么這種算法要用這種數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)？

更多題解可以訪問(wèn)我的 LeetCode 題解倉(cāng)庫(kù)：https://github.com/azl397985856/leetcode 。目前已經(jīng) 36K+ star 啦。

Reference

推薦閱讀