算法D6 | 哈希表基礎 | 242.有效的字母異位詞 349. 兩個數組的交集 202. 快樂數

哈希表理論基礎?

建議:大家要了解哈希表的內部實現原理,哈希函數,哈希碰撞,以及常見哈希表的區(qū)別,數組,set?和map。??

什么時候想到用哈希法,當我們遇到了要快速判斷一個元素是否出現集合里的時候,就要考慮哈希法。??這句話很重要,大家在做哈希表題目都要思考這句話。?文章講解

在D4已經遇到了set/map的結構對比了,這里再補充一下對比。(from carlprogrming)

242.有效的字母異位詞?

建議:?這道題目,大家可以感受到?數組?用來做哈希表?給我們帶來的遍歷之處。 題目鏈接/文章講解/視頻講解。

第一反應是用python的字典結構來記錄character出現的個數,再比較兩個字典是否相同。如果是一個字典呢?第二個字典在原字典基礎上計數遞減,那么省了一半的空間,如果不用字母作為Key,而是數值(當前字母和字母a的差值),那么可以直接用數組結構(array), 因為數組也是由Index和value的對應關系來表示的, 和字典的key, value結構類似底層都是hash table。能用數組的時候盡量用數組,比另外兩種結構set/map要快。

Python方法一:字典

Python方法二:數組

數組方法需要把index確定為int格式, python里用ord()函數實現,Python ord() 函數是一個內置函數,可以將一個字符轉換為對應的 ASCII 或 Unicode 數值,或者將一個 ASCII 或 Unicode 數值轉換為對應的字符。這里補充一些Python的編碼的知識:非常詳細的字符編碼講解,ASCII、GB2312、GBK、Unicode、UTF-8等知識點都有

C++方法二:數組

僅實現數組方法,聲明一個指定長度元素全為0的數組的方法: record[26] = {0}。

349.?兩個數組的交集?

建議:本題就開始考慮?什么時候用set?什么時候用數組,本題其實是使用set的好題,但是后來力扣改了題目描述和?測試用例,添加了?0?<=?nums1[i],?nums2[i]?<=?1000?條件,所以使用數組也可以了,不過建議大家忽略這個條件。?嘗試去使用set。 題目鏈接/文章講解/視頻講解

求集合的交集, 再轉換成數組輸出即可。

Python 方法一: set

Python 方法二:數組

leetcode后續(xù)把array中元素的范圍限制在了[0, 1000], 所以這個題可以用數組實現。如果數字范圍是可變的,那么就不是和數組,需要的空間也是無限大。

C++ 方法一: set - unordered_set

把vector內的元素全部放到unordered_set 參考line27。

C++ 方法二:數組?

202.?快樂數?

建議:這道題目也是set的應用,其實和上一題差不多,就是?套在快樂數一個殼子。題目鏈接/文章講解。

Python 方法:

求digits平方參考C++方法,str的轉換也是需要消耗時間的。

C++ 方法:

1.?兩數之和?

建議:本題雖然是?力扣第一題,但是還是挺難的,也是?代碼隨想錄中?數組,set之后,使用map解決哈希問題的第一題。?

建議大家先看視頻講解,然后嘗試自己寫代碼,在看文章講解,加深印象。題目鏈接/文章講解/視頻講解。

Python 方法:

C++ 方法:

注意C++中函數return {}; 不能省略。 返回list 直接寫 {ele1, ele2, ...} 即可; 找到unordered_map對應key的value, 使用it-> second:

it表示按key找到的整個item。

it->first 表示的是這個元素的key的值;

it->second 表示的是這個元素的value的值。

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成,瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明:文章內容(如有圖片或視頻亦包括在內)由作者上傳并發(fā)布,文章內容僅代表作者本人觀點,簡書系信息發(fā)布平臺,僅提供信息存儲服務。

相關閱讀更多精彩內容

友情鏈接更多精彩內容