【代码随想录】Day6 哈希表理论基础 242.有效的字母异位词 ,349. 两个数组的交集 202. 快乐数 1. 两数之和

这篇具有很好参考价值的文章主要介绍了【代码随想录】Day6 哈希表理论基础 242.有效的字母异位词 ,349. 两个数组的交集 202. 快乐数 1. 两数之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

系列文章目录

【代码随想录】Day6 哈希表理论基础 242.有效的字母异位词 ,349. 两个数组的交集 202. 快乐数 1. 两数之和



前言

新的一部分-哈希表,哈希表之前做题相对比较熟练希望能快速复习


242.有效的字母异位词

Source: 题目
Note:以前刷的时候使用python字典,这次换做C++
注意数组就是简单的哈希表,但是数组的大小可不是无限开辟的

class Solution {
public:
    bool isAnagram(string s, string t) {
        // 
        int record[26] = {0};
        for (int i = 0; i < t.size(); i++) {
            record[t[i] - 'a']++;
        }
        for (int i = 0; i < s.size(); i++) {
            record[s[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (record[i]!=0) {
                return false;
            }
        }
        return true;
    }
};

Tips:

349. 两个数组的交集

Source: 题目
Note:python刷过,C++写的话要考察unordered_set的用法,需要加强认识
要熟悉不同容器之间的转换,以及unordered_set的基本用法如find(), for后范围的写法等和python有所不同
这道题涉及了vector-> unordered_set和 unordered_set->vector,都使用了范围构造的方法
vector (InputIterator first, InputIterator last)

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // 结果set,为了去重
        unordered_set<int> result_set;
        // nums1的去重数集
        unordered_set<int> nums_set(nums1.begin(),nums1.end()); 
        // 遍历nums1中的所有数字
        for (int num : nums2) {
            // 如果发现数字和nums1数集中某个数相同,加入最终结果集合
            //(可能会相同数字重复加入,所以使用unordered_set)
            if (nums_set.find(num)!=nums_set.end()) {
                result_set.insert(num);
            } 
        }
        // 这里是使用范围构造vector即vector (InputIterator first, InputIterator last);
        // end()指向范围结束迭代器 指向容器中最后一个元素之后的位置
        return vector<int>(result_set.begin(),result_set.end());
    }
};

