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

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

字節(jié)跳動的算法面試題是什么難度？

由于 lucifer 我是一個小前端， 最近也在準(zhǔn)備寫一個《前端如何搞定算法面試》的專欄，因此最近沒少看各大公司的面試題。都說字節(jié)跳動算法題比較難，我就先拿 ta 下手,?做了幾套。這次我們就拿一套?2018 年的前端校招（第四批）來看下字節(jié)的算法筆試題的難度幾何。地址：https://www.nowcoder.com/test/8536639/summary

?

實際上，這套字節(jié)的前端崗位筆試題和后端以及算法崗位的筆試題也只有一道題目（紅包的設(shè)計題被換成了另外一個設(shè)計題）不一樣而已，因此也不需要擔(dān)心你不是前端，題目類型和難度和你的崗位不匹配。

?

這套題一共四道題， 兩道問答題， 兩道編程題。

其中一道問答題是 LeetCode 426 的原題，只不過題型變成了找茬（改錯）?？上У氖?LeetCode 的 426 題是一個會員題目，沒有會員的就看不來了。不過，劍指 Offer 正好也有這個題，并且力扣將劍指 Offer 全部的題目都 OJ 化了。這道題大家可以去 https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof 提交答案。簡單說一下這個題目的思路，我們只需要中序遍歷即可得到一個有序的數(shù)列，同時在中序遍歷過程中將 pre 和 cur 節(jié)點通過指針串起來即可。

另一個問答是紅包題目，這里不多說了。我們重點看一下剩下兩個算法編程題。

?

兩個問答題由于不能在線判題，我沒有做，只做了剩下兩個編程題。

?

球隊比賽

第一個編程題是一個球隊比賽的題目。

題目描述

有三只球隊，每只球隊編號分別為球隊 1，球隊 2，球隊 3，這三只球隊一共需要進(jìn)行 n 場比賽?，F(xiàn)在已經(jīng)踢完了 k 場比賽，每場比賽不能打平，踢贏一場比賽得一分，輸了不得分不減分。已知球隊 1 和球隊 2 的比分相差 d1 分，球隊 2 和球隊 3 的比分相差 d2 分，每場比賽可以任意選擇兩只隊伍進(jìn)行。求如果打完最后的 (n-k) 場比賽，有沒有可能三只球隊的分?jǐn)?shù)打平。

思路

假設(shè)球隊 1，球隊 2，球隊 3 此時的勝利次數(shù)分別為 a，b，c，球隊 1，球隊 2，球隊 3 總的勝利次數(shù)分別為 n1，n2，n3。

我一開始的想法是只要保證 n1，n2，n3 相等且都小于等于 n / 3 即可。如果題目給了 n1，n2，n3 的值就直接：

print(n1?==?n2?==?n3?==?n?/?3)

可是不僅 n1，n2，n3 沒給， a，b，c 也沒有給。

實際上此時我們的信息僅僅是：

①?a?+?b?+?c?=?k
②?a?-?b?=?d1?or?b?-?a?=?d1
③?b?-?c?=?d2?or?c?-?b?=?d2

其中 k 和 d1，d2 是已知的。a ，b，c 是未知的。也就是說我們需要枚舉所有的 a，b，c 可能性，解方程求出合法的 a，b，c，并且 合法的 a，b，c 都小于等于 n / 3 即可。

?

這個 a,b,c 的求解數(shù)學(xué)方程就是中學(xué)數(shù)學(xué)難度， 三個等式化簡一下即可，具體見下方代碼區(qū)域。

?

• a 只需要再次贏得 n / 3 - a 次
• b 只需要再次贏得 n / 3 - b 次
• c 只需要再次贏得 n / 3 - c 次

n1?=?a?+?n?/?3?-?a?=?n?/?3
n2?=?b?+?(n?/?3?-?b)?=?n?/?3
n3?=?c?+?(n?/?3?-?c)?=?n?/?3

代碼(Python)

?

?？陀悬c讓人不爽， 需要 print 而不是 return

?

t?=?int(input())
for?i?in?range(t):
????n,?k,?d1,?d2?=?map(int,?input().split("?"))
????if?n?%?3?!=?0:
????????print('no')
????????continue
????abcs?=?[]
????for?r1?in?[-1,?1]:
????????for?r2?in?[-1,?1]:
????????????a?=?(k?+?2?*?r1?*?d1?+?r2?*?d2)?/?3
????????????b?=?(k?+?-1?*?r1?*?d1?+?r2?*?d2)?/?3
????????????c?=?(k?+?-1?*?r1?*?d1?+?-2?*?r2?*?d2)?/?3
????????????a?+?r1
????????????if??0?<=?a?<=?k?and?0?<=?b?<=?k?and?0?<=?c?<=?k?and?a.is_integer()?and?b.is_integer()?and?c.is_integer():
????????????????abcs.append([a,?b,?c])
????flag?=?False
????for?abc?in?abcs:
????????if?len(abc)?>?0?and?max(abc)?<=?n?/?3:
????????????flag?=?True
????????????break
????if?flag:
????????print('yes')
????else:
????????print('no')

