【代码随想录 | Leetcode | 第九天】哈希表 | 快乐数 | 四数相加 II | 赎金信

你的名字 2023-10-13 20:58 28阅读 0赞

## 前言 ##

**欢迎来到[小K][K]的[Leetcode|代码随想录|专题化][Leetcode]专栏，今天将为大家带来哈希法~快乐数 | 四数相加 II | 赎金信的分享**✨

#### 目录 ####

*  前言
 *  202. 快乐数
 *  454. 四数相加 II
 *  383. 赎金信
 *  总结

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

## 202. 快乐数 ##

✨[题目链接点这里][Link 1]  
**编写一个算法来判断一个数 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，也就是说当`sum`重复出现，这个数决定不是快乐数~而要快速判断一个数是否出现在集合中时，我们自然会想到哈希法！**

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

![在这里插入图片描述][669f46fdc7b342549c4eb17b370fbfe1.png]

## 454. 四数相加 II ##

✨[题目链接点这里][Link 2]  
**给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：`0 <= i, j, k, l < n`  
`nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0`**

示例 1：

**输入**：nums1 = \[1,2\], nums2 = \[-2,-1\], nums3 = \[-1,2\], nums4 = \[0,2\]  
**输出**：2

> **解释**：
> 
> > 两个元组如下：
> > 
> > 1.  (0, 0, 0, 1) -> nums1\[0\] + nums2\[0\] + nums3\[0\] + nums4\[1\] = 1 + (-2) + (-1) + 2 = 0
> > 2.  (1, 1, 0, 0) -> nums1\[1\] + nums2\[1\] + nums3\[0\] + nums4\[0\] = 2 + (-1) + (-1) + 0 = 0

示例 2：

**输入**：`nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]`  
**输出**：1

提示:

n == nums1.length
    n == nums2.length
    n == nums3.length
    n == nums4.length
    1 <= n <= 200
    -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

> **「思路如下」：**
> 
> > **首先定义 一个unordered\_map，key放a和b两数之和，value 放a和b两数之和出现的次数。**  
> > 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。  
> > **定义int变量count，用来统计 a+b+c+d = 0 出现的次数。**  
> > 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。  
> > **最后返回统计值 count 就可以了**

class Solution {
        
    public:
        int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        
            //key存放nums1和nums2中值的和，value则记录该值出现的次数
            unordered_map<int,int> umap;
            //遍历nums1和nums2数值，记录他们的和出现的次数，并放入map中
            for (auto a : nums1) {
        
                for (auto b : nums2) {
        
                    umap[a+b]++;
                }
            }
            int count = 0; //记录四数之和等于零
            //遍历nums3和nums4数组，如果他们的和等于map中任意一值的相反数，则用count记录该和出现的次数
            //也就是四数之和等于零的次数
            for (auto c : nums3) {
        
                for (auto d : nums4) {
        
                    if (umap.find(- (c + d)) != umap.end()) {
        
                        count += umap[- (c + d)];
                    }
                }
            }
            return count;
        }
    };

![在这里插入图片描述][3fc99d76bd6948e6bee39e7e127fe80b.png]

## 383. 赎金信 ##

✨[题目链接点这里][Link 3]  
**给你两个字符串：`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` <= 105  
**`ransomNote` 和 `magazine`由小写英文字母组成**

**「方法一」：暴力法，直接两层`for`循环，如果magazine中有ransomNote的元素，那么就从ransomNote中删除，最后看ransomNote的大小是否为零**

class Solution {
        
    public:
        bool canConstruct(string ransomNote, string magazine) {
        
            for (int i = 0; i < magazine.size(); i++) {
        
                for (int j = 0; j < ransomNote.size(); j++) {
        
                    if (magazine[i] == ransomNote[j]) {
        
                        ransomNote.erase(ransomNote.begin() + j);
                        break;
                    }
                }
            }
            if (ransomNote.size() == 0) return true;
            return false;
        }
    };

![在这里插入图片描述][f60a1a949ee54c2ead21750917afb80b.png]

**「方法二」：哈希法，我的第一想法是用map，map思路，把字母当key，用value记录出现次数，先把ransomNote放入map中，然后用该map查找magazine中的元素，找到一个减掉一个，最后看map中的value是否都小于等于零。**

class Solution {
        
    public:
        bool canConstruct(string ransomNote, string magazine) {
        
            if (magazine.size() < ransomNote.size()) return false;
            unordered_map<char,int> umap;
            for (int i = 0; i < ransomNote.size() ; i++) umap[ransomNote[i]]++;
            for (int i = 0; i < magazine.size(); i++) umap[magazine[i]]--;
            for (int i = 0; i < ransomNote.size() ; i++) {
        
                if (umap[ransomNote[i]] > 0)
                return false;
            }
            return true;
        }
    };

![在这里插入图片描述][f3a0c8c577014b22a7a2f0091f597e9f.png]

**「方法三」：因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！所以这里用数组作为哈希表比map要快！！！**

class Solution {
        
    public:
        bool canConstruct(string ransomNote, string magazine) {
        
            if (ransomNote.size() > magazine.size()) return false;
            int record[26] = {
        0};
            for (int i = 0; i < ransomNote.size(); i++) record[ransomNote[i] - 'a']++;
            for (int i = 0; i < magazine.size(); i++) record[magazine[i] - 'a']--;
            for (int i = 0; i < 26; i++) {
        
                if (record[i] > 0) {
        
                    return false;
                }
            }
            return true;
        }
    };

![在这里插入图片描述][e65aaae01fd94fddb038a3ef84d015c5.png]

## 总结 ##

**哈希表有三种结构，数组，`set`，`map`，要根据情况适当选择~**

[K]: https://blog.csdn.net/qq_72157449?spm=1000.2115.3001.5343
[Leetcode]: https://blog.csdn.net/qq_72157449/category_12293229.html?spm=1001.2014.3001.5482
[Link 1]: https://leetcode.cn/problems/happy-number/
[669f46fdc7b342549c4eb17b370fbfe1.png]: https://img-blog.csdnimg.cn/669f46fdc7b342549c4eb17b370fbfe1.png
[Link 2]: https://leetcode.cn/problems/4sum-ii/
[3fc99d76bd6948e6bee39e7e127fe80b.png]: https://img-blog.csdnimg.cn/3fc99d76bd6948e6bee39e7e127fe80b.png
[Link 3]: https://leetcode.cn/problems/ransom-note/description/
[f60a1a949ee54c2ead21750917afb80b.png]: https://img-blog.csdnimg.cn/f60a1a949ee54c2ead21750917afb80b.png
[f3a0c8c577014b22a7a2f0091f597e9f.png]: https://img-blog.csdnimg.cn/f3a0c8c577014b22a7a2f0091f597e9f.png
[e65aaae01fd94fddb038a3ef84d015c5.png]: https://img-blog.csdnimg.cn/e65aaae01fd94fddb038a3ef84d015c5.png