Tips:这道题也可以构造1000+位的数组充当哈希表,因为num的大小限定在1000之下
参考如下:

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; // 存放结果,之所以用set是为了给结果集去重
        int hash[1005] = {0}; // 默认数值为0
        for (int num : nums1) { // nums1中出现的字母在hash数组中做记录
            hash[num] = 1;
        }
        for (int num : nums2) { // nums2中出现话,result记录
            if (hash[num] == 1) {
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

202. 快乐数

Source: 题目
Note:快乐数:求一个数各位的平方然后加和,如果不为1就将和作为新数继续求,如果最终能为1这个数就是快乐数,反之则不是。

这道题的关键在于理解如何判断非快乐数(原文链接:https://blog.csdn.net/2301_79811033/article/details/135854331)
核心在于该结论:
一个数是否为快乐数,只有两种可能:情况1:最终这个数变成了1后无限循环;情况2:无限循环但始终变不到 1。
鸽巢原理,假设有n个巢,和n+1个鸽子,那么至少会有一个巢鸟的数量>1
推导过程如下:
1.题目限定数最大只能是2的31次方-1,即2,147,483,647
2. 2,147,483,647<9,999,999,999,这个各个位的数的平方和为810,
即这个最大数2,147,483,647的平方和,其平方数和一定位于 [ 1, 810 ] 之间。
3.然后假设我们对2,147,483,647,进行811次这样的求平方数和的操作
4.由鸽巢原理可知,一定会有一个数重合,那么此时就构成了闭环。
5.那么我们也可以确定它一定会出现一个闭环,只不过是闭环中的数是否相同而已。

所以使用上面的结论我们可以知道,如果将每次判断时的平方和加入unordered_set,如果是情况2,循环一定会出现重复,而当sum出现重复的时候,就证明了这不是快乐数。

class Solution {
public:
    int getSum(int n) {
        int k = 0;
        int sum = 0;
        while (n != 0) {
            k = n % 10;
            n = n / 10;
            sum = k * k + sum; 
        }
        return sum;
    }
    bool isHappy(int n) {
        // 一想到需要查询是否有重复元素就要用unordered_set哈希表
        unordered_set<int> sum_set;
        while (1) {
            // 获取数字各位平方和
            int sum = getSum(n);
            if (sum == 1){
                return true;
            }
            // 如果在sum集合中找到重复元素,说明这是个无限循环,不是快乐数
            if (sum_set.find(sum)!=sum_set.end()) {
                return false;
            }
            // 将新的sum插入数集
            sum_set.insert(sum);
            // 更新下一个n为sum
            n = sum;
        }
    }
};

1. 两数之和

Source: 题目
Note:这道题用python刷过,但是不清晰C++内map的写法,所以既算预习也算复习
注意:find()函数返回一个iterator

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> nums_map;
        for (int i = 0 ; i < nums.size() ; i++) {
            auto iter = nums_map.find(target - nums[i]);  // 声明并初始化迭代器
            if (iter != nums_map.end()) {  // 使用迭代器进行比较
                return {iter->second, i};  // 如果找到,返回{找到的元素的索引,当前元素的索引}
            }
            nums_map.insert(pair<int,int>(nums[i], i));
        }
        return {};
    }
};

Tips:

  1. 为什么返回值是 {} 而不能是 NULL?
    在C++中,使用 {} 返回一个空的初始化列表,这在返回一个空的 std::vector 时非常有用。如果函数的返回类型是 std::vector,那么返回 {} 会构造并返回一个空的 vector 对象。而 NULL 通常用于指针类型的返回值,表示没有指向任何对象。在这种情况下,使用 {} 而不是 NULL 是因为我们需要返回一个空的 vector,而不是一个空指针。
  2. pair<int,int>(nums[i], i) 这里的 pair 用法是什么?
    std::pair 是C++标准库中的一个模板类,用于存储一对值,这对值可以是不同类型的。在这个例子中,pair<int, int>(nums[i], i) 创建了一个包含两个 int 类型的 pair,其中第一个元素是 nums[i] 的值,第二个元素是索引 i。pair 通常用于需要将两个相关联的值作为单个实体处理的情况。
  3. return {iter->second, i}; 又是什么用法?
    这行代码使用了初始化列表来构造并返回一个 vector 对象。iter->second 访问的是 unordered_map 中与 iter->first 对应的值(在本例中是数组中的索引),i 是当前元素的索引。例如,return {iter->second, i}; 这行代码实际上构造了一个包含两个整数的 vector,并将其返回。编译器根据函数的返回类型和提供的初始化列表自动推导出需要构造的 vector 对象。
  4. 为什么是 auto iter 而不是 unordered_map<int, int>::iterator iter?
    在C++11及之后的版本中,auto 关键字用于自动类型推导,让编译器根据初始化表达式自动推断变量的类型。在这个例子中,auto iter 能让编译器自动推断 iter 的类型为 unordered_map<int, int>::iterator,这简化了代码并提高了可读性。如果不使用 auto,你需要显式指定迭代器的完整类型,这会使代码更加冗长。使用 auto 不仅减少了需要键入的字符数量,还使代码更容易维护,因为如果 nums_map 的类型改变了,iter 的类型也会自动更新,而不需要手动修改。

总结

今天主要详细理解了C++中哈希表 unordered_set unordered_map的基础使用以及快乐数算法。
DAY 6 Finished 撒花~文章来源地址https://www.toymoban.com/news/detail-830649.html

到了这里,关于【代码随想录】Day6 哈希表理论基础 242.有效的字母异位词 ,349. 两个数组的交集 202. 快乐数 1. 两数之和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录刷题day6

    242.有效的字母异位词 用数组实现哈希; 注意初始化; int storage[26] = {0}; //定义数组的方法:  数据类型  数组名[数组长度]; 这时候index从 0 - 25;注意要初始化这个数组,不初始化会报错 349. 两个数组的交集 用unoderset来实现哈希,注意unorderset容器内部直接就做了去重操作 要

    2024年02月03日
    浏览(48)
  • 代码随想录day3|链表理论基础、移除链表元素、设计链表、翻转链表

    1、基本类型:单链表、双链表、循环链表 2、存储方式:和数组不一样,链表是随机存储在内存中,不是连续分配在内存中。 3、链表的定义: 定义了一个数据域,还有一个指针域,并且定义了一个构造函数。 4、链表的操作: 删除节点:  在图中,若需要删除D这个节点,只

    2024年02月05日
    浏览(46)
  • 代码随想录Day3|链表理论基础|203.移除链表元素|707.设计链表|206.反转链表

    虽然以前写过一次链表,但是真的已经忘得一干二净了 链表 :通过 指针 串联在一起的线性结构,每个 节点 都由数据域和指针域组成。 指针域 :存放下一个节点的指针,最后一个节点的指针域指向null,也即空指针 head :链表的入口节点,也即链表的头节点 链表的类型 单

    2024年02月11日
    浏览(54)
  • Day7代码随想录(1刷) 哈希表

    目录 454. 四数相加 II  383. 赎金信 15. 三数之和  18. 四数之和   给你四个整数数组  nums1 、 nums2 、 nums3  和  nums4  ,数组长度都是  n  ,请你计算有多少个元组  (i, j, k, l)  能满足: 0 = i, j, k, l n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 示例 1: 示例 2:    提示: n == nums1.l

    2024年03月25日
    浏览(45)
  • 代码随想录第6天| 哈希表理论基础 ,LeetCode242.有效的字母异位词,LeetCode349. 两个数组的交集,LeetCode202. 快乐数,LeetCode1. 两数之和

    哈希表(散列表)理论基础 : 哈希表是根据关键码的值而直接进行访问的数据结构。 直白来讲其实数组就是一张哈希表。   什么时候想到用哈希法, 当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法 。 当我们遇到了要快速判断一个元素是否出现集

    2024年02月10日
    浏览(66)
  • 代码随想录二刷 day06 | 哈希表之 242.有效的字母异位词 349. 两个数组的交集 202. 快乐数 1. 两数之和

    哈希表能解决什么问题呢?一般哈希表都是用来快速判断一个元素是否出现集合里。 242.有效的字母异位词 题目链接 解题思路: 题目的意思就是 判断两个字符串是否由相同字母组成。 字符a到字符z的ASCII是26个连续的数值,所以字符a映射为下标0,相应的字符z映射为下标25。

    2024年02月07日
    浏览(49)
  • 代码随想录第44天|动态规划:完全背包理论基础 518.零钱兑换II 377. 组合总和 Ⅳ

    代码随想录 (programmercarl.com) 动态规划之完全背包,装满背包有多少种方法?组合与排列有讲究!| LeetCode:518.零钱兑换II_哔哩哔哩_bilibili 完全背包和01背包问题唯一不同的地方就是,每种物品有无限件 。 完全背包中的物品可以添加多次,所以要从小到大遍历: 518. 零钱兑换

    2024年04月25日
    浏览(43)
  • 代码随想录打卡—day41—【DP】— 8.26+27 DP基础3

    343. 整数拆分 一开始做 没有思路,学习了题解才,ac代码: 后来仔细看题解,其实 for - j 的次数可以优化—— 注意 枚举j的时候,是从1开始的。从0开始的话,那么让拆分一个数拆个0,求最大乘积就没有意义了。 优化1: j 的结束条件是 j i - 1 ,其实 j i 也是可以的,不过

    2024年02月11日
    浏览(40)
  • 代码随想录 -- 哈希表--两数之和

    力扣hot1:两数之和 给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] +

    2024年02月09日
    浏览(38)
  • 第10天-代码随想录刷题训练-第五章 栈和队列- ● 理论基础 ● 232.用栈实现队列 ● 225. 用队列实现栈

    栈和队列对应的三个不同的STL版本,底层实现方式不一样, 为我们所知道的是 SGI STL 栈 栈提供 pop和push等接口, 不提供走访功能 也不提供迭代器, 不像map和set可以使用迭代器遍历,往往不被归类为容器,而是容器适配器 栈的内部实现结构可以使用 verctor、list 和 deque(默认)

    2024年02月04日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包