当前位置 : 主页 > 编程语言 > java >

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

来源:互联网 收集:自由互联 发布时间:2023-09-03
前言 欢迎来到小K的Leetcode|代码随想录|专题化专栏,今天将为大家带来哈希法~快乐数 | 四数相加 II | 赎金信的分享✨ 目录 前言 202. 快乐数 454. 四数相加 II 383. 赎金信 总结 202. 快乐数


前言

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


目录

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



202. 快乐数

✨题目链接点这里编写一个算法来判断一个数 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;
        }
    }
};

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

454. 四数相加 II

✨题目链接点这里给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足:0 <= i, j, k, l < nnums1[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;
    }
};

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

383. 赎金信

✨题目链接点这里给你两个字符串:ransomNotemagazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以,返回 true ;否则返回 falsemagazine 中的每个字符只能在 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
ransomNotemagazine 由小写英文字母组成

「方法一」:暴力法,直接两层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;
    }
};

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

「方法二」:哈希法,我的第一想法是用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;
    }
};

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

「方法三」:因为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;
    }
};

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

总结

哈希表有三种结构,数组,setmap,要根据情况适当选择~


网友评论