「復(fù)雜度分析」

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

小結(jié)

感覺這個難度也就是力扣中等水平吧，力扣也有一些數(shù)學(xué)等式轉(zhuǎn)換的題目， 比如?494.target-sum^[1]

轉(zhuǎn)換字符串

題目描述

有一個僅包含’a’和’b’兩種字符的字符串 s，長度為 n，每次操作可以把一個字符做一次轉(zhuǎn)換（把一個’a’設(shè)置為’b’，或者把一個’b’置成’a’)；但是操作的次數(shù)有上限 m，問在有限的操作數(shù)范圍內(nèi)，能夠得到最大連續(xù)的相同字符的子串的長度是多少。

思路

看完題我就有種似曾相識的感覺。

?

每次對妹子說出這句話的時候，她們都會覺得好假 ^_^

?

不過這次是真的?！迸叮?！每次都是真的“。這道題其實就是我之前寫的滑動窗口的一道題【1004. 最大連續(xù) 1 的個數(shù) III】滑動窗口（Python3）^[2]的換皮題。專題地址：https://github.com/azl397985856/leetcode/blob/master/thinkings/slide-window.md

所以說，如果這道題你完全沒有思路的話。說明：

• 抽象能力不夠。
• 滑動窗口問題理解不到位。

第二個問題可以看我上面貼的地址，仔細(xì)讀讀，并完成課后練習(xí)即可解決。

第一個問題就比較困難了， 不過多看我的題解也可以慢慢提升的。比如：

• 《割繩子》^[3]?實際上就是?343. 整數(shù)拆分^[4]?的換皮題。

• 力扣 230 和 力扣 645 就是換皮題，詳情參考位運(yùn)算專題^[5]

• 以及?你的衣服我扒了 - 《最長公共子序列》

• 以及?穿上衣服我就不認(rèn)識你了？來聊聊最長上升子序列

• 以及?一招吃遍力扣四道題，媽媽再也不用擔(dān)心我被套路啦～

• 等等

回歸這道題。其實我們只需要稍微抽象一下， 就是一個純算法題。抽象的另外一個好處則是將很多不同的題目返璞歸真，從而可以在茫茫題海中逃脫。這也是我開啟《我是你的媽媽呀》 - 第一期?的原因之一。

如果我們把 a 看成是 0 ， b 看成是 1?；蛘邔?b 看成 1， a 看成 0。不就抽象成了：

給定一個由若干?0?和 1 組成的數(shù)組 A，我們最多可以將 m 個值從?0?變成 1 。

返回僅包含 1 的最長（連續(xù)）子數(shù)組的長度。

這就是 力扣 1004. 最大連續(xù) 1 的個數(shù) III 原題。

因此實際上我們要求的是上面兩種情況:

1. a 表示 0， b 表示 1
2. a 表示 1， b 表示 0

的較大值。

?

lucifer 小提示：其實我們也可以僅僅考慮一種情況，比如 a 看成是 0 ， b 看成是 1。這個時候， 我們操作變成了兩種情況，0 變成 1 或者 1 變成 0，同時求解的也變成了最長連續(xù) 0 或者 最長連續(xù) 1 。由于這種抽象操作起來更麻煩， 我們不考慮。

?

問題得到了抽象就好解決了。我們只需要記錄下加入窗口的是 0 還是 1：

• 如果是 1，我們什么都不用做
• 如果是 0，我們將 m 減 1

相應(yīng)地，我們需要記錄移除窗口的是 0 還是 1:

• 如果是 1，我們什么都不做
• 如果是 0，說明加進(jìn)來的時候就是 1，加進(jìn)來的時候我們 m 減去了 1，這個時候我們再加 1。

?

lucifer 小提示：實際上題目中是求「連續(xù)」?a 或者 b 的長度?？吹竭B續(xù)，大家也應(yīng)該有滑動窗口的敏感度， 別管行不行， 想到總該有的。

?

我們拿 A = [1, 1, 0, 1, 0, 1], m = 1 來說?？聪滤惴ǖ木唧w過程：

?

