• 代码随想录算法训练营day6| 哈希表理论基础、242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和


    目录

    一、哈希表理论

    hash function

    ​编辑hash collision

    常见哈希结构

    1)set

    2)map

    二、(leetcode 242)有效的字母异位词

    三、(leetcode 349)两个数组的交集

    四、(leetcode 202)快乐数

    思路

    五、(leetcode 1)两数之和

    思路


    一、哈希表理论

    哈希表是根据关键码的值而直接进行访问的数据结构

    什么时候使用哈希法:当我们需要查询一个元素是否出现过,或者一个元素是否在集合里的时候,就要第一时间想到哈希法

    hash function

    hash collision

    解决办法

    • 拉链法
    • 线性探测法:满足tableSize>dataSize

    常见哈希结构

    1)set

    红黑树是一种平衡二叉搜索树,所以key值是有序的,但key不可以修改,改动key值会导致整棵树的错乱,所以只能删除和增加

    要使用集合来解决哈希问题的时候,优先使用unordered_set,因为它的查询和增删效率是最优的,如果需要集合是有序的,那么就用set,如果要求不仅有序还要有重复数据的话,那么就用multiset。

    2)map

    二、(leetcode 242)有效的字母异位词

    力扣题目链接

    状态:已AC,困在了一直考虑ASCII码上,但其实只要有差值即可

    1. class Solution {
    2. public:
    3. bool isAnagram(string s, string t) {
    4. int record[26] = {0};
    5. for (int i = 0; i < s.size(); i++) {
    6. // 并不需要记住字符a的ASCII,只要求出一个相对数值就可以了
    7. record[s[i] - 'a']++;
    8. }
    9. for (int i = 0; i < t.size(); i++) {
    10. record[t[i] - 'a']--;
    11. }
    12. for (int i = 0; i < 26; i++) {
    13. if (record[i] != 0) {
    14. return false;
    15. }
    16. }
    17. return true;
    18. }
    19. };

    三、(leetcode 349)两个数组的交集

    力扣题目链接

    状态:思路清楚,但代码混乱,哈希表unordered_set的用法需要学习

    1. class Solution {
    2. public:
    3. vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    4. unordered_set<int> result_set; // 存放结果,之所以用set是为了给结果集去重
    5. unordered_set<int> nums_set(nums1.begin(), nums1.end());//迭代器构造
    6. for (int num : nums2) {
    7. // 发现nums2的元素 在nums_set里又出现过
    8. if (nums_set.find(num) != nums_set.end()) {
    9. result_set.insert(num);
    10. }
    11. }
    12. return vector<int>(result_set.begin(), result_set.end());
    13. }
    14. };

    四、(leetcode 202)快乐数

    力扣题目链接

    状态:已AC,注意set.find(key)的用法

    思路

    判断sum是否重复出现,如果重复了就是return false, 否则一直找到sum为1为止

    1. class Solution {
    2. public:
    3. // 取数值各个位上的单数之和
    4. int getSum(int n) {
    5. int sum = 0;
    6. while (n) {
    7. sum += (n % 10) * (n % 10);
    8. n /= 10;
    9. }
    10. return sum;
    11. }
    12. bool isHappy(int n) {
    13. unordered_set<int> set;
    14. while(1) {
    15. int sum = getSum(n);
    16. if (sum == 1) {
    17. return true;
    18. }
    19. // 如果这个sum曾经出现过,说明已经陷入了无限循环了,立刻return false
    20. if (set.find(sum) != set.end()) {
    21. return false;
    22. } else {
    23. set.insert(sum);
    24. }
    25. n = sum;
    26. }
    27. }
    28. };

    五、(leetcode 1)两数之和

    力扣题目链接

    状态:思路都不清楚,败笔啊,不过看图清楚了,代码待回顾

    思路

    本题不仅要知道元素有没有遍历过,还要知道这个元素对应的下标,需要使用 key value结构来存放,key来存元素,value来存下标,那么使用map正合适

    • map用来做什么
    • map中key和value分别表示什么

    1. class Solution {
    2. public:
    3. vector<int> twoSum(vector<int>& nums, int target) {
    4. std::unordered_map <int,int> map;
    5. for(int i = 0; i < nums.size(); i++) {
    6. // 遍历当前元素,并在map中寻找是否有匹配的key
    7. auto iter = map.find(target - nums[i]);
    8. if(iter != map.end()) {
    9. return {iter->second, i};
    10. }
    11. // 如果没找到匹配对,就把访问过的元素和下标加入到map中
    12. map.insert(pair<int, int>(nums[i], i));
    13. }
    14. return {};
    15. }
    16. };

  • 相关阅读:
    I/O多路复用三种实现
    用vba实现将记录集输出到Excel模板
    网络安全相关
    常问面试题:TCP与UDP的区别
    助力企业转型,华为云CDN值得期待!
    vscode两个项目环境不一致怎么办
    程序员应该怎么学数学
    【LeetCode】1774. 最接近目标价格的甜点成本
    【钰娘娘】1373. 二叉搜索子树的最大键值和 DFS
    深入理解JVM虚拟机第二十二篇:详解JVM当中与操作数栈相关的字节码指令
  • 原文地址:https://blog.csdn.net/weixin_42179093/article/details/133279470