C++算法题 - 哈希表

383. 赎金信

LeetCode_link

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：
输入：ransomNote = “a”, magazine = “b”
输出：false

示例 2：
输入：ransomNote = “aa”, magazine = “ab”
输出：false

示例 3：
输入：ransomNote = “aa”, magazine = “aab”
输出：true

提示：
1 <= ransomNote.length, magazine.length <= 10^5
ransomNote 和 magazine 由小写英文字母组成

思路：用哈希表

class Solution {
private:
    unordered_map<char, int> hash;
public:
    bool canConstruct(string ransomNote, string magazine) {
        int n = ransomNote.size(), m = magazine.size();
        init_hash(magazine);
        for(int i = 0; i < n; i++){
            if(!delete_hash(ransomNote[i])){
                return false;
            }
        }
        return true;
    }
    void init_hash(string s){
        int n = s.size();
        for(int i = 0; i < n; i++){
            if(hash.find(s[i]) == hash.end()){
                hash[s[i]] = 1;
            }else{
                hash[s[i]] ++;
            }
        }
    }
    bool delete_hash(char c){
        if(hash.find(c) != hash.end()){
            if(hash[c] > 1){
                hash[c] --;
            }else{
                hash.erase(c);
            }
            return true;
        }
        return false;
    }
};

思路：思路差不多，用数组，但是时间快一点，空间节省一点
在这里插入图片描述

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int n = ransomNote.size(), m = magazine.size();
        int find[26] = {0};
        for(int i = 0; i < m; i++){
            int num = magazine[i] - 'a';
            find[num] ++;
        }
        for(int i = 0; i < n ; i++){
            if(!delete_find(find, ransomNote[i])){
                return false;
            }
        }
        return true;
    }
    bool delete_find(int find[], char c){
        int num = c - 'a';
        if(find[num] > 0){
            find[num] --;
            return true;
        }
        return false;
    }
};

205. 同构字符串

LeetCode_link

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:
输入：s = “egg”, t = “add”
输出：true

示例 2：
输入：s = “foo”, t = “bar”
输出：false

示例 3：
输入：s = “paper”, t = “title”
输出：true

提示：
1 <= s.length <= 5 * 10^4
t.length == s.length
s 和 t 由任意有效的 ASCII 字符组成

思路：用哈希表正反映射，因为key是唯一的，但是value不是，所以需要前后两遍。防止"aab"和"aaa"在单向的时候也会映射成功。

class Solution {
private:
    unordered_map<char, char> hash;
public:
    bool isIsomorphic(string s, string t) {
        int n = s.size();
        for(int i = 0; i < n; i++){
            if(hash.find(s[i]) == hash.end()){
                hash[s[i]] = t[i];
            }else{
                if(hash[s[i]] != t[i]){
                    return false;
                }
            }
        }
        hash.clear();
        for(int i = 0; i < n; i++){
            if(hash.find(t[i]) == hash.end()){
                hash[t[i]] = s[i];
            }else{
                if(hash[t[i]] != s[i]){
                    return false;
                }
            }
        }
        return true;
    }
};

290. 单词规律

LeetCode_link

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的遵循指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例1:
输入: pattern = “abba”, s = “dog cat cat dog”
输出: true

示例 2:
输入:pattern = “abba”, s = “dog cat cat fish”
输出: false

示例 3:
输入: pattern = “aaaa”, s = “dog cat cat dog”
输出: false

提示:
1 <= pattern.length <= 300
pattern 只包含小写英文字母
1 <= s.length <= 3000
s 只包含小写英文字母和 ' '
s 不包含 任何前导或尾随对空格
s 中每个单词都被 单个空格 分隔

思路：和上题一样，只不过不能使用同一个哈希表了，因为两侧的数据类型不一样

class Solution {
private:
    unordered_map<char, string> hash_cs;
    unordered_map<string, char> hash_sc;
public:
    bool wordPattern(string pattern, string s) {
        int n = pattern.size(), m = s.size();
        int i = 0;
        int words = 0;
        int start = 0;
        while(i < m && words < n){
            while(s[i] != ' ' && i < m)  i++;
            string cut = s.substr(start, i - start);
            if(hash_cs.find(pattern[words]) == hash_cs.end()){
                hash_cs[pattern[words]] = cut;
            }else{
                if(hash_cs[pattern[words]] != cut){
                    return false;
                }
            }
            if(hash_sc.find(cut) == hash_sc.end()){
                hash_sc[cut] = pattern[words];
            }else{
                if(hash_sc[cut] != pattern[words]){
                    return false;
                }
            }
            words ++;
            i ++;
            start = i;
        }
        if(i < m || words < n)  return false;
        return true;

    }
};

242. 有效的字母异位词

LeetCode_link

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true

