字節跳動的算法面試題是什么難度？ · ttttt

# 字節跳動的算法面試題是什么難度？ # 字節跳動的算法面試題是什么難度？由于 lucifer 我是一個小前端，最近也在準備寫一個《前端如何搞定算法面試》的專欄，因此最近沒少看各大公司的面試題。都說字節跳動算法題比較難，我就先拿 ta 下手，做了幾套。這次我們就拿一套 `2018 年的前端校招（第四批）`來看下字節的算法筆試題的難度幾何。地址：<https://www.nowcoder.com/test/8536639/summary> > 實際上，這套字節的前端崗位筆試題和后端以及算法崗位的筆試題也只有一道題目（紅包的設計題被換成了另外一個設計題）不一樣而已，因此也不需要擔心你不是前端，題目類型和難度和你的崗位不匹配。這套題一共四道題，兩道問答題，兩道編程題。其中一道問答題是 LeetCode 426 的原題，只不過題型變成了找茬（改錯）。可惜的是 LeetCode 的 426 題是一個會員題目，沒有會員的就看不來了。不過，劍指 Offer 正好也有這個題，并且力扣將劍指 Offer 全部的題目都 OJ 化了。這道題大家可以去 <https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof> 提交答案。簡單說一下這個題目的思路，我們只需要中序遍歷即可得到一個有序的數列，同時在中序遍歷過程中將 pre 和 cur 節點通過指針串起來即可。另一個問答是紅包題目，這里不多說了。我們重點看一下剩下兩個算法編程題。 ![](https://img.kancloud.cn/05/86/0586e3f19c229575cf50b4342797cd8e_1381x1080.jpg) > 兩個問答題由于不能在線判題，我沒有做，只做了剩下兩個編程題。 ## 球隊比賽第一個編程題是一個球隊比賽的題目。 ### 題目描述有三只球隊，每只球隊編號分別為球隊 1，球隊 2，球隊 3，這三只球隊一共需要進行 n 場比賽。現在已經踢完了 k 場比賽，每場比賽不能打平，踢贏一場比賽得一分，輸了不得分不減分。已知球隊 1 和球隊 2 的比分相差 d1 分，球隊 2 和球隊 3 的比分相差 d2 分，每場比賽可以任意選擇兩只隊伍進行。求如果打完最后的 (n-k) 場比賽，有沒有可能三只球隊的分數打平。 ### 思路假設球隊 1，球隊 2，球隊 3 此時的勝利次數分別為 a，b，c，球隊 1，球隊 2，球隊 3 總的勝利次數分別為 n1，n2，n3。我一開始的想法是只要保證 n1，n2，n3 相等且都小于等于 n / 3 即可。如果題目給了 n1，n2，n3 的值就直接： ``` <pre class="calibre18">``` print(n1 == n2 == n3 == n / 3) ``` ``` 可是不僅 n1，n2，n3 沒給， a，b，c 也沒有給。實際上此時我們的信息僅僅是： ``` <pre class="calibre18">``` ① 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 的求解數學方程就是中學數學難度，三個等式化簡一下即可，具體見下方代碼區域。 - a 只需要再次贏得 n / 3 - a 次 - b 只需要再次贏得 n / 3 - b 次 - c 只需要再次贏得 n / 3 - c 次 ``` <pre class="calibre18">``` n1 = a + n / 3 - a = n / 3 n2 = b + (n / 3 - b) = n / 3 n3 = c + (n / 3 - c) = n / 3 ``` ``` ### 代碼(Python) > 牛客有點讓人不爽，需要 print 而不是 return ``` <pre class="calibre18">``` 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') ``` ``` **復雜度分析** - 時間復雜度：O(t)O(t)O(t) - 空間復雜度：O(t)O(t)O(t) ### 小結感覺這個難度也就是力扣中等水平吧，力扣也有一些數學等式轉換的題目，比如 [494.target-sum](https://github.com/azl397985856/leetcode/blob/master/problems/494.target-sum.md "494.target-sum") ## 轉換字符串 ### 題目描述有一個僅包含’a’和’b’兩種字符的字符串 s，長度為 n，每次操作可以把一個字符做一次轉換（把一個’a’設置為’b’，或者把一個’b’置成’a’)；但是操作的次數有上限 m，問在有限的操作數范圍內，能夠得到最大連續的相同字符的子串的長度是多少。 ### 思路看完題我就有種似曾相識的感覺。 > 每次對妹子說出這句話的時候，她們都會覺得好假 ^\_^ 不過這次是真的。 ”哦，不！每次都是真的“。這道題其實就是我之前寫的滑動窗口的一道題[【1004. 最大連續 1 的個數 III】滑動窗口（Python3）](https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/1004-zui-da-lian-xu-1de-ge-shu-iii-hua-dong-chuang/ "【1004. 最大連續 1 的個數 III】滑動窗口（Python3）")的換皮題。專題地址：<https://github.com/azl397985856/leetcode/blob/master/thinkings/slide-window.md> 所以說，如果這道題你完全沒有思路的話。說明： - 抽象能力不夠。 - 滑動窗口問題理解不到位。第二個問題可以看我上面貼的地址，仔細讀讀，并完成課后練習即可解決。第一個問題就比較困難了，不過多看我的題解也可以慢慢提升的。比如： - [《割繩子》](https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/ "《割繩子》") 實際上就是 [343. 整數拆分](https://lucifer.ren/blog/2020/05/16/343.integer-break/ "343. 整數拆分") 的換皮題。 - 力扣 230 和力扣 645 就是換皮題，詳情參考[位運算專題](https://lucifer.ren/blog/2020/03/24/bit/ "位運算專題") - 以及 [你的衣服我扒了 - 《最長公共子序列》](https://lucifer.ren/blog/2020/07/01/LCS/) - 以及 [穿上衣服我就不認識你了？來聊聊最長上升子序列](https://lucifer.ren/blog/2020/06/20/LIS/) - 以及 [一招吃遍力扣四道題，媽媽再也不用擔心我被套路啦～](https://lucifer.ren/blog/2020/06/13/%E5%88%A0%E9%99%A4%E9%97%AE%E9%A2%98/) - 等等回歸這道題。其實我們只需要稍微抽象一下，就是一個純算法題。抽象的另外一個好處則是將很多不同的題目返璞歸真，從而可以在茫茫題海中逃脫。這也是我開啟[《我是你的媽媽呀》](https://lucifer.ren/blog/2020/08/03/mother-01/) 的原因之一。如果我們把 a 看成是 0 ， b 看成是 1。或者將 b 看成 1， a 看成 0。不就抽象成了： ``` <pre class="calibre18">``` 給定一個由若干 0 和 1 組成的數組 A，我們最多可以將 m 個值從 0 變成 1 。返回僅包含 1 的最長（連續）子數組的長度。 ``` ``` 這就是力扣 [1004. 最大連續 1 的個數 III](https://leetcode-cn.com/problems/max-consecutive-ones-iii/solution/1004-zui-da-lian-xu-1de-ge-shu-iii-hua-dong-chuang/) 原題。因此實際上我們要求的是上面兩種情況: 1. a 表示 0， b 表示 1 2. a 表示 1， b 表示 0 的較大值。 > lucifer 小提示：其實我們也可以僅僅考慮一種情況，比如 a 看成是 0 ， b 看成是 1。這個時候，我們操作變成了兩種情況，0 變成 1 或者 1 變成 0，同時求解的也變成了最長連續 0 或者最長連續 1 。由于這種抽象操作起來更麻煩，我們不考慮。問題得到了抽象就好解決了。我們只需要記錄下加入窗口的是 0 還是 1： - 如果是 1，我們什么都不用做 - 如果是 0，我們將 m 減 1 相應地，我們需要記錄移除窗口的是 0 還是 1: - 如果是 1，我們什么都不做 - 如果是 0，說明加進來的時候就是 1，加進來的時候我們 m 減去了 1，這個時候我們再加 1。 > lucifer 小提示：實際上題目中是求**連續** a 或者 b 的長度。看到連續，大家也應該有滑動窗口的敏感度，別管行不行，想到總該有的。我們拿 A = \[1, 1, 0, 1, 0, 1\], m = 1 來說。看下算法的具體過程： > lucifer 小提示：左側的數字表示此時窗口大小，黃色格子表示修補的墻，黑色方框表示的是窗口。 ![](https://img.kancloud.cn/62/36/6236deb5f14e162619f39ab1cdbca471_748x204.jpg) 這里我形象地將 0 看成是洞，1 看成是墻，我們的目標就是補洞，使得連續的墻最長。 ![](https://img.kancloud.cn/17/93/1793636fdfb815f98395bfd4e1b2ec95_668x184.jpg) 每次碰到一個洞，我們都去不加選擇地修補。由于 m 等于 1，也就是說我們最多補一個洞。因此需要在修補超過一個洞的時候，我們需要調整窗口范圍，使得窗口內最多修補一個墻。由于窗口表示的就是連續的墻（已有的或者修補的），因此最終我們返回窗口的最大值即可。 ![](https://img.kancloud.cn/d2/4b/d24b4d12a8ad9b51115e72a6f4ce2e4b_1202x490.jpg) > 由于下面的圖窗口內有兩個洞，這和”最多補一個洞“沖突，我們需要收縮窗口使得滿足“最多補一個洞”的先決條件。 ![](https://img.kancloud.cn/d3/15/d315f4969ae2b53f5f434e3e59d58422_870x406.jpg) 因此最大的窗口就是 max(2, 3, 4, ...) = 4。 > lucifer 小提示：可以看出我們不加選擇地修補了所有的洞，并調整窗口，使得窗口內最多有 m 個修補的洞，因此窗口的最大值就是答案。然而實際上，我們并不需要真的”修補“（0 變成 1），而是僅僅修改 m 的值即可。我們先來看下抽象之后的**其中一種情況**的代碼： ``` <pre class="calibre18">``` 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 ``` ``` 因此**完整代碼**就是： ``` <pre class="calibre18">``` 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 會生成兩個不同的數組。我只是為了方便大家理解才新建的兩個數組，實際上根本不需要，具體見后面的代碼. ### 代碼(Python) ``` <pre class="calibre18">``` i = 0 n, m = map(int, input().split(" ")) s = input() ans = 0 k = m # 存一下，后面也要用這個初始值 # 修補 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 # 修補 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)) ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) ### 小結這道題就是一道換了皮的力扣題，難度中等。如果你能將問題抽象，同時又懂得滑動窗口，那這道題就很容易。我看了題解區的參考答案，內容比較混亂，不夠清晰。這也是我寫下這篇文章的原因之一。 ## 總結這一套字節跳動的題目一共四道，一道設計題，三道算法題。其中三道算法題從難度上來說，基本都是中等難度。從內容來看，基本都是力扣的換皮題。但是如果我不說他們是換皮題，你們能發現么？如果你可以的話，說明你的抽象能力已經略有小成了。如果看不出來也沒有關系，關注我。手把手扒皮給你們看，扒多了慢慢就會了。切記，不要盲目做題！如果你做了很多題，這幾道題還是看不出套路，說明你該緩緩，改變下刷題方式了。更多題解可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 36K+ star 啦。關注公眾號力扣加加，努力用清晰直白的語言還原解題思路，并且有大量圖解，手把手教你識別套路，高效刷題。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)