首页 > 其他分享 >【代码随想录训练营第42期 Day6打卡 LeetCode 242.有效的字母异位词 349.两个数组的交集 202.快乐数 1.两数之和】

【代码随想录训练营第42期 Day6打卡 LeetCode 242.有效的字母异位词 349.两个数组的交集 202.快乐数 1.两数之和】

时间:2024-07-22 18:57:15浏览次数:14  
标签:hash int sum 元素 随想录 哈希 return 打卡 两数

目录

一、序言

二、哈希表的相关知识

1.基本概念

2.常见的哈希结构

3.总结

三、题目及其题解

242.有效的字母异位词

题目链接

题解

思路1

思路2

思路3

349.两个数组的交集

题目链接

题解

202.快乐数

题目链接

题解

1.两数之和

题目链接

题解

思路1

思路2

四、小结


一、序言

今天是代码随想录训练营打卡的第六天,共完成了4道哈希表相关的题目。整体来讲难度不大,但是今天在202.快乐数那里卡住了,没想到怎么跳出循环,通过观看题解,对此也有了更为清晰的认识。话不多说,直接开始。

二、哈希表的相关知识

1.基本概念

哈希函数:一个将关键码值映射为表中存储位置的函数。理想的哈希函数应该能够将数据均匀地散列到各个桶中,减少哈希冲突的概率。

哈希表:基于哈希函数构建的数据结构,用于存储键值对。每个键通过哈希函数映射到一个特定的位置(索引或槽),该位置存储对应的值。

哈希冲突:不同的关键字通过相同的哈希函数计算出相同的哈希地址,这种现象称为哈希冲突或哈希碰撞。哈希冲突是不可避免的,但可以通过设计合理的哈希函数和冲突解决策略来尽量减少其影响。

2.常见的哈希结构

数组:vector<>

set(集合):一般用unordered_set<>

map(映射):一般用unordered_map<key,value>

3.总结

我的总结就一句话:当我们需要查询一个元素是否出现过,或者一个元素是否在集合里的时候,就要第一时间想到用哈希表。

三、题目及其题解

242.有效的字母异位词

题目链接

242. 有效的字母异位词 - 力扣(LeetCode)

题解
思路1

这里应该最容易想到的就是定义一个map型的哈希表,键和值分别存放元素和对应元素的个数,这里由于每个元素都是字符类型,故key为char型;元素个数存储在value处,int型。先通过循环记录s中每个元素的个数,再对t进行循环,如果t中某个元素个数比s中要多,就肯定不满足要求,直接return false;(记得刚开始先考虑size不同的情况)

这里直接看我的代码:

思路2

直接用哈希的第一种结构--数组,定义一个vector数组,数组的下标是0-25,对应着26个字母,先都初始化为0。对s中元素进行循环遍历,存储s中每个字母的个数。然后对t进行遍历,后边的操作就跟上一种思路一样了(用数字下标表示,这里感觉和第一种思路差不多,只是第二种思路将char类型转化为了数字,这样可以直接用简单的数组存储)。

代码如下:

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s.size() != t.size())        //先判断size不同的特殊情况
            return false;
        vector<int> hash(26,0);     //注意初始化全为0(26个字母)
        for(char ch : s)        
        {
            hash[ch - 'a']++;      //字母转化为数字下标
        }
        for(char ch : t)
        {
            hash[ch - 'a']--;
            if(hash[ch - 'a'] < 0)          
                return false;
        }
        return true;
    }
};
思路3

排序做法:思路十分简单,但复杂度相对较高,这里直接引用库函数sort()解决问题。

代码如下:

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        return s == t;
    }
};

349.两个数组的交集

题目链接

349. 两个数组的交集 - 力扣(LeetCode)

题解

和上一道题基本一样的思路,需要注意的就是这道题最后的结果每个元素不重复,这里我们可以在存入num1中元素时,将每个元素的个数都记为1,这样在遍历nums2中元素时,每出现一次相同的元素就减1,当元素个数为0时,就是重复出现的元素,而再次出现时,值就变为负数(不为0),就避免了重复计入的问题。(注意这道题最后return的结果是个数组,我们在这得先创建一个数组存储结果)

代码如下:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> hash;
        vector<int> ans;            //专门建立一个数组来储存结果
        for(int i : nums1)
        {
            hash[i]=1;          //关键处,将出现的元素个数都先记为1
        }
        for(int i : nums2)
        {
            hash[i]--;
            if(hash[i] == 0)         //刚好nums2出现第一次的元素,避免了后续重复插入
                ans.push_back(i);      
        }
        return ans;
    }
};

202.快乐数

题目链接

202. 快乐数 - 力扣(LeetCode)

题解

这个题有两个关键点:

1.定义一个函数求每位的数的平方和:考察数学知识,比较简单

2.找到循环终止条件(即什么时候停止对得到的数进行1的操作):这里采用哈希表,判断中间函数调用后是否出现过同样的值,若存在过,直接停止循环。

代码如下:(代码里有详细题解)

class Solution {
public:
    // 定义一个函数getSum取n的各个位数平方和
    int getSum(int n) {
        int sum = 0;
        while (n) {
            sum += (n % 10) * (n % 10);
            n = n/10;
        }
        return sum;
    }
    bool isHappy(int n) {
        unordered_set<int> hash;         //初始化哈希表,后续用哈希表判断循坏何时截止
        while(1) {                  //一个可一直进行的循环,直到达到循环内部的终止条件
            int sum = getSum(n);
            if (sum == 1)
                return true;
            // 如果这个sum曾经出现过,说明已经陷入了无限循环了,立刻return false
            if (hash.find(sum) != hash.end())     //判断元素sum是否出现过:hash.find(sum) != hash.end()
                return false; 
            else
                hash.insert(sum);        //sum没出现过就插入哈希表hash中
            n = sum;            //关键处:照应sum = getSum(n),在这里对n重新赋值
        }
    }
};

