devbox
Cpp五条
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法练习day6

作者：Cpp五条 | 2024-05-12 18:13:28

赞

踩

算法练习day6

哈希表理论基础

哈希表在放弃算法后，就再也没有接触过这个了。

c++标准库提供的数据结构中，有数组、set和map三种可以用于实现哈希表。

  • 数组不用提

  • set：中文是集合的意思

c#的数据结构中，也有hashtable、hashSet和dictionary可以用。

有效的字母异位词

代码随想录 0242.有效的字母异位词

242. 有效的字母异位词 - 力扣（LeetCode）

（用时：0.5小时）

思路

这道题直接用双重循环直接搜索也是可以的，这个思路比较粗暴就不多说。

题目需要我们比较两个字符串的字母是否互为异位。我们可以查看两个字符串的字母是否完全一样，需要看的是字母的出现频率是否一样。

一般的思路就是先将第一个字符串中元素出现的频率情况记录下来，接着与第二个字符串进行对照。记录的容器有很多种，第一反应想到的是数组。用数组下标区别不同元素，记录出现的频率即可。

这里用数组下标区别元素，对应统计频率的想法就是哈希的思想，这里哈希的实现结构就是数组。（字母只有26个，故可以用数组。）

总结来说：

  • 首先需要用一个循环将第一个字符串元素的出现情况更新在哈希数组上

  • 接着在用一个循环将第二个字符串元素的出现情况更新在同一哈希数组上（或者可以用两个哈希数组，然后比较不同也行）

  • 最后再用一个循环，判断两个字符串元素的出现情况是否一样（如果是两个哈希数组就直接比较即可，如果是一个哈希数组，那就通过哈希值来判断。）

错误

写的过程中也有遇到一些错误：

  1. 后面两个循环合并在一起写了（即将第二个字符串元素的出现情况的更新与判断两个字符串元素的出现情况放在了一起同时进行）

  2. 第三个循环中的if判断条件出错（写成了hash[i]<0）（即判断两个字符串元素的出现情况是否一样的条件写错了。

个人理解如下：

  • 后面两个循环合并在一起写了

    不能把后面两个循环合在一起写。第二个循环的目的是记录字符串t字母的出现情况，第三个循环的目的是查看所有字母的情况。第二个循环中是不会遍历到所有字母的。

  • 第三个循环中的if判断条件出错（写成了hash[i]<0）

    借用官方提供的测试数据：s="ab" t="a"。在最后一个循环中，a对应的数组值是0，但b是1。只有当哈希数组中所有的值都等于0，才表示两个字符串元素的出现情况完全相同。这里应该用hash[i]!=0判断才行。

代码实现

  1. /// <summary>
  2. /// 哈希数组遍历
  3. /// </summary>
  4. /// <param name="s"></param>
  5. /// <param name="t"></param>
  6. /// <returns></returns>
  7. public bool IsAnagram(string s, string t)
  8. {
  9.     int[] hash = new int[26];
  10. ​
  11.     for (int i=0;i<s.Length;i++)
  12.     {
  13.         hash[s[i] - 'a']++;
  14.     }
  15. ​
  16.     for (int i=0;i<t.Length;i++)
  17.     {
  18.         hash[t[i] - 'a']--;
  19.     }
  20. ​
  21.     for (int i=0;i<hash.Length;i++)
  22.     {
  23.         if (hash[i]!=0)
  24.         {
  25.             return false;
  26.         }
  27.     }
  28.     return true;
  29. }

两个数组的交集

代码随想录 两个数组的交集

349. 两个数组的交集 - 力扣（LeetCode）

（用时：1小时）

思路

本道题要找两个数组的交集。根据力扣上的示例，可以认为找交集是要找两个数组重复的元素。判断一个元素是否重复，就是查看在这两个数组中，该元素是否都出现了。

简单的暴力枚举就是两层循环直接搜索。

这里卡哥提供的是用哈希的思路。力扣的题目上两个数组的数值都小于1000，故可以用数组实现哈希表。卡哥也有解释这是力扣后面修改的条件，当数值大到一定程度时，数组就会很费空间。因此本道题我们考虑用其他的容器来实现。

卡哥教的c++使用的是set集合结构，在c#中可以使用hashSet。

总结来说：

  • 首先在第一个数组中统计出现的元素。

  • 接着在第二个数组中判断前面出现的元素是否有出现。在这同时要记录下重复的元素。

重点

本道题和上一题有些不一样，上一题的元素是比较两者的出现频率是否一样，这一题的元素是比较两者是否都出现过，并且还需要记录两者都出现的元素本身。

