leetcode刷题 (5.29) 哈希表

1. 快乐数

202

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

「快乐数」 定义为：

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

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

思路：
该题判定条件为结果为1或者无限循环，用哈希表（unordered_set）来判断无限循环。
分为两个函数，一个算平方和，一个判断平方和为1还是无限循环。

笔记：
C++当做unordered_set类型的题来做，Python就看做数据类型是集合就行。

C++：

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;
            }
            // 如果这个sum曾经出现过，说明已经陷入无限循环，return false，否则继续插入哈希表中
            if(set.find(sum) != set.end()){
    
                return false;
            }else{
    
                set.insert(sum);
            }
            n = sum;  // 没到1也没死循环，接着算下一轮平方和
        }
    }
};

Python：

class Solution:
    
    def isHappy(self, n: int) -> bool:
        def calculate_sum(n):
            sum_ = 0
            while n:
                sum_ += (n % 10) ** 2
                n = n // 10
            return sum_

        record = set()

        while True:
            n = calculate_sum(n)
            if n == 1:
                return True
            if n in record:
                return False
            else:
                record.add(n)

2. 两数之和

1

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

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

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

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

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

思路：
C++:
创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，若存在即输出target - x和x对应下标，若不存在将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

Python就当普通字典来做

笔记：
本题呢，则要使用map，那么来看一下使用数组和set来做哈希法的局限。

数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。

set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

此时就要选择另一种数据结构：map ，map是一种key value的存储结构，可以用key保存数值，用value在保存数值所在的下标。

注意（C++）：一开始映射表map是空的，所以第一遍i=0一定找不到对应的target - nums[i]，哪怕真的有也不是第一个i找到的，是后面那个找到的（例如：[2,7,11,15] , target=9，不是i=2时找到的，是i=7时，因为此时2已经被存进map中了）所以 map.insert(pair<int,int>(nums[i], i)) 这句不是只有i没有匹配时才有用，一开始都要插入的。还有这一句一定要放在后面，要先搜索再插入，否则会出现找到自己的情况（例如：[0,0]）

C++：

class Solution {
    
public:
    vector<int> twoSum(vector<int>& nums, int target) {
    
        unordered_map <int,int> map;
        for(int i = 0; i < nums.size(); i++){
    
            auto iter = map.find(target - nums[i]);
            // 迭代器没有迭代到最后，说明前面就找到了
            if(iter != map.end()){
    
            	// iter->first是值，iter->second是index
                return {
    iter->second, i};
            }
            // 这个i没有找到，就把i的信息插入map中
            // 等同于 map[nums[i]]=i
            map.insert(pair<int,int>(nums[i], i));
        }
        return {
    };
    }
};

Python：

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        records = dict()

        for idx, val in enumerate(nums):
            if target - val not in records:
                records[val] = idx
            else: 
                # 如果当前idx的val能在records中找到对应的target - val，
                # 就返回target - val的idx和当前idx
                return [records[target - val], idx]

3. 四数相加II

454

题目：
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

输入：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

思路：
定义一个unordered_map 放（a+b, a+b出现的次数），遍历A,B数组插入map中，再遍历C,D数组，如果0-(c+d)在map中出现过，就统计出现过的次数（value）

笔记：
插入map也可以直接 map[key]++

C++：

class Solution {
    
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    
        unordered_map<int,int> abmap; // key: a+b的值 value: 该值出现的次数
        // 遍历1,2数组
        for(int a : nums1){
    
            for(int b: nums2){
    
                abmap[a + b]++;  // 这句插入map写的很妙
            }
        }

        int count = 0;   // 统计 a+b+c+d=0出现的次数
        // 遍历3,4数组
        for(int c: nums3){
    
            for(int d: nums4){
    
                if(abmap.find(0 - (c + d)) != abmap.end()){
    
                    count += abmap[0 - (c + d)];
                }
            }
        }
        return count;
    }
};

Python：

class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        hashmap = dict()
        for a in nums1:
            for b in nums2:
                if a + b in hashmap:
                    hashmap[a + b] += 1
                else:
                    hashmap[a + b] = 1

        count = 0
        for c in nums3:
            for d in nums4:
                key = 0 - (c + d)
                if key in hashmap:
                    count += hashmap[key]
        return count

4. 赎金信

383

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

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

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

输入：ransomNote = "aa", magazine = "ab"
输出：false

输入：ransomNote = "aa", magazine = "aab"
输出：true

思路：（类似242. 有效字母异位词）
用一个长度为26的数组来记录magazine里字母出现的次数，然后再用ransomNote去验证这个数组是否包含了ransomNote所需要的所有字母

笔记：
C++ 用set，Python用list

C++：

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

Python：

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        record = [0] * 26

        for i in magazine:
            record[ord(i) - ord('a')] += 1

        for i in ransomNote:
            if record[ord(i) - ord('a')] == 0:
                return False
            else:
                record[ord(i) - ord('a')] -= 1
        return True