示例 2:
输入: s = “rat”, t = “car”
输出: false

提示:
1 <= s.length, t.length <= 5 * 10^4
s 和 t 仅包含小写字母

思路：哈希表统计一个字符串中字符出现的次数，然后再用这个哈希表检查另一个字符串

class Solution {
private:
    unordered_map<char, int> hash;
public:
    bool isAnagram(string s, string t) {
        int n = s.size(), m = t.size();
        if(n != m)  return false;
        init_hash(s);
        for(int i = 0; i < m; i++){
            if(!delete_hash(t[i])){
                return false;
            }
        }
        return true;
    }
    void init_hash(string s){
        int n = s.size();
        for(int i = 0; i < n; i++){
            if(hash.find(s[i]) == hash.end()){
                hash[s[i]] = 1;
            }else{
                hash[s[i]] ++;
            }
        }
    }
    bool delete_hash(char c){
        if(hash.find(c) == hash.end()){
            return false;
        }else{
            if(hash[c] > 1){
                hash[c] --;
            }else{
                hash.erase(c);
            }
        }
        return true;
    }
};

49. 字母异位词分组

LeetCode_link

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

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

示例 2:
输入: strs = [“”]
输出: [[“”]]

示例 3:
输入: strs = [“a”]
输出: [[“a”]]

提示：
1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

思路：思路打开，哈希表的value位置可以放容器，用key存放排序后的string，这样，相同的排序后的字符串被放在了一起。

class Solution {
private:
    unordered_map<string, vector<string>> hash;
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> rec;
        int n =strs.size();
        for(int i = 0; i < n; i++){
            string sort_s = strs[i];
            sort(sort_s.begin(), sort_s.end());
            hash[sort_s].push_back(strs[i]);
        }
        for(auto it = hash.begin(); it != hash.end(); it++){
            rec.push_back(it -> second);
        }
        return rec;
    }
};

1. 两数之和

LeetCode_link

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]

提示：
2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
只会存在一个有效答案

思路：边找边建哈希表，值作为key，下标作为value。面对有相同值的情况，因为题目中说明只会有唯一解，所以相同值的情况只存在于这俩个相同值同时是答案，因此，当遍历到相同值中的第二个时，就已经可以得到答案。

class Solution {
private:
    unordered_map<int, int> hash;
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for(int i = 0; i < n; i++){
            if(hash.find(target - nums[i]) != hash.end()){
                return {i, hash[target - nums[i]]};
            }else{
                hash[nums[i]] = i;
            }
        }
        return {};
    }
};

202. 快乐数

LeetCode_link

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 true ；不是，则返回 false 。

示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：
输入：n = 2
输出：false

提示：
1 <= n <= 231 - 1

思路：只要历史数字不是1就记录下来，因为是1就是结果了，如果不是1而且还在历史记录中，那就不是快乐数。

class Solution {
private:
    unordered_set<int> hash;
public:
    bool isHappy(int n) {
        int next_num = n;
        int sum = 0;
        while(sum != 1){
            sum = compute_sum(next_num);
            if(hash.find(sum) == hash.end()){
                hash.insert(sum);
            }else{
                return false;
            }
            next_num = sum;
        }
        return true;
    }
    int compute_sum(int num){
        int sum = 0;
        while(num / 10 > 0){
            sum += (num % 10) * (num % 10);
            num /= 10;
        }
        sum += num * num;
        return sum;
    }
};

219. 存在重复元素Ⅱ

LeetCode_link

给你一个整数数组 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 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^5

思路：和两数之和思路差不多

class Solution {
private:
    unordered_map<int, int> hash;
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        int n = nums.size();
        for(int i = 0; i < n; i++){
            if(hash.find(nums[i]) != hash.end() && i - hash[nums[i]] <= k){
                return true;
            }else{
                hash[nums[i]] = i;
            }
        }
        return false;
    }
};

128. 最长连续序列

LeetCode_link

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

提示：
0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

思路：

class Solution {
private:
    unordered_map<int, int> hash;
public:
    int longestConsecutive(vector<int>& nums) {
        init_hash(nums);
        int l = 0;
        for(auto it = hash.begin(); it != hash.end(); it++){
            if(it->second == 1) continue;
            int lo = 1;
            int left = it->first - 1;
            int right = it->first + 1;
            it->second = 1;
            while(hash.find(left) != hash.end()){
                hash[left] = 1;
                lo ++;
                left --;
            }
            while(hash.find(right) != hash.end()){
                hash[right] = 1;
                lo ++;
                right ++;
            }
            l = max(l, lo);
        }
        return l;
    }
    void init_hash(vector<int> nums){
        int n = nums.size();
        for(int& i : nums){
            if(hash.find(i) == hash.end()){
                hash[i] = 0;
            }
        }
    }
};