8月，互聯網大廠們的校招已經陸續打響！不少童鞋們也喜迎了字節跳動第一批難不死人的研發類筆試題~筆試結束，哀嚎聲一片。當然也有解題高手淡定的表示”可以準備下一輪面試了“。相信參加了/將要參加研發筆試的旁友們都想知道神秘的出題人到底是怎麼想的？

為此，我們特地化作出題人肚裡的小字節蟲，為大家奉上乾貨：研發筆試的題目類別以及解題思路！

第一類：世界盃開幕式

題目大意：01矩陣，求其中的八連通塊的數量。

題解：經典題，BFS 或 DFS。

第二類：文章病句標識

題目大意：求區間合併問題。

題解：經典題，排序後合併區間。

第三類：積分卡牌遊戲

題目大意：有n張卡牌，每張上面有兩個數字x,y，兩人各自選擇若干張卡牌，求他們各自選擇的卡牌的x的總和相等時，所有選擇的卡牌的y的總和的最大值。

題解：動態規劃。

​d[i][j]​ 表示前i張牌，兩人所選擇的牌的差值為j時的最大值，轉移方程為:

​d[i][j] = max(d[i-1][j], d[i-1][j-x[i]] + y[i], d[i-1][j+x[i]] + y[i])​

注意: 空間可能不夠用，由於狀態 ​d[i]​ 只與狀態 ​d[i-1]​ 有關，可以使用滾動數組來優化空間。

時間複雜度 ​O(n*Σx)​

第四類：區間最大最小值

題目大意：給定兩個序列a、b，求有多少個區間[l, r]滿足，區間a[l, r]的最大值小於區間b[l, r]的最小值

題解：

解法1

1. 通過觀察發現，固定區間的左端點 ​l​，隨著右端點 ​r​ 的右移，區間 ​a[l,r]​ 的最大值只會變大，區間 ​b[l,r]​ 的最小值只會變小，具有單調性
2. 因此我們枚舉區間的左端點 ​l​，使用二分查找的方法，找到 ​a[l,r]​ 的最大值小於 ​b[l,r]​ 的最小值的臨界點 ​r​，此時答案增加計數 ​(r - l + 1)​
3. 其中區間最值可以使用 ST 表查詢，單次查詢複雜度為常數
4. 時間複雜度 ​O(n*log(n))​

解法2

1. 通過觀察發現，對於兩個滿足條件的區間 ​[l, r]​和 ​[l', r']​，若 ​l'>=l​，那麼 ​r'>=r​。
2. 因此我們可以使用兩個指針 ​l​ 和 ​r​，初始都在序列的第一個位置，並重復以下過程:
3. 一直向右移動l，直到滿足 ​a[l,r]​ 的最大值 ​< b[l,r]​ 的最小值或者 ​l>r​ 為止
4. 答案增加計數 ​(r - l + 1)​
5. ​r​ 向右移動一個單位
6. 使用兩個單調隊列分別維護 ​a[l,r]​ 的最大值和 ​b[l,r]​ 的最小值。
7. 時間複雜度 ​O(n)​

第五類：直播愛好者

題目大意：本題是區間調度問題，可以用貪心算法實現。

題解：

1. 本題需要注意的是直播可能跨天，因此我們可以將原始輸入複製一份，使其擴展到​2*M​的時間區間內，再進行貪心算法求解
2. 貪心算法基於優先選擇結束時間最早的直播節目。因此我們可以將將輸入數據按照結束時間排序
3. 排序後，我們可以用兩層循環，外層循環選定一個直播節目作為起點，內層循環用貪心算法獲取這個節目結束到第二天該節目的開始時間之前，能夠儘早結束的節目。時間複雜度為 ​O(n^2)​

解法2

1. 解法1在確定第一個區間之後使用的貪心算法存在大量的重複計算，而對於某個區間 ​i​ 的下一個滿足 ​t[i]≤s[j]​ 的所有 ​j​ 中 ​t[j]​ 最小的那個區間是確定的，可以預處理並記錄對應關係，此部分時間複雜度為 ​O(n*logn)​
2. 得到對應關係後我們可以使用倍增法，維護一個數組 ​next[i][j]​ 表示區間 ​i​ 在走 ​2^j​ 步後所到達的區間，再利用倍增函數對於每個區間只需要 ​O(logn)​ 的複雜度即可找到答案，因此整個算法的複雜度降為 ​O(n*logn)​

解法3

1. 本題還有一種除去排序外只需時間複雜度 ​O(n)​ 的解法。有興趣的同學可以試著思考一下並在本文下討論哦

看完以上筆試解密，是不是頓時覺得楊超越上身，充滿力量！

已經參加了第一場研發筆試的童鞋，可以對個人的筆試結果做個判斷~即將要迎戰之後幾場筆試的朋友們，相信經過認真總結和反覆練習，優秀的你一定能斬獲字節跳動的offer！

之後幾場研發類崗位筆試安排：

8月25日；9月9日、20日；10月07日、20日；11月11日；12月2日；1月6日

有其他招聘問題，歡迎點擊字節跳動招聘Q&A頁面：https://job.bytedance.com/campus/q&a 瞭解更多信息~

我們提供研發、產品、運營、職能等各類崗位5000+offer，歡迎點擊文末

閱讀更多 字節跳動招聘 的文章

關鍵字: 出題 筆試 字節