LeetCode-题目详解（八）：哈希表【Python：dict = {}】【C++：unordered_map＜int, int＞ map】

心已赠人 2023-10-04 13:30 5阅读 0赞

#### 这里写目录标题 ####

*   *  剑指 Offer 50. 第一个只出现一次的字符
     *  49. 字母异位词分组
     *  169. 多数元素【剑指 Offer 39. 数组中出现次数超过一半的数字】
     *  217. 存在重复元素
     *  219. 存在重复元素 II
     *  409. 最长回文串
     *  560. 和为K的子数组
     *  面试题 01.01. 判定字符是否唯一
     *  面试题 01.02. 判定是否互为字符重排
     *  面试题 01.04. 回文排列

### 剑指 Offer 50. 第一个只出现一次的字符 ###

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例 1:

输入：s = "abaccdeff"
    输出：'b'

示例 2:

输入：s = "" 
    输出：' '

限制：

*  0 <= s 的长度 <= 50000

--------------------

class Solution {
        
    public:
        char firstUniqChar(string s) {
        
            unordered_map<char, int> map;
            for(char c : s){
        
                map[c]++;
            }
    
            for(char c : s){
        
                if(map[c] == 1){
        
                    return c;
                }
            }
            return ' ';
        }
    };

class Solution:
        def firstUniqChar(self, s: str) -> str:
            dict = {
        }
            for c in s:
                dict[c] = dict.get(c, 0) + 1
            
            for c in s:
                if dict[c] == 1:
                    return c
            return " "

### 49. 字母异位词分组 ###

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
    输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
    输出: [[""]]

示例 3:

输入: strs = ["a"]
    输出: [["a"]]

提示：

*  1 <= strs.length <=  1 0 4 10^4 104
 *  0 <= strs\[i\].length <= 100
 *  strs\[i\] 仅包含小写字母

--------------------

class Solution:
        def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
            dict = {
        }
            result = []
    
            for s in strs:
                key = ''.join(sorted(s))
                if dict.get(key) != None:
                    dict[key].append(s)
                else:
                    dict[key] = [s]
    
            for value in dict.values():
                result.append(value)
    
            return result

class Solution {
        
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) {
        
            unordered_map<string, vector<string>> mp;
            for(string& str : strs){
        
                string key = str;
                sort(key.begin(), key.end());
                mp[key].push_back(str);
            }
    
            vector<vector<string>> result;
            for(auto it = mp.begin(); it != mp.end(); it++){
        
                result.push_back(it->second);
            }
            return result;
        }
    };

class Solution {
        
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) {
        
            unordered_map<string, vector<string>> mp;
            for(string str : strs){
        
                string key = str;
                sort(key.begin(), key.end());
                mp[key].push_back(str);
            }
    
            vector<vector<string>> result;
            for(auto it = mp.begin(); it != mp.end(); it++){
        
                result.push_back(it->second);
            }
            return result;
        }
    };

class Solution {
        
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) {
        
            unordered_map<string, vector<string>> mp;
            for(auto str : strs){
        
                auto key = str;
                sort(key.begin(), key.end());
                mp[key].push_back(str);
            }
    
            vector<vector<string>> result;
            for(auto it = mp.begin(); it != mp.end(); it++){
        
                result.push_back(it->second);
            }
            return result;
        }
    };

### 169. 多数元素【剑指 Offer 39. 数组中出现次数超过一半的数字】 ###

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
    输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
    输出：2

提示：

*  n == nums.length
 *   1 < = n < = 5 ∗ 1 0 4 1 <= n <= 5 \* 10^4 1<=n<=5∗104
 *   − 1 0 9 < = n u m s \[ i \] < = 1 0 9 -10^9 <= nums\[i\] <= 10^9 −109<=nums\[i\]<=109

--------------------

**思路**

我们知道出现次数最多的元素大于  ⌊ n 2 ⌋ \\lfloor \\dfrac\{n\}\{2\} \\rfloor ⌊2n⌋ 次，所以可以用哈希表来快速统计每个元素出现的次数。

**算法**

我们使用哈希映射（HashMap）来存储每个元素以及出现的次数。对于哈希映射中的每个键值对，键表示一个元素，值表示该元素出现的次数。

我们用一个循环遍历数组 nums 并将数组中的每个元素加入哈希映射中。在这之后，我们遍历哈希映射中的所有键值对，返回值最大的键。我们同样也可以在遍历数组 nums 时候使用打擂台的方法，维护最大的值，这样省去了最后对哈希映射的遍历。

class Solution {
        
    public:
        int majorityElement(vector<int>& nums) {
        
            unordered_map<int, int> count;
            int majority = 0;
            int cnt = 0;
    
            for(int num : nums){
        
                count[num]++;
                if(count[num] > cnt){
        
                    majority = num;
                    cnt = count[num];
                }
            }
    
            return majority;
        }
    };

