代码随想录算法训练营15期 Day 6 | 242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和网站首页 技术交流

代码随想录算法训练营15期 Day 6 | 242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

ASDWYang 2024-07-03 12:01:03

简介代码随想录算法训练营15期 Day 6 | 242.有效的字母异位词、349. 两个数组的交集、202. 快乐数、1. 两数之和

由于昨天是周日，周日是休息日，所以就是什么也没有写啦。今天是day06天，继续加油。

哈希表理论基础

建议：大家要了解哈希表的内部实现原理，哈希函数，哈希碰撞，以及常见哈希表的区别，数组，set 和map。

什么时候想到用哈希法，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。这句话很重要，大家在做哈希表题目都要思考这句话。

数组也是一个哈希表。

那么哈希表能够解决什么问题？
哈希表可以解决的问题是能够判断一个元素是否存在集合之中。

例如：在一个学校之中，想要知道一个同学是否在这个学校之中，一般我们查询的复杂度是O(n)，但是有了哈希表的存在，可以将查询的复杂度降低到O(1)。学生的姓名映射到一个表之中进行查询，就是一个哈希函数的过程。

一.哈希函数

通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。

二.哈希碰撞

如上面的这个图所示，在进行一个映射的时候，如果要是学生姓名过多的时候，会出现超出hashsize的情况，进行取模操作，但是还是会存在一个hash位置存在多个姓名的情况，这个问题我们称之为hash碰撞。

解决hash碰撞的方式一般是有两个：
（1）拉链法：在进行到hash碰撞的地方，使用一个链表将碰撞的位置的同学添加到一起。拉链法的使用要注意使用合适大小的数组，这样就是可以避免数组的浪费，同时还可以减少链表的长度。

（2）线性探针法

使用线性探测法，一定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。

三.常见的hash结构

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

std::set / map和std::multiset / multimap 的底层实现是红黑树，红黑树是一种平衡二叉搜索树，所以key值是有序的，但key不可以修改，改动key值会导致整棵树的错乱，所以只能删除和增加。

哈希法也是牺牲了空间换取了时间，因为我们要使用额外的数组，set或者是map来存放数据，才能实现快速的查找。

242.有效的字母异位词

建议：这道题目，大家可以感受到数组用来做哈希表给我们带来的遍历之处。

题目链接：力扣

本题的解题思路：首先是判断一个使用什么样的数据结构，一般的hash问题是存在三个hash结构。本题之中的字符的小写字母是连续的。

使用范围：在hash值比较小，范围可控使用数组；如果范围很大，使用set；带有value使用map。

class Solution {
public:
    bool isAnagram(string s, string t) {

        //本题是使用ASCLL进行相应的计算
        int hash[26] = {0};

        for(int i = 0;i<s.size();i++)
        {
            hash[s[i] - 'a']++;
        }

        for(int i = 0;i<t.size();i++)
        {
            hash[t[i] - 'a']--;
        }

        for(int i = 0;i<26;i++)//注意这个地方需要赋值的地方是26，否则会存在错误
        {
            if(hash[i] != 0)
            {
                return false;
            }
        }

        return true;
    }
};

349. 两个数组的交集

建议：本题就开始考虑什么时候用set 什么时候用数组，本题其实是使用set的题，但是后来力扣改了题目描述和测试用例，添加了 0 <= nums1[i], nums2[i] <= 1000 条件，所以使用数组也可以了，不过建议大家忽略这个条件。尝试去使用set。

题目链接：力扣

本题的思路是进行一个交集的计算过程，是进行去重的。这个题如果要是数值是非常大的情况，可以使用set。比如：[0,1,10000]如果要是使用数组就过于大了。
hash表最擅长解决给你一个元素，这个元素是否在集合之中出现过。
首先将一个数组变成unorder_set multiset set,underset是hash表情况，做映射的情况时，效率是最高的。由于要进行去重，因此使用underset是非常必要的。

使用unordered_set方式:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

            //首先声明一个unorder_set数组，用于存在nums1
            unordered_set<int> num111(nums1.begin(),nums1.end());

            //声明一个unordered_set数组,用来存放新的
            unordered_set<int> result;

            for(int num:nums2)
            {
                if(num111.find(num) != num111.end())//说明是找到了
                {
                    result.insert(num);
                }
            }

            return vector<int> (result.begin(),result.end());

    }
};

使用数组方式:首先将nums1之中的东西都是变成为1,然后遍历nums2,看看是否二者都是存在这个数组的,如果要是存在的话,需要将其插入到新的数组之中.

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

         
            //声明一个unordered_set数组,用来存放新的,可以实现去重的操作
            unordered_set<int> result;

            //声明一个数组,将nums1之中的东西都放入进去
            int nums111[10000] = {0};

            for(int num:nums1)
            {
                 nums111[num]=1;//注意:这个地方必须是=1,不是++,因为有些地方初始的时候是空的.
            }

            for(int num:nums2)
            {
                 if(nums111[num] == 1)
                 {
                     result.insert(num);
                 }

            }

            return vector<int> (result.begin(),result.end());

    }
};

202. 快乐数 (一会儿看)

建议：这道题目也是set的应用，其实和上一题差不多，就是套在快乐数一个壳子

题目链接：力扣

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. 两数之和

建议：本题虽然是力扣第一题，但是还是挺难的，也是代码随想录中数组，set之后，使用map解决哈希问题的第一题。

题目链接：力扣

解题思路:本题要存放两个东西,一个是数组的元素,另外是一个下标,因此,本题使用<key,value>的方式进行存放.另一方面,查找的是key,这里将key的值使用元素放置.下标作为value存放.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {

        //首先,声明一个map,用来存放数组与下标
        unordered_map<int,int> map;
        int i = 0;
        //遍历相应的nums数组
        for(int num:nums)
        {
            int s = target - num;

            if(map.find(s)!=map.end())//说明找到了
            {
                return {map.find(s)->second,i};
            }
            map.insert(pair<int,int>(num,i));
            i++;
        }
        return {};
    }
};

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。