lucifer 小提示：左側(cè)的數(shù)字表示此時窗口大小，黃色格子表示修補(bǔ)的墻，黑色方框表示的是窗口。

?

這里我形象地將 0 看成是洞，1 看成是墻， 我們的目標(biāo)就是補(bǔ)洞，使得連續(xù)的墻最長。

每次碰到一個洞，我們都去不加選擇地修補(bǔ)。由于 m 等于 1， 也就是說我們最多補(bǔ)一個洞。因此需要在修補(bǔ)超過一個洞的時候，我們需要調(diào)整窗口范圍，使得窗口內(nèi)最多修補(bǔ)一個墻。由于窗口表示的就是連續(xù)的墻（已有的或者修補(bǔ)的），因此最終我們返回窗口的最大值即可。

?

由于下面的圖窗口內(nèi)有兩個洞，這和”最多補(bǔ)一個洞“沖突， 我們需要收縮窗口使得滿足“最多補(bǔ)一個洞”的先決條件。

?

因此最大的窗口就是 max(2, 3, 4, ...) = 4。

?

lucifer 小提示：可以看出我們不加選擇地修補(bǔ)了所有的洞，并調(diào)整窗口，使得窗口內(nèi)最多有 m 個修補(bǔ)的洞，因此窗口的最大值就是答案。然而實際上，我們并不需要真的”修補(bǔ)“（0 變成 1），而是僅僅修改 m 的值即可。

?

我們先來看下抽象之后的「其中一種情況」的代碼：

class?Solution:
????def?longestOnes(self,?A:?List[int],?m:?int)?->?int:
????????i?=?0
????????for?j?in?range(len(A)):
????????????m?-=?1?-?A[j]
????????????if?m?0:
????????????????m?+=?1?-?A[i]
????????????????i?+=?1
????????return?j?-?i?+?1

因此「完整代碼」就是：

class?Solution:
????def?longestOnes(self,?A:?List[int],?m:?int)?->?int:
????????i?=?0
????????for?j?in?range(len(A)):
????????????m?-=?1?-?A[j]
????????????if?m?0:
????????????????m?+=?1?-?A[i]
????????????????i?+=?1
????????return?j?-?i?+?1
????def?longestAorB(self,?A:List[int],?m:?int)?->?int:
????????return?max(self.longestOnes(map(lambda?x:?0?if?x?==?'a'?else?1,?A)?,m),?self.longestOnes(map(lambda?x:?1?if?x?==?'a'?else?0,?A),m))

這里的兩個 map 會生成兩個不同的數(shù)組。我只是為了方便大家理解才新建的兩個數(shù)組， 實際上根本不需要，具體見后面的代碼.

代碼(Python)

i?=?0
n,?m?=?map(int,?input().split("?"))
s?=?input()
ans?=?0
k?=?m?#???存一下，后面也要用這個初始值
#?修補(bǔ)?b
for?j?in?range(n):
????m?-=?ord(s[j])?-?ord('a')
????if?m?0:
????????m?+=?ord(s[i])?-?ord('a')
????????i?+=?1
ans?=?j?-?i?+?1
i?=?0
#?修補(bǔ)?a
for?j?in?range(n):
????k?+=?ord(s[j])?-?ord('b')
????if?k?0:
????????k?-=?ord(s[i])?-?ord('b')
????????i?+=?1
print(max(ans,?j?-?i?+?1))

「復(fù)雜度分析」

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

小結(jié)

這道題就是一道換了皮的力扣題，難度中等。如果你能將問題抽象，同時又懂得滑動窗口，那這道題就很容易。我看了題解區(qū)的參考答案， 內(nèi)容比較混亂，不夠清晰。這也是我寫下這篇文章的原因之一。

總結(jié)

這一套字節(jié)跳動的題目一共四道，一道設(shè)計題，三道算法題。

其中三道算法題從難度上來說，基本都是中等難度。從內(nèi)容來看，基本都是力扣的換皮題。但是如果我不說他們是換皮題， 你們能發(fā)現(xiàn)么？如果你可以的話，說明你的抽象能力已經(jīng)略有小成了。如果看不出來也沒有關(guān)系，關(guān)注我。手把手扒皮給你們看，扒多了慢慢就會了。切記，不要盲目做題！如果你做了很多題， 這幾道題還是看不出套路，說明你該緩緩，改變下刷題方式了。

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

Reference

1、力扣刷題插件

2、提前批算法工程師面試之路

3、動態(tài)規(guī)劃問題為什么要畫表格？

4、《丟雞蛋問題》重制版來襲～

5、用最優(yōu)雅的方式打開終端