class Solution:
        def majorityElement(self, nums: List[int]) -> int:
            count = {
        }
            majority = 0
            cnt = 0
    
            for i in range(len(nums)):
                num = nums[i]
                count[num]  = count.get(num, 0) + 1
                if count[num] > cnt:
                    majority = num
                    cnt = count[num]
    
            return majority

### 217. 存在重复元素 ###

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]
    输出：true

示例 2：

输入：nums = [1,2,3,4]
    输出：false

示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]
    输出：true

提示：

*   1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
 *  \- 1 0 9 < = n u m s \[ i \] < = 1 0 9 10^9 <= nums\[i\] <= 10^9 109<=nums\[i\]<=109

--------------------

class Solution:
        def containsDuplicate(self, nums: List[int]) -> bool:
            dict = {
        }
            for num in nums:
                if dict.get(num) is not None:
                    return True
                dict[num] = 1
            return False

class Solution {
        
    public:
        bool containsDuplicate(vector<int>& nums) {
        
            unordered_map<int, int> map;
            for(int num : nums){
        
                if(map[num] == 1){
        
                    return true;
                }
                map[num] = 1;
            }
            return false;
        }
    };

### 219. 存在重复元素 II ###

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums\[i\] == nums\[j\] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,1], k = 3
    输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1
    输出：true

示例 3：

输入：nums = [1,2,3,1,2,3], k = 2
    输出：false

提示：

*   1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
 *   − 1 0 9 < = n u m s \[ i \] < = 1 0 9 -10^9 <= nums\[i\] <= 10^9 −109<=nums\[i\]<=109
 *   0 < = k < = 1 0 5 0 <= k <= 10^5 0<=k<=105

--------------------

class Solution:
        def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
            dict = {
        }
            for idx, val in enumerate(nums):
                if dict.get(val) is not None and abs(dict.get(val) - idx) <= k:
                    return True
                dict[val] = idx
            return False

class Solution {
        
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) {
        
            unordered_map<int, int> map;
            for(int i = 0; i < nums.size(); i++){
        
                if(map.count(nums[i]) && i - map[nums[i]] <= k){
        
                    return true;
                }
                map[nums[i]] = i;
            }
            return false;
        }
    };

### 409. 最长回文串 ###

给定一个包含大写字母和小写字母的字符串 s ，返回 通过这些字母构造成的 最长的回文串 。

在构造过程中，请注意 区分大小写 。比如 “Aa” 不能当做一个回文字符串。

示例 1:

输入:s = "abccccdd"
    输出:7
    解释:
    我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。

示例 2:

输入:s = "a"
    输入:1

示例 3：

输入:s = "aaaaaccc"
    输入:7

提示:

*  1 <= s.length <= 2000
 *  s 只由小写 和/或 大写英文字母组成

--------------------

class Solution:
        def longestPalindrome(self, s: str) -> int:
            dict = {
        }
            for c in s:
                dict[c] = dict.get(c, 0) + 1
    
            result = 0
            for value in dict.values():
                if value % 2 == 1:
                    value -= 1
                result += value
    
            if len(s) == result:
                return result
            else:
                return result + 1

class Solution {
        
    public:
        int longestPalindrome(string s) {
        
            int result = 0;
            unordered_map<char, int> map;
            for(char c : s){
        
                map[c]++;
            }
    
            for(auto item : map){
        
                int value = item.second;
                if(value % 2 == 1){
        
                    value -= 1;
                }
                result += value;
            }
    
            if(s.size() == result){
        
                return result;
            }else{
        
                return result + 1;
            }
    
        }
    };

### 560. 和为K的子数组 ###

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2
    输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

*  数组的长度为 \[1, 20,000\]。
 *  数组中元素的范围是 \[-1000, 1000\] ，且整数 k 的范围是 \[-1e7, 1e7\]。

--------------------

具体算法：

*  维护一个 hashmap，hashmap 的 key 为累加值 acc，value 为累加值 acc 出现的次数。
 *  迭代数组，然后不断更新 acc 和 hashmap，如果 acc 等于 k，那么很明显应该+1. 如果 hashmap\[acc - k\] 存在，我们就把它加到结果中去即可。

画了一个图来演示 nums = \[1,2,3,3,0,3,4,2\], k = 6 的情况。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70]  
如图，当访问到 nums\[3\]的时候，hashmap 如图所示，这个时候 count 为 2.  
其中之一是\[1,2,3\],这个好理解。还有一个是\[3,3\].

这个\[3,3\]正是我们通过 hashmap\[acc - k\]即 hashmap\[9 - 6\]得到的。

