概述#

Chapter 17 包含 26 道困難程度的程式設計題目，涵蓋位元運算、機率與隨機、動態規劃、圖論、字串搜尋、矩陣處理等進階主題。這些題目往往需要非直覺的思路突破或對資料結構的深入理解。

本章題目難度較高，部分題目需要結合多種演算法技巧。建議先熟悉 Chapters 1–15 的內容再挑戰。

題目列表#

位元運算與數學#

• 17.1 Add Without Plus：不使用 + 或任何算術運算子，實作兩數相加。
• 17.4 Missing Number：陣列 A 包含 0 到 n 的所有整數，只缺一個。元素以二進位表示，且只能使用「取得 A[i] 的第 j 個位元」這個操作，能否在 O(n) 時間內找到缺失的數？
• 17.6 Count of 2s：計算 0 到 n 之間所有數字中，數字 2 出現的總次數（包含 n）。
  • 範例：Input 25 → Output: 9（2, 12, 20, 21, 22, 23, 24, 25，其中 22 計兩次）
• 17.19 Missing Two：陣列包含 1 到 N 的所有整數，恰好缺少兩個數。能否在 O(N) 時間、O(1) 空間內找出？若缺少一個呢？

排列、隨機與機率#

• 17.2 Shuffle：以完美洗牌方式洗一副 52 張牌，要求 52! 種排列等機率出現。假設有完美隨機數產生器。
• 17.3 Random Set：從大小為 n 的陣列中，隨機挑選 m 個整數的集合，每個元素被選中的機率相等。

陣列與搜尋#

• 17.5 Letters and Numbers：陣列中混有字母與數字，找出含有相同數量字母與數字的最長子陣列。
• 17.10 Majority Element：陣列中的「多數元素」是出現次數超過一半的元素。在 O(N) 時間、O(1) 空間內找出（若不存在則回傳 -1）。
  • 範例：Input 1 2 5 9 5 9 5 5 5 → Output: 5
• 17.14 Smallest K：設計演算法找出陣列中最小的 K 個數。
• 17.18 Shortest Supersequence：給定一個較短陣列（元素皆不同）與一個較長陣列，在較長陣列中找出包含所有較短陣列元素的最短子陣列。
  • 範例：Input {1,5,9} | {7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7} → Output: [7, 10]
• 17.21 Volume of Histogram：給定長條圖（每個柱寬為 1），計算倒水後能容納的水量。
  • 範例：Input {0,0,4,0,0,6,0,0,3,0,5,0,1,0,0,0} → Output: 26
• 17.24 Max Submatrix：給定 NxN 的正負整數矩陣，找出總和最大的子矩陣。

字串處理#

• 17.7 Baby Names：每年政府公布最常見嬰兒名單與頻率，但同一個名字可能有多種拼法（如 John 與 Jon）。給定名字頻率清單與同義詞對，計算每個名字的真實頻率（同義詞關係具傳遞性與對稱性）。
• 17.11 Word Distance：在大型文字檔中，找出任意兩個指定單字之間的最短距離（以單字數計）。若需對同一檔案反覆查詢，如何最佳化？
• 17.13 Re-Space：文件中所有空白、標點和大寫均被移除。給定字典與文件字串，設計演算法重新插入空白，使無法識別的字元數量最少。
  • 範例：Input jessslookedjustliketimherbrother → Output: jess looked just like tim her brother（7 個無法識別字元）
• 17.15 Longest Word：給定單字清單，找出由清單中其他單字組合而成的最長單字。
  • 範例：Input cat, banana, dog, nana, walk, walker, dogwalker → Output: dogwalker
• 17.17 Multi Search：給定字串 b 與一組較短字串陣列 T，搜尋 b 中每個 T 中字串出現的位置。
• 17.22 Word Transformer：給定兩個等長且在字典中的單字，每次只改變一個字母，每步驟產生的新單字也必須在字典中，找出從起始單字到目標單字的轉換路徑。
  • 範例：Input DAMP, LIKE → Output: DAMP -> LAMP -> LIMP -> LIME -> LIKE
• 17.25 Word Rectangle：給定數百萬個單字，設計演算法找出最大的字母矩形，使每一列（橫向）與每一行（縱向）皆形成有效單字。所有列等長，所有行等高。

資料結構設計#

• 17.8 Circus Tower：馬戲團設計疊羅漢，每個人必須比下方的人矮且輕。給定每個人的身高與體重，找出最多人的疊羅漢排列。
  • 範例：Input (65,100)(70,150)(56,90)(75,190)(60,95)(68,110) → Output: 長度 6
• 17.9 Kth Multiple：找出第 k 個只含質因數 3、5、7 的數（不需以這些數為因數，例如 1 也符合）。前幾個數為：1, 3, 5, 7, 9, 15, 21…
• 17.12 BiNode：BiNode 有兩個指標（node1, node2），可同時表示二元樹或雙向鏈結串列。將以 BiNode 實作的二元搜尋樹轉換為雙向鏈結串列，原地操作，維持數值順序。
• 17.16 The Masseuse：按摩師面對一連串預約申請，每次預約之間需要 15 分鐘休息，因此不能接受相鄰的預約。找出能接受的最高總分鐘數。
  • 範例：Input {30,15,60,75,45,15,15,45} → Output: 180 分鐘（{30,60,45,45}）
• 17.20 Continuous Median：持續接收隨機產生的數值，維護當前所有數值的中位數。
• 17.23 Max Black Square：矩陣中每個像素為黑或白，找出四條邊都全為黑色像素的最大正方形子矩陣。
• 17.26 Sparse Similarity：兩份文件的相似度定義為「交集大小 / 聯集大小」（Jaccard 相似度）。給定大量文件（每份各有 distinct 元素），找出所有相似度大於 0 的文件對及其相似度。
  • 範例：{1,5,3} 與 {1,7,2,3} 的相似度為 0.4（交集 2，聯集 5）

題型分類總結#

Hard 題目通常有多種解法，且時間複雜度差異顯著。面試時應先說出 brute force 解，再逐步最佳化，並主動討論各解法的時間與空間複雜度取捨。