1.两数之和

题目链接

1. 两数之和 - 力扣(LeetCode)

题解

欢迎来到梦开始的地方。(相信大家都做过很多遍了)

思路1

暴力解法:简单易懂,直接看代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int i,j;
        for(int i=0;i<nums.size()-1;i++)
        {
            for(int j=i+1;j<nums.size();j++)
            {
                if(nums[i]+nums[j]==target)
                    return {i,j};
            }
        }
        return {};
    }
};
思路2

哈希表:我们在这创建hash用unordered_map<key,value>,因为我们得到的结果是值的下标,所以这里是将元素的值作为键(key),元素下标索引为值(value)。搞清楚这一点,剩下的思路就跟今天前两道题差不多了。(具体请看代码详解)

代码如下:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //注意我们在这创建hash是将元素的值作为键(key),元素下标索引为值(value),因为我们得到的结果是值的下标
        unordered_map<int, int> hash;       
        for (int i = 0; i < nums.size(); i++) {
            auto t = hash.find(target - nums[i]);
            if (t != hash.end())    //如果hash中找到了满足的t(注意t是另一个目标元素的值(hash中作为key),我们需要的是它的下标(即hash中的value,即是key->second))
                return {t->second, i};
            else
                hash[nums[i]] = i;          //将数组元素(注意是将元素值作为key,下标索引作为value)存入hash中
        }
        return {};
    }
};

四、小结

今天的打卡到此也就结束了,希望同诸君共同进步。我是算法小白,但也希望终有所获。

标签:hash,int,sum,元素,随想录,哈希,return,打卡,两数
From: https://blog.csdn.net/2303_79786049/article/details/140615142

相关文章

  • 昇思25天学习打卡营第14天|计算机视觉
    昇思25天学习打卡营第14天文章目录昇思25天学习打卡营第14天FCN图像语义分割语义分割模型简介网络特点数据处理数据预处理数据加载训练集可视化网络构建网络流程训练准备导入VGG-16部分预训练权重损失函数自定义评价指标Metrics模型训练模型评估模型推理总结引用......
  • 代码随想录算法训练营第17天 | 复习二叉搜索树
    2024年7月19日题654.最大二叉树熟练运用递归即可classSolution{publicTreeNodeconstructMaximumBinaryTree(int[]nums){intmaxNum=Integer.MIN_VALUE;intflag=-1;for(inti=0;i<nums.length;i++){if(nums[i]>maxNum){......
  • 「代码随想录算法训练营」第十七天 | 二叉树 part7
    235.二叉搜索树的最近公共祖先题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/题目难度:中等文章讲解:https://programmercarl.com/0235.二叉搜索树的最近公共祖先.html视频讲解:https://www.bilibili.com/video/BV1Zt4y1F7ww?share_so......
  • 代码随想录算法训练营第十一天| 144. 二叉树的前序遍历 , 94. 二叉树的中序遍历, 145.二
    今天主要学习了二叉树的基本概念,以及多种遍历方法。包含分别使用迭代思想和递归思想的前序遍历,中序遍历,后序遍历以及层次遍历。二叉树的基础知识二叉树二叉树的种类可以分为满二叉树和完全二叉树。满二叉树指的是一个二叉树仅包含度为0和度为2的结点,并且度为0的节点在同一层......
  • 代码随想录算法训练营第一天leetcode704二分查找27移除元素
    leetcode704,这是leetcode提交四次后通过的结果:classSolution{  publicintsearch(int[]nums,inttarget){    if(nums.length==1&&nums[0]==target)      return 0;    if(nums.length==2)      if(nums[0]==target)......
  • 代码随想录day6 | 242 有效字母异位词 349 两个数组交际 202 快乐数 1 两数之和
    hash表遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法242判断字母异位词关于字符串的遍历问题//什么情况下遍历的是rune[]int36类型,什么情况下遍历的是char字节类型?s:="Hello,世界"fori,r:=ranges{ fmt.Printf("Index:%d,Rune:%c,......
  • 代码随想录算法训练营第36天 | 动态规划基础2:62.不同路径、63.不同路径 II
    62.不同路径https://leetcode.cn/problems/unique-paths/submissions/548656029/代码随想录https://programmercarl.com/0062.不同路径.html63.不同路径IIhttps://leetcode.cn/problems/unique-paths-ii/description/代码随想录https://programmercarl.com/0063.不同路径......
  • 1. 两数之和
    题目:给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。示例1:输入:nums=[2,......
  • 一入循环深似海,代码随想录螺旋矩阵二刷
    代码随想录螺旋矩阵二刷leetcode59来看下螺旋矩阵。螺旋矩阵这道题确实很容易写着写着就绕进去了。首先读下题。给出正整数n,生成n*n的矩阵。我们来看其中一个用例,完成一个圈是需要四个循环去填充。但是四条边填充的时候要始终保持一样的规则,比如左闭右开的规则。那么转几圈呢......
  • 代码随想录训练营 Day4打卡 链表part02 24. 两两交换链表中的节点 19.删除链表的倒数
    代码随想录训练营Day4打卡链表part02一、力扣24.两两交换链表中的节点给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。示例1:输入:head=[1,2,3,4]输出:[2,1,4,3]算法思路:引入虚......