class Solution:
        def subarraySum(self, nums: List[int], k: int) -> int:
            '''
                前缀和；
                    一次遍历；
                    字典存储前缀和的值；
                    当前前缀和减去K，则为之前的前缀和，查看是否字典存在；
                    如果有则结果加1.
            '''
    
            # dict 存储某“前缀和”出现的次数
            # 如果某前缀不在此字典中，那么它对应的次数为0
            
            dict = {
        0: 1}  # 先给定一个初始值，代表前缀和为0的出现了一次
            total = 0  # 记录到当前位置的前缀和
            result = 0
    
            for i in range(len(nums)):
                total += nums[i]  # 计算当前和【从索引0到索引i的所有元素的和】
                
                if total - k in dict:  # 如果前缀和减去目标值k所得到的值在字典中出现，即当前位置前缀和减去之前某一位的前缀和等于目标值
                    result += dict[total - k]
                
                dict[total] = dict.get(total, 0) + 1
            
            return result

### 面试题 01.01. 判定字符是否唯一 ###

实现一个算法，确定一个字符串 s 的所有字符是否全都不同。

示例 1：

输入: s = "leetcode"
    输出: false

示例 2：

输入: s = "abc"
    输出: true

限制：

*  0 <= len(s) <= 100
 *  s\[i\]仅包含小写字母
 *  如果你不使用额外的数据结构，会很加分。

--------------------

class Solution {
        
    public:
        bool isUnique(string astr) {
        
            unordered_map<char, int> map;
            for(auto c : astr){
        
                if(map.find(c) != map.end()){
        
                    return false;
                }
                map[c] = 1;
            }
            return true;
        }
    };

class Solution:
        def isUnique(self, astr: str) -> bool:
            dict = {
        }
            for c in astr:
                if dict.get(c) is not None:
                    return False
                dict[c] = 1
            
            return True

### 面试题 01.02. 判定是否互为字符重排 ###

给定两个由小写字母组成的字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

示例 1：

输入: s1 = "abc", s2 = "bca"
    输出: true

示例 2：

输入: s1 = "abc", s2 = "bad"
    输出: false

说明：

*  0 <= len(s1) <= 100
 *  0 <= len(s2) <= 100

--------------------

**方法一：排序**

class Solution {
        
    public:
        bool CheckPermutation(string s1, string s2) {
        
            sort(s1.begin(), s1.end());
            sort(s2.begin(), s2.end());   
            return s1 == s2;   
        }
    };

class Solution:
        def CheckPermutation(self, s1: str, s2: str) -> bool:
            s1 = list(s1)
            s2 = list(s2)
            s1.sort()
            s2.sort()
    
            return s1 == s2

**方法二：哈希表**  
![在这里插入图片描述][e6d55d64444c4488a7366bcceaa46cdb.gif_pic_center]

class Solution {
        
    public:
        bool CheckPermutation(string s1, string s2) {
        
            unordered_map<char, int> map;
            for(char c : s1){
        
                map[c]++;
            }
            for(char c : s2){
        
                map[c]--;
            }
            for(auto kv : map){
        
                if(kv.second != 0){
        
                    return false;
                }
            }
            return true;
        }
    };

class Solution {
        
    public:
        bool CheckPermutation(string s1, string s2) {
        
            unordered_map<char, int> map;
            for(char c : s1){
        
                map[c]++;
            }
            for(char c : s2){
        
                map[c]--;
            }
            for(pair<char, int> kv : map){
        
                if(kv.second != 0){
        
                    return false;
                }
            }
            return true;
        }
    };

### 面试题 01.04. 回文排列 ###

给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。

回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。

回文串不一定是字典当中的单词。

示例1：

输入："tactcoa"
    输出：true（排列有"tacocat"、"atcocta"，等等）

--------------------

class Solution {
        
    public:
        bool canPermutePalindrome(string s) {
        
            int count = 0;
            unordered_map<char, int> map;
            for(char c : s){
        
                map[c]++;
            }
            for(auto kv : map){
        
                if(kv.second % 2 == 1){
        
                    count++;
                }
            }
    
            if(count > 1){
        
                return false;
            }else{
        
                return true;
            }
        }
    };

class Solution:
        def canPermutePalindrome(self, s: str) -> bool:
            dict = {
        }
    
            for c in s:
                dict[c] = dict.get(c, 0) + 1
            
            count = 0
            for val in dict.values():
                if val % 2 == 1:
                    count += 1
            
            if count > 1:
                return False
            else:
                return True

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210623153451919.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70
[e6d55d64444c4488a7366bcceaa46cdb.gif_pic_center]: https://img-blog.csdnimg.cn/e6d55d64444c4488a7366bcceaa46cdb.gif#pic_center