6.5   練習¶

6.5.1   知識鞏固¶

1.   發生雜湊衝突後怎樣查詢¶

一個雜湊表有 5 個桶，雜湊函式為 \(h(x)=x \bmod 5\)，衝突時把元素依次放進該桶的串列中。 依次插入 [1, 6, 11, 7]：

1. 寫出 0～4 號桶中的內容；
2. 查詢 6 時會先進入哪個桶，並依次檢查哪些元素？
3. 根據第 1 問寫出的桶內容，後插入的元素是否覆蓋了先插入的元素？結合這種衝突處理方式說明理由。

2.   雜湊表擴容後元素去哪兒¶

一個使用鏈式位址的雜湊表原有 5 個桶，雜湊函式為 \(h(x)=x\bmod5\)。 鍵 [1, 6, 11] 都在 1 號桶中。

現在把雜湊表擴容為 7 個桶，雜湊函式相應變為 \(h(x)=x\bmod7\)：

1. 分別計算 1、6、11 的新桶號。
2. 擴容後哪些桶中有元素？
3. 擴容時能否把原來 1 號桶中的串列原樣複製到新的 1 號桶？結合第 1、2 問的結果說明理由。

3.   刪除 6 後還能找到 11 嗎¶

一個雜湊表有 5 個位置，索引為 0～4，雜湊函式為 \(h(x)=x\bmod5\)。 發生衝突時，從雜湊函式算出的索引開始，向右尋找第一個空位。

依次插入 [1, 6, 11]：

1. 三個數最終分別放在哪個索引？
2. 查詢 11 時，會依次檢查哪些索引？
3. 如果刪除 6 時直接把它的位置改成“從未使用的空位”，而查詢遇到空位就停止， 再查詢 11 時會發生什麼？這個查詢結果是否正確？如果有問題，應怎樣避免？

6.5.2   程式設計練習¶

1.   比較兩個字串的字元組成¶

給定兩個只含小寫英文字母的字串 s 和 t。 可以任意調整 s 中字元的位置，但不能新增、刪除或替換字元。

請判斷調整後能否得到 t；可以則返回 true，否則返回 false。 請使用雜湊表記錄各字母的出現次數，不對字串中的字元排序。

LeetCode 題目解析

歡迎在評論區留下你的見解、問題或建議