这里需要注意两个重点：

  1. 元素只要在两者出现过就可以了。

    有一处出现了多次和出现一次是一样的，那么意味着要给数组的元素去重。

  2. 两者都出现的元素要记录下来。

    记录的条件是通过哈希表判断出来的：要么就得在第二步判断元素是否重复出现时一起记录；要么就得先将判断结果记录下来后续再来一个循环构造答案数组。

    如果是前者，边判断边记录。

    • 普通的数组结构，数组的长度是固定的。为了保险将长度提前定义成足够大，那么就需要同时记录数组的有效长度，以便最后在对数组进行处理，去掉额外的数组空间。

    • 此外c#里面还有list、arrayList等其他数据结构可以使用，这些可以实现动态数组。

    如果是后者，先将判断结果记录下来。

    • 记录的同时需要一起记录有效数组的长度，在后续构建答案数组时使用。

代码实现

哈希数组实现：

  1. /// <summary>
  2. /// 哈希数组实现
  3. /// </summary>
  4. /// <param name="nums1"></param>
  5. /// <param name="nums2"></param>
  6. /// <returns></returns>
  7. public int[] Intersection(int[] nums1, int[] nums2)
  8. {
  9.     int ansLen = 0;
  10. ​
  11.     //构建哈希数组
  12.     int[] hash = new int[1001];
  13.     for (int i=0;i<nums1.Length;i++)
  14.     {
  15.         //输入构建哈希数组时，nums1去重
  16.         if (hash[nums1[i]]==0)
  17.         {
  18.             hash[nums1[i]]++;
  19.         }
  20.     }
  21. ​
  22.     //查找并更新哈希数组
  23.     for (int i=0;i<nums2.Length;i++)
  24.     {
  25.         if (hash[nums2[i]]==1)
  26.         {
  27.             //通过哈希数组查找时，num2去重
  28.             hash[nums2[i]]++;
  29.             ansLen++;
  30.         }
  31.     }
  32. ​
  33.     //通过哈希数组得到数组交集
  34.     int[] ans = new int[ansLen];
  35.     ansLen = 0;
  36.     for (int i=0;i<hash.Length;i++)
  37.     {
  38.         if (hash[i] == 2)
  39.         {
  40.             ans[ansLen++] = i;
  41.         }
  42.     }
  43.     return ans;
  44. ​
  45. }

用hashSet实现：

  1. /// <summary>
  2. /// 用hashset实现
  3. /// </summary>
  4. /// <param name="nums1"></param>
  5. /// <param name="nums2"></param>
  6. /// <returns></returns>
  7. public int[] Intersection2(int[] nums1, int[] nums2)
  8. {
  9.     HashSet<int> hashSet = new HashSet<int>();
  10.     HashSet<int> ans = new HashSet<int>();
  11. ​
  12.     foreach (int num in  nums1)
  13.     {
  14.         hashSet.Add(num);
  15.     }
  16. ​
  17.     foreach (int num in nums2)
  18.     {
  19.         if (hashSet.Contains(num))
  20.         {
  21.             ans.Add(num);
  22.         }
  23.     }
  24. ​
  25.     return ans.ToArray<int>();
  26. }

本题用的还是HashSet来定义答案数组，用ToArray函数即可转成普通数组。用HashSet主要时因为

综合考虑，还是HashSet方便。

快乐数

代码随想录 快乐数

202. 快乐数 - 力扣（LeetCode）

（用时：0.5小时）

思路

刚开始看到这道题，第一反应是循环、递归这些东西。

题目要求就是要一直求各个位数的平方和，直到结果为1，或者无限循环下去永远都不会为1。

重点

这道题的重点有两个：

  1. 各个位数平方和的求法。

  2. 如何判断这个结果永远都不会到1。

个人理解：

  • 各个位置上数字平方和的求法很简单，用模运算和除法即可。

  • 关于如何判断这个结果永远都不会到1，这里就出现了错误。

错误

  1. 思路有误。认为让其始终循环，直到其s<10或小于某个数时就会停止

  2. 找到了1的判断出错。

