• 代码随想录-哈希表|ACM模式

    目录

    前言：

    （1）基本概念

    （2）常见的三种哈希结构

    242.有效字母的异位词

    题目描述：

    输入输出描述：

    思路和想法:

    349. 两个数组的交集

    题目描述：

    输入输出描述：

    思路和想法：

    202. 快乐数

    题目描述：

    输入输出描述：

    思路和想法：

    1. 两数之和

    题目描述：

    输入输出描述：

    思路和想法：

    454. 四数相加 II

    题目描述：

    输入输出描述：

    思路和想法：

    383. 赎金信

    题目描述：

    输入输出描述：

    思路和想法

    前言：

    （1）基本概念

    就是用哈希函数构建索引和内容之间的映射。就相当于一个内容就会有相对应的哈希函数值（即索引下标），直接找下标，就能查询是否有相应的内容。

    在这个过程中，可能会遇到两个同时映射到一个，这个就是哈希碰撞的现象，应对这个方法常见的有两种，其中一个是拉链法（即采用链表的方式），另一个就是线性探测法。

    ①拉链法需要选择适当的哈希表的大小----不会因为数组空值而浪费大量内存，另一个不会链表太长而在查找上浪费太多时间。

    ②线性探测法，一定要保证tablesize大于datasize。依靠哈希表空位来解决碰撞问题。

    （2）常见的三种哈希结构

    数组、set（集合）以及map（映射）

    242.有效字母的异位词

    题目描述：

    给定两个字符串 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 * 104
    • s 和 t 仅包含小写字母

    思路和想法:

    这个问题可以分为三个步骤来解决。

    • 步骤一：构建Hash table-数组，之后遍历第一个字符串将里面的元素一一对应到哈希表上记录频次。
    • 步骤二：再遍历第二个字符串，将相应位置--。
    • 步骤三：最终只需判断哈希表内元素是否都为零，就可以判断这两个字符串是否互为有效字母异位词。
    1. #include 
    2. using namespace std;
    3. bool isAnagram(string s, string t) {
    4.     //将a-z，26个字母到0-25
    5.     //哈希表
    6.     unordered_map<int, int> m;
    7.     for(int i = 0; i < s.size(); i++ ){
    8.         m[s[i]-'a']++;
    9.     }
    10.     for(int i = 0; i < t.size(); i++){
    11.         m[t[i]-'a']--;
    12.     }
    13.     for(int i = 0; i < 26;i++){
    14.         if(m[i] != 0) return false;
    15.     }
    16.     return true;
    17. }
    18. int main() {
    19.     string s,t;
    20.     getline(cin,s);
    21.     getline(cin,t);
    22.  
    23.     bool result;
    24.     result = isAnagram(s,t);
    25.  
    26.     if(result == 1){
    27.         cout << "true";
    28.     }else{
    29.         cout << "false";
    30.     }
    31.     return 0;
    32. }
    33. /************
    34. 示例1:
    35. anagram
    36. nagaram
    37. 示例2:
    38. rat
    39. car
    40. *************/

    349. 两个数组的交集

    题目描述：

    给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

    输入输出描述：

    示例 1：

    输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2]

    示例 2：

    输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 解释：[4,9] 也是可通过的

    提示：

    • 1 <= nums1.length, nums2.length <= 1000
    • 0 <= nums1[i], nums2[i] <= 1000

    思路和想法：

    可以清晰的知道我们要判断元素在集合中是否出现过。这里数值较大，适合采用set的方式，并且非重复，考虑时间复杂度和空间复杂度，采用unordered_set。

    将第一个数组进行处理转换成set，再用numbers2遍历查询是否出现过，放在result集合里。

    1. #include 
    2. using namespace std;
    3.  
    4. vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    5.     unordered_set <int> result;
    6.     unordered_set <int> nums_set(nums1.begin(), nums1.end());    //将数组1转换成哈希表
    7.  
    8.     for(int i = 0; i < nums2.size(); i++){
    9.         if(nums_set.find(nums2[i]) != nums_set.end()){
    10.             result.insert(nums2[i]);                            //set插入元素操作
    11.         }
    12.     }
    13.     return vector <int> (result.begin(), result.end());
    14.  
    15. }
    16.  
    17. int main() {
    18.     vector<int> nums1,nums2;
    19.     int num;
    20.     //nums1
    21.     while(cin >> num) {
    22.         nums1.push_back(num);
    23.         // 读到换行符，终止循环
    24.         if(getchar() == '\n') {
    25.             break;
    26.         }
    27.     }
    28.     //nums2
    29.     while(cin >> num) {
    30.         nums2.push_back(num);
    31.         // 读到换行符，终止循环
    32.         if(getchar() == '\n') {
    33.             break;
    34.         }
    35.     }
    36.  
    37.     vector<int> result;
    38.     result = intersection(nums1,nums2);
    39.  
    40.     for(int i = 0; i < result.size(); i++) {
    41.         cout << result[i] << " ";
    42.     }
    43.     cout << endl;
    44.     return 0;
    45. }
    46. /*************
    47. 示例1:
    48. 1 2 2 1
    49. 2 2
    50. 示例2:
    51. 4 9 5
    52. 9 4 9 8 4
    53.  ************/

    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 <= 2^31 - 1

    思路和想法：

    这里比较重要的地方，在于判断什么时候出现无限循环，即判断平方和数值重复出现。这里就是判断元素有无重复出现，就可以set来解决了。解决这道题目具体的步骤如下：

    步骤一：计算数n的各个位置的平方和

    步骤二：判断是否出现了1，并进行循环，如果在这个过程中，在set集合中找到元素，则证明出现循环，return false。

    1. #include 
    2. using namespace std;
    3.  
    4. int Sum(int n){
    5.     int sum = 0;
    6.     while(n){
    7.         sum += (n % 10) * (n % 10);
    8.         n /= 10;
    9.     }
    10.     return sum;
    11. }
    12.  
    13. bool isHappy(int n) {
    14.     unordered_set<int> set;
    15.     while(1){
    16.         int sum1 = Sum(n);
    17.         if(sum1 == 1){
    18.             return true;
    19.         }
    20.         if (set.find(sum1) != set.end()) {
    21.             return false;
    22.         } else {
    23.             set.insert(sum1);
    24.         }
    25.         n = sum1;
    26.     }
    27. }
    28.  
    29. int main() {
    30.     int number;
    31.     cin >> number;
    32.  
    33.     bool result;
    34.     result = isHappy(number);
    35.  
    36.     if(result == 1){
    37.         cout << "true" <
    38.     }else{
    39.         cout << "false" <
    40.     }
    41.  
    42.     return 0;
    43. }
    44. /*************
    45. 示例1:
    46. 19
    47. true
    48. 示例2:
    49. 2
    50. false
    51.  ************/

    1. 两数之和

    题目描述：

    给定一个整数数组 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 <= 104
    • -109 <= nums[i] <= 109
    • -109 <= target <= 109
    • 只会存在一个有效答案

    思路和想法：

    在判断元素有无的同时，也要存储下标，所以这里我们采用unorderded_map。其中map结构--key（元素），value（下标）。

    1. #include 
    2. using namespace std;
    3.  
    4. vector<int> twoSum(vector<int>& nums, int target) {
    5.     unordered_map <int,int> map;
    6.     for(int i = 0; i < nums.size(); i++) {
    7.         // 遍历当前元素，并在map中寻找是否有匹配的key
    8.         auto iterm = map.find(target - nums[i]);
    9.         if(iterm != map.end()) {
    10.             return {iterm->second, i};
    11.         }
    12.         // 如果没找到匹配对，就把访问过的元素和下标加入到map中
    13.         map.insert(pair<int, int>(nums[i], i));
    14.     }
    15.     return {};
    16. }
    17.  
    18. int main() {
    19.     vector<int> nums;
    20.     int num;
    21.     while(cin >> num){
    22.         nums.push_back(num);
    23.         if(getchar() == '\n'){
    24.             break;
    25.         }
    26.     }
    27.  
    28.     int target;
    29.     cin >> target;
    30.     vector<int> result;
    31.     result = twoSum(nums,target);
    32.  
    33.     for (int i = 0; i < result.size(); ++i) {
    34.         cout << result[i] << " ";
    35.     }
    36.     cout << endl;
    37.     return 0;
    38. }
    39. /*************
    40. 示例1:
    41. 2 7 11 15
    42. 9
    43. 示例2:
    44. 3 2 4
    45. 6
    46. 示例3：
    47. 3 3
    48. 6
    49.  ************/

    454. 四数相加 II

    题目描述：

    给你四个整数数组 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
    • -2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

    思路和想法：

    将四个数组简化成两个数组，并将其中一个放入map中，key放两两数组加和值，value放数组下标。

    步骤一：先构建一个哈希表（nums1），存储key以及value，key对应数组之和，value记录次数。

    步骤二：nums3 + nums4，进行map查询，寻找里面是否有其相反数的映射。

    1. #include <bits/stdc++.h>
    2. using namespace std;
    3.  
    4. int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    5.     std::unordered_map<int, int> h1;
    6.     //步骤一，构建哈希表，存储key以及value
    7.     int size = nums1.size();
    8.     int sum = 0;                //key---数组两两加和值
    9.     int Ycount = 0;             //记录多少个元组满足
    10.     for(int i = 0; i < size; i++){
    11.         for(int j = 0; j < size; j++){
    12.             sum = nums1[i] + nums2[j];
    13.             h1[sum]++;
    14.         }
    15.     }
    16.     //步骤二，map查询，记录次数
    17.     for(int i = 0; i < size; i++){
    18.         for(int j = 0; j < size; j++){
    19.             sum = nums3[i] + nums4[j];
    20.             auto item = h1.find(-sum);
    21.             if(item != h1.end()){
    22.                 Ycount += h1[-sum];
    23.             }
    24.         }
    25.     }
    26.     return Ycount;
    27. }
    28.  
    29. int main() {
    30.     int n;
    31.     cin >> n;
    32.     vector<int> n1(n),n2(n),n3(n),n4(n);
    33.     for (int i = 0; i < n; ++i) {
    34.         cin >> n1[i];
    35.     }
    36.     for (int i = 0; i < n; ++i) {
    37.         cin >> n2[i];
    38.     }
    39.     for (int i = 0; i < n; ++i) {
    40.         cin >> n3[i];
    41.     }
    42.     for (int i = 0; i < n; ++i) {
    43.         cin >> n4[i];
    44.     }
    45.  
    46.     int result;
    47.     result = fourSumCount(n1,n2,n3,n4);
    48.     cout << result << endl;
    49.  
    50.     return 0;
    51. }
    52. /*************
    53. 示例1:
    54. 2
    55. 1 2
    56. -2 -1
    57. -1 2
    58. 0 2
    59. 示例2:
    60. 1
    61. 0
    62. 0
    63. 0
    64. 0
    65.  ************/

    383. 赎金信

    题目描述：

    给你两个字符串：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 由小写英文字母组成

    思路和想法：

    这里分为三个步骤。

    • 步骤一：用哈希数组记录magzine字母出现次数
    • 步骤二：遍历ransomNote，消耗magzine
    • 步骤三：判断magzine是否透支（有负数），是则返回false
    1. #include <bits/stdc++.h>
    2. using namespace std;
    3.  
    4. bool canConstruct(string ransomNote, string magazine) {
    5.     //因为magzine只由小写字母组成，26,采用数组哈希解决最好，不占空间的同时，查询时间也很短
    6.     int h1[26] = {0};
    7.     //步骤一，进行遍历,记录字母出现次数
    8.     for(int i = 0; i < magazine.size(); i++){
    9.         h1[magazine[i]-'a']++;
    10.     }
    11.  
    12.     //步骤二：再对ransomNote进行遍历，对应--
    13.     for(int i = 0; i < ransomNote.size(); i++ ){
    14.         h1[ransomNote[i]-'a']--;
    15.     }
    16.     //步骤三：对数组遍历，看其是否存在负数，存在return false
    17.     for(int i = 0; i < 26;i++){
    18.         if(h1[i] < 0) return false;
    19.     }
    20.     return true;
    21. }
    22.  
    23. int main() {
    24.     string str1,str2;
    25.     getline(cin,str1);
    26.     getline(cin,str2);
    27.  
    28.     bool result;
    29.     result = canConstruct(str1,str2);
    30.  
    31.     if(result == 1){
    32.         cout << "true" << endl;
    33.     }else{
    34.         cout << "false" << endl;
    35.     }
    36.  
    37.     return 0;
    38. }
    39. /*************
    40. 示例1:
    41. a
    42. b
    43. 示例2:
    44. aa
    45. ab
    46. 示例3：
    47. aa
    48. aab
    49.  ************/
  • 相关阅读:
    【Java】Apache HttpClient调用微信支付API v3报错：找不到证书序列号对应的证书
    location rewrite
    一级缓存和二级缓存在Mybaits和操作系统中分别指什么
    【每日一题Day33】LC799香槟塔 | 动态规划
    处理器美之华大170处理器
    Docker | 容器数据卷详解
    算法leetcode｜87. 扰乱字符串（rust重拳出击）
    自动编码器（AE）生成Mnist手写数字集，基于tensorflow和keras实现
    .NET的CancellationTokenSource和ManualResetEvent结合使用
    初级前端面试题（一） 之 html/css/js
  • 原文地址：https://blog.csdn.net/weixin_42373086/article/details/133437935