首页 > 编程语言 >代码随想录算法训练营第五天 | 哈希表基础、有效字母异位、两个数组交集、快乐数

代码随想录算法训练营第五天 | 哈希表基础、有效字母异位、两个数组交集、快乐数

时间:2024-06-05 15:46:03浏览次数:28  
标签:哈希 异位 训练营 随想录 快乐 dict https

哈希表基础理论
https://programmercarl.com/哈希表理论基础.html#哈希表
242有效字母异位词题
https://leetcode.cn/problems/valid-anagram/description/
242代码随想录解析
https://programmercarl.com/0242.有效的字母异位词.html#算法公开课
349两个数组的交集https://leetcode.cn/problems/intersection-of-two-arrays/
349代码随想录解析
https://programmercarl.com/0349.两个数组的交集.html#算法公开课
202快乐数
https://leetcode.cn/problems/happy-number/
202代码随想录解析
https://programmercarl.com/0202.快乐数.html#其他语言版本

哈希表基础理论

当我们遇到了要快速判断一个元素是否出现集合里的时候,就要考虑哈希法

python中重要和字典相关的语句

num = res.get(num,0)+1
##res.get(num,0) 如果存在num,则获取该数值,如果不存在该key,则赋值为0

242有效字母异位词

题目

给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。

注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。

题解

对于Python来说 有两种解决方案

  1. 直接采用python的collections.counter
  2. 采用哈希表 统计26字母的频次

解法代码

###解法一:counter
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s_dict = dict(collections.Counter(s))
        t_dict = dict(collections.Counter(t))
        if s_dict==t_dict:
            return True
        else:
            return False
##解法二
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record = [0]*26 ##哈希表
        for i in s:
            record[ord(i)-ord("a")]+=1
        for i in t:
            record[ord(i)-ord("a")]-=1
        for i in record:
            if i!=0:
                return False
        return True

349两个数组的交集

题目

给定两个数组 nums1 和 nums2 ,返回 它们的 交集。
输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

题解:

  1. 采用字典和集合统计
  2. 直接使用集合
##用集合方法
class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))

快乐数

题目

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为:

对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1,那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ;不是,则返回 false。

题解

要点在如果不是快乐数,可能无限循环始终变不到1
因此,只需要判断结果是否有重复出现即可

解题代码

class Solution:
    def isHappy(self, n: int) -> bool:
        curr = n
        res = {}
        while curr!=1 and res.get(curr,0)<2:
            num = 0
            for i in str(curr):
                num = num + int(i)**2
            curr = num
            res[num] = res.get(num,0)+1
        if curr==1:
            return True
        else:
            return False

标签:哈希,异位,训练营,随想录,快乐,dict,https
From: https://www.cnblogs.com/P201821440041/p/18233155

相关文章

  • 代码随想录算法训练营第二十七天 | 39.组合总和
    39.组合总和题目链接文章讲解视频讲解classSolution{private:vector<int>combine;vector<vector<int>>result;intcount=0;public:vector<vector<int>>combinationSum(vector<int>&candidates,inttarget){......
  • 算法基础之哈希表
    大家好,这里是教授.F什么是哈希表:   哈希表其实就是数组的pro版本。数组有下标,每个下标对应着一个值。哈希表也类似,哈希表有很多哈希值,然后每一个哈希值都会对应着一个值。就是这样:hash(key)哈希表的要求:    1.key必须是不变的。这点非常重要。所谓不可变类......
  • 逐梦航天!AIRIOT大学计划暑期训练营来啦!
    品质训练营助力“小白”,开启大神之路!AIRIOT大学计划暑期训练营等你来!“产业赋能,教育创新",为了促进物联网产业的纵深发展和创新,推进教育链、产业链与创新链的有机结合,提升理论、实践和创新能力,扩展学生视野,促进学生交流,为中国最有前途的物联网人才成长助力,航天科技AIRIOT大学计......
  • 算法训练营第10天|理论基础 232.用栈实现队列 225. 用队列实现栈
    理论基础Java中实现栈有以下两种方式:stack类LinkedList实现(继承了Deque接口)(1)Stack实现Stack底层是使用Vector的,而Vector支持线程同步,所以整体性能相对较低,如果没有多线程的场景,不建议使用Stack。(2)LinkedList实现LinkedList实现了List,Deque(实现了Queue接口)的接口,底层是双......
  • 算法训练营第九天|28. 实现 strStr()459.重复的子字符串 字符串总结 双指针回顾
    28.实现strStr()1.暴力解法:对主串的每一个字符都作为开头,尝试是否匹配字串,时间复杂度O(m*n)2.确保所有的变量在使用前都被明确地初始化了3.kmp算法之后慢慢理解!!!要记得!!!459.重复的子字符串1.暴力解法:列出所有的子字符串,看是否合法(子字符串开头固定),时间复杂度O(n*n)2.用模......
  • 代码随想录训练营第28天 | 93.复原IP地址、78.子集 、90.子集II
    93.复原IP地址本期本来是很有难度的,不过大家做完分割回文串之后,本题就容易很多了题目链接/文章讲解:https://programmercarl.com/0093.复原IP地址.html视频讲解:https://www.bilibili.com/video/BV1XP4y1U73i/和分割字符串类似,还有判断当前数字是否符合要求functionisValid......
  • 代码随想录算法训练营第四天 |节点交换、删除倒数n个节点、交叉链表、环形链表
    24题目链接:https://leetcode.cn/problems/swap-nodes-in-pairs/description/24题代码随想录讲解:https://programmercarl.com/0024.两两交换链表中的节点.html#思路19题链接:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/19题代码随想录:https://programmerca......
  • 代码随想录算法训练营day14(二叉树)
    代码随想录算法训练营day14(二叉树):学习内容:今天学习二叉树。二叉树节点标准写法(当前节点值,左右子节点,有点像链表节点的定义):structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(NULL),right(NULL){}};二......
  • 代码随想录算法训练营第四十六天|动态规划:完全背包理论基础、518.零钱兑换II、377. 组
    动态规划:完全背包理论基础文档讲解:代码随想录题目链接:52.携带研究材料(第七期模拟笔试)完全背包有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i]。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总......
  • 代码随想录算法训练营第四十九天| 139.单词拆分、多重背包
    139.单词拆分文档讲解:代码随想录题目链接:.-力扣(LeetCode)第一想法: 非空字符串s:背包非空单词的列表wordDict:物品每个物品可以使用多次,是一个完全背包问题看到这道题目的时候,大家应该回想起我们之前讲解回溯法专题的时候,讲过的一道题目回溯算法:分割回文串 (opens......