个人理解如下：

  • 思路有误。认为让其始终循环，直到其s<10或小于某个数时就会停止。

    事实上，s即使小于10（当前的结果是个位数），依旧能够通过一次平方变为更大的数。就算是找到个位数，一次的平方无法达到更多的位数，但是多几次平方，依可以以变回去。思考的时候忽略了这道题是只要没有出现1，就需要一直平方下去。而只有1一直平方下去始终不变。

    正确思路：正确的想法应该是根据题目要求一直让各个位数的数字平方然后相加。题目提到说会一直无限循环，那么当开始重复循环时，就代表已经是无法找到1了。

  • 找到了1的判断出错。

    当最原始的数在运算中，某一次所有位数的平方和是1时，就代表该数是开心数。

    s是用于累加平方的平方和结果。当平方和为1时就表示其是开心数，但while此时的主要功能是用于累加平方和，可能会出现最高位是1导致误判的情况，因此平方和为1且当前的数字各位数都已取出（即n=0）才能确定原始数是开心数。

代码实现

hashSet解法：

  1. /// <summary>
  2. /// hashSet解法
  3. /// </summary>
  4. /// <param name="n"></param>
  5. /// <returns></returns>
  6. public bool IsHappy(int n)
  7. {
  8.     int s = 0;
  9.     HashSet<int> hashSet = new HashSet<int>();
  10. ​
  11.     while(true)
  12.     {
  13.         s += (n % 10) * (n % 10);
  14.         n = n / 10;
  15. ​
  16.         if (n == 0)
  17.         {
  18.             if (s==1)
  19.             {
  20.                 return true;
  21.             }
  22. ​
  23.             if (!hashSet.Add(s))
  24.             {
  25.                 return false;
  26.             }
  27.             n = s;
  28.             s = 0;
  29.         }
  30.     }
  31. }

两数之和

代码随想录 两数之和

1. 两数之和 - 力扣（LeetCode）

（用时：0.5小时）

思路

这道题其实就是给定和，让我们在数组中查找能够让加法等式成立的元素。

等式的和是确定的，当我们已知加数时，被加数是可以被计算出来的。那么这就意味着，我们可以在数组中从头进行遍历，每确定一个数为加数，就在数组中查看另外的数中是否有被加数。这个思路就是简单的暴力枚举方法。

也可以用数组去记录值的出现情况，每次判断这个值是否有在这个数组中出现时通过“查表”即可，这里就是哈希表的方法。

哈希表的结构有很多。target最大可以到109，用哈希数组就不合适了。并且题目要求是要输出数组下标。

卡哥将c++时用的是map，而c#我是用的是字典dictionary

  • 哈希表HashTable对于int,float这些值类型还需要进行装箱等操作，会非常耗时。

  • 字典Dictionary表示键和值的集合，它支持泛型,相对好一点。

总结来说：

  • 整体是对数组进行遍历。

  • 在遍历时，首先计算出当前元素下的被加数。

  • 接着通过字典，查看被加数是否有出现在数组中。

    若出现了，则直接构建答案数组输出即可（题目提到可以假设只会有一个答案、同一元素的答案不会重复出现且可以按任意顺序返回答案）

    若未出现。若是字典中没有该数，值和下标加入字典，若有则不处理（数组可能是3，3，3的情况，元素值相同选一个即可。）

重点

  1. 注意两个if的顺序（即注意需要查找被加数是否出现和将加数进入字典这两个操作的先后顺序）

个人理解如下：

  • 注意两个if的顺序

    在循环中，我们遍历数组，通过结果target可以求得在当前数组元素下的被加数，接着我们需要查找被加数是否出现、将加数进入字典。这里有一个顺序的问题，两个if的顺序本质上是先找被加数还是先增加加数进字典？

    如果先增加加数进字典，接着查找被加数是否出现，那么当被加数和加数数值相等时，就被被判定为已出现，那么就是会让数组的同一个元素在答案里重复出现，这不符合题意。

    先查找被加数再将加数加入字典，这样可以避免重复用一个元素的情况。

代码实现

键值对结构实现：

  1. /// <summary>
  2. /// 键值对数据结构实现
  3. /// </summary>
  4. /// <param name="nums"></param>
  5. /// <param name="target"></param>
  6. /// <returns></returns>
  7. public int[] TwoSum(int[] nums, int target)
  8. {
  9.     int[] ans = new int[2];
  10.     int tempNum;
  11.     Dictionary<int, int> numberDic = new Dictionary<int, int>();
  12. ​
  13.     for (int i=0;i<nums.Length;i++)
  14.     {
  15.         tempNum = target - nums[i];
  16. ​
  17.         if (numberDic.ContainsKey(tempNum))
  18.         {
  19.             ans[0] = numberDic[tempNum];
  20.             ans[1] = i;
  21.             break;
  22.         }
  23. ​
  24.         if (!numberDic.ContainsKey(nums[i]))
  25.         {
  26.             numberDic.Add(nums[i], i);
  27.         }
  28.     }
  29.     return ans;
  30. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/560122
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号