昨日回顧

昨天我們開始了哈希表的學(xué)習(xí)，講解了哈希表的集中實現(xiàn)方式。并通過一道 設(shè)計哈希集合 的題目，讓我們將哈希表的理論轉(zhuǎn)化為實踐。

今天，我們就開始正式學(xué)習(xí)哈希表在Python與Java中的使用方式。在Java中，哈希表有兩個數(shù)據(jù)類型 HashMap 與 HashSet，它們對應(yīng)Python中的 dict 與 set ，下面我們開始分類學(xué)習(xí)！

HashSet & set

我們在昨天的設(shè)計哈希集合題目中，對HashSet已經(jīng)有了一個初步的了解。HashSet與set 是一個無序不重復(fù)的元素集，集合在我們?nèi)粘Ｋ惴ㄖ袑?shù)組去重、已搜索的節(jié)點記錄等有很大幫助。

具體方法如下：

Python針對集合還可存在update更新、difference 并可以使用 | & 等方法，但在算法中的使用頻度并不高，大家下來可以自行復(fù)習(xí)。

HashMap & dict

就如力扣 twoSum 這道題中，題目要求我們在數(shù)組中查找等于 target 的兩個元素，并返回這兩個數(shù)字的下標。如果只是判斷能否找到這兩個數(shù)，我們初始化一個HashSet，在遍歷數(shù)組的過程中檢查target - num 是否在存在HashSet中，如果找到直接返回True，否則將當前數(shù)字保存至HashSet中。

但既然要返回下標，就需要在保存數(shù)字的同時記錄該數(shù)字的下標。使用方式如下圖：

讓我們來看看Python和Java中HashMap 和dict 都有哪些方法吧：

剩余一些通用的d.keys() d.values() d.items()獲取字典所有鍵、值、鍵值對等就不再贅述了，大家下來可以自行復(fù)習(xí)。

關(guān)于HashSet、set和HashMap、dict的相關(guān)知識就復(fù)習(xí)到這里。下來讓我們做第一題熟悉熟悉？嗯...還是換個稍微有點難度的吧。

劍指OfferII032.有效的變位詞

https://leetcode-cn.com/problems/dKk3P7/solution/shua-chuan-jian-zhi-offer-day15-ha-xi-bi-5pqx/

難度：簡單

題目

給定兩個字符串 s 和 t ，編寫一個函數(shù)來判斷它們是不是一組變位詞（字母異位詞）。

注意：若 s 和 t 中每個字符出現(xiàn)的次數(shù)都相同且字符順序不完全相同，則稱 s 和 t 互為變位詞（字母異位詞）。

進階: 如果輸入字符串包含 unicode 字符怎么辦？你能否調(diào)整你的解法來應(yīng)對這種情況？

提示:

• 1 <= s.length, t.length <= 5 * 10 ^ 4
• s and t 僅包含小寫字母

示例

示例 1:
輸入: s = "anagram", t = "nagaram"
輸出: true

示例 2:
輸入: s = "rat", t = "car"
輸出: false

示例 3:
輸入: s = "a", t = "a"
輸出: false

分析

在不看進階的情況下，這道題其實用不到哈希表，因為s和t只包含小寫字母，我們在字符串和數(shù)組那章節(jié)已經(jīng)講過了這種題目的快速解法。
我們通過構(gòu)造一個長度為26的數(shù)組對應(yīng)26個英文字母(嗯...突然想起，譚警官的28個英文字母倒背如流，怕了怕了...)
通過字符串與ascii對應(yīng)的方式完成匹配，這套路用的太多就不細講了。

但是，進階中說了，如果字符串包含unicode字符串怎么辦？
怎么辦，涼拌....直接上哈希表就行了?。?/p>

其他操作和數(shù)據(jù)沒什么區(qū)別，只是換成了哈希表的對應(yīng)方法而已么。

數(shù)組解題

