[5]-代码随想录算法训练营-day6-哈希-part1

缪白 / 2023-08-30 / 原文

代码随想录算法训练营第六天|哈希表-part1

1.Leecode 242.有效的字母异味词

题目

https://leetcode.cn/problems/valid-anagram/

思路

长26数组，下标0表示'a'，25表示'z'，初始化为0，读取字符串，记录对应的字母

利用拉链法，记录每个字母

刷随想录后想法

一个数组，一个累加，一个累减，如果全为0，则符合题目

实现困难
实现代码
class Solution {
public:
    bool isAnagram(string s, string t) {
        int hash[26];
        for (int i = 0; i < 26; i++){
            hash[i] = 0;
        }

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

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

        for(int i =0; i < 26; i++){
            if(hash[i] != 0){
                return 0;
            }
        }

        return 1;
    }
};
学习收获

一个数组实现判断，合理利用累加和累减，节省空间。

2.Leecode 349.两个数的交集

题目

https://leetcode.cn/problems/intersection-of-two-arrays/

思路

数组暴力

刷随想录后想法

借用unorder_set

实现困难

unorder_set用法不太熟练
实现代码
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set <int> result;
        unordered_set <int> nums_set(nums1.begin(), nums1.end());//将nums1转化为unordered_set
        for (int i=0; i < nums2.size(); i++){
            if(nums_set.find(nums2[i]) != nums_set.end()){
                result.insert(nums2[i]);
            }
        }

        return vector<int>(result.begin(), result.end());
    }
};
学习收获

数组being()和end()用法：http://c.biancheng.net/view/7376.html

范围for循环for(num : nums)：https://blog.csdn.net/HFGD2019/article/details/108737013

关于unordered_set使用：http://c.biancheng.net/view/7250.html

关于类型转换的用法vector<int>(result.begin(), result.end())

3.Leecode 202.快乐数

题目

https://leetcode.cn/problems/happy-number/

思路

无

刷随想录后想法

分析出死循环的条件，在死循环时跳出

实现困难

对n每一位的拆分

快乐数的计算

对于unordered_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) {
        int sum = 0;
        unordered_set<int>sums;
        while(1){
            sum = getSum(n);
            if(1 == sum){   //为1跳出循环
                return true;
            }

            //存在重复sum值， 即无限循环
            if(sums.find(sum) != sums.end()){
                // 存在重复值
                return false;
            }else{
                sums.insert(sum);
            }
            n = sum;
        }
    }
};
小记一下：
学习收获
大数拆分，利用while循环拆分数值每一位

关于unordered_set用法

读题仔细，分析提议，无限循环等价于重复出现同样的和值

4.Leecode 1.两数的和

题目

https://leetcode.cn/problems/two-sum/

思路

拆每一位，暴力

刷随想录后想法

无限循环的条件：某个和重复出现

利用unordered_map实现对过程中sum的记录

实现困难

对unordered_map不熟：查找、插入用法；返回参数的使用、键值的取用

对map进行insert时使用pair<int, int>(x, y)有些模糊
实现代码
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int , int >map;
        int s;
        int iter;
        for (int i=0; i < nums.size(); i++){
            s = target-nums[i];
            auto iter = map.find(s);
            if(iter != map.end()){
                //存在两数之和
                return {iter->second, i};
            }else{
                map.insert(pair<int, int>(nums[i], i));
            }

        }
        return {};
    }
};
学习收获

关于unordered_map使用：http://c.biancheng.net/view/7231.html

关于unordered_map：https://zh.cppreference.com/w/cpp/container/unordered_map

关于unordered_map.find：https://zh.cppreference.com/w/cpp/container/unordered_map/find、find返回参数解释

关于unordered_map.insert：https://zh.cppreference.com/w/cpp/container/unordered_map/insert

关于pair的用法：https://blog.csdn.net/LUSH_BOY/article/details/113484043