Python:

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t) or s == t:
            return False
        comp = [0] * 26
        for i in s:
            comp[ord(i) - 97] += 1
        for j in t:
            index = ord(j) - 97
            if comp[index] < 1:
                return False
            comp[index] -= 1
        return True

Python:

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length() || s.equals(t)) {
            return false;
        }
        int[] arr = new int[26];
        for (char i:s.toCharArray()) {
            arr[i - 97]++;
        }
        for (char j:t.toCharArray()) {
            arr[j - 97]--;
            if (arr[j - 97] < 0){
                return false;
            }
        }
        return true;
    }
}

哈希表解題

Python:

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return s != t and Counter(s) == Counter(t)

Python:

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length() || s.equals(t)) {
            return false;
        }
        HashMap<Character, Integer> arr = new HashMap<>();
        for (char i : s.toCharArray()) {
            arr.put(i, arr.getOrDefault(i, 0) + 1);
        }
        for (char j : t.toCharArray()) {
            if (!arr.containsKey(j) || arr.get(j) == 0)
                return false;
            arr.put(j, arr.get(j) - 1);
        }
        return true;
    }
}

不得不說Python做這種類型的題目簡直是無腦啊....請恕我偷懶了，哈哈。

經(jīng)過這道簡單題的鋪墊，再來看下面這道中等題，可以說就那會兒事兒....手速題而已！

劍指OfferII033.變位詞組

https://leetcode-cn.com/problems/sfvd7V/solution/shua-chuan-jian-zhi-offer-day15-ha-xi-bi-p57n/

難度：中等

題目

給定一個字符串數(shù)組 strs ，將 變位詞 組合在一起。 可以按任意順序返回結(jié)果列表。

注意：若兩個字符串中每個字符出現(xiàn)的次數(shù)都相同，則稱它們互為變位詞。

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 僅包含小寫字母

示例

示例 1:
輸入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
輸出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
輸入: strs = [""]
輸出: [[""]]

示例 3:
輸入: strs = ["a"]
輸出: [["a"]]

分析

這道題在難度方面并不高，思路其實劍指OfferII032類似的：

1. 我們創(chuàng)建一個哈希表s，key 為String，value 為List
2. 然后循環(huán)列表中的每個字符串，先將字符串排序
3. 再看排序后的字符串是否在哈希表中，如果在則追加，如果不在單獨開辟一對key:value即可
4. 最終將哈希表的value值轉(zhuǎn)化為列表返回即可。

但對于 Python 這里還有一個優(yōu)化點的，如果按照上面的方式，我們需要創(chuàng)建一個哈希表嵌套列表的操作。
而且最終有需要將哈希表的value轉(zhuǎn)化為列表再返回比較麻煩。
我們可以換個思路：

1. 我們單獨創(chuàng)建一個哈希表s和列表li
2. 當哈希表中不存在排序后的字符串時，我們獲取當前列表長度作為value(其實是列表的下標)
3. 然后向哈希表中插入 key = 排序后的字符串, value = 該字符串在列表中的下標。
4. 下次遇到同類型的字符串，我們直接在列表對應(yīng)下標中插入該字符串即可。

解題

Python:

class Solution:
    def groupAnagrams(self, strs):
        ret = []
        d = {}
        for i in strs:
            sort_i = ''.join(sorted(i))
            if sort_i in d:
                ret[d[sort_i]].append(i)
            else:
                d[sort_i] = len(ret)
                ret.append([i])
        return ret

Java:

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            ArrayList<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

好了，今天的哈希表學(xué)習(xí)就到這里，題目雖然基礎(chǔ)，但是一定要練習(xí)啊！

歡迎關(guān)注我的公眾號: 清風(fēng)Python，帶你每日學(xué)習(xí)Python算法刷題的同時，了解更多python小知識。

我的個人博客：https://qingfengpython.cn

力扣解題合集：https://github.com/BreezePython/AlgorithmMarkdown