首页 > 编程语言 >代码随想录算法训练营第六天| leetcode242.有效的字母异位词、leetcode349.两个数组的交集、leetcode202.快乐数、leetcode1.两数之和

代码随想录算法训练营第六天| leetcode242.有效的字母异位词、leetcode349.两个数组的交集、leetcode202.快乐数、leetcode1.两数之和

时间:2024-10-30 11:46:31浏览次数:6  
标签:leetcode242 set return int List 随想录 num 哈希 两数

1. leetcode 242.有效的字母异位词

题目链接:242. 有效的字母异位词 - 力扣(LeetCode)

文章链接:代码随想录

视频链接:学透哈希表,数组使用有技巧!Leetcode:242.有效的字母异位词哔哩哔哩bilibili

自己的思路:首先就是对字符串进行分开成一个一个单独的字母,然后使用列表存储这些数据,再对这个数据进行排序,排序完后就输出两个字符串相等或者不等的值

1.1 自己写的代码

自己做题的思路就是暴力搜索,调用内部的函数进行计算

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        s.split()
        t.split()
        s_l = list(s)
        t_l = list(t)
        s_l.sort()
        t_l.sort()
        return s_l== t_l
1.2 哈希表的方法
1.2.1哈希表的思路
  1. 字符串总共有26个,所以建立一个可以容纳26个字符串的哈希表,初始值为0

  2. 统计第一个字符串s中每个字母出现的次数,这里计算就是用字符串位置减去第一个字母即'a'的值,计算两个字符串的值在python中转化为对ASCII码计算,函数是ord(),然后就是统计每个字符串出现的次数,对其数值进行相加

  3. 对第二个字符串t中的数据对哈希表进行一个减法的操作

  4. 对字符串中的字符进行循环,如果哈希表的值有不等于0的,则证明两个字符串不相等,否则就是相等

1.2.2 哈希表的代码
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        record = [0]*26
        for i in s:
            record [ord(i)-ord('a')] +=1
        for j in t:
            record [ord(j)-ord('a')]-=1
        for i in range(26):
            if (record[i]!=0):
                return False
        return True
1.3 本题小结
  1. 定义哈希表为数组的方法:recode= [0]*26

  2. 这种题一般就是会有一个简单的思路来做,但是这种思路的缺点就是计算时间会比较久,用哈希表的方法会节省很多的计算时间

2. leetcode 349.两个数组的交集

题目链接:349. 两个数组的交集 - 力扣(LeetCode)

文章链接:代码随想录

视频链接:学透哈希表,set使用有技巧!Leetcode:349. 两个数组的交集哔哩哔哩bilibili

自己的思路:首先就是创建一个空列表,然后对第一个列表里面的数据进行循环,如果第一个列表的数据在第二个列表中,就对空列表进行数据增加,最后使用set对其进行去重,输出

2.1 自己的思路

这种方法有一种暴力搜索的感觉

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        l = list()
        for i in nums1:
            if i in nums2:
                l.append(i)
        return list(set(l))
2.2 哈希表的方法

这道题数据最长在1000,所以进行哈希表的时候其实使用set和数组都是可以的

2.2.1 set哈希表的方法

发现python中直接使用集合的方式真的简单

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))
2.2.2 哈希表数组的方式

fun1

思路

  1. 首先建立两个空数组,初始值都为0

  2. 对两个数组进行判断,然后存储至这个空列表中

  3. 出错点:如何判断这两个已有数组的值是否相等,不是对其直接进行等于,这样没有用的哈希表的值也会进行相加,所以这里就是对二者的数值进行,然后判断有的话进行列表数组加,没有则继续循环

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        num_l1 = [0]*1005
        num_l2 = [0]*1005
        result = []
        for i in nums1:
            num_l1[i] +=1
        for j in nums2:
            num_l2[j] +=1
        for k in range(1005):
            if num_l1[k]*num_l2[k]>0:
                result.append(k)
        return result

fun2

思路:

  1. 创建一个空集合

  2. 对第一个数组的数进行循环,然后将其值添加值哈希表中

  3. 对第二个数组的值进行判断,如果第二个值的索引值和哈希表中规定的值相等,在空集合中添加第二个数组的下标

  4. 最后对这个集合使用列表进行返回即可

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set_num = set()
        num = [0]*1005
        for i in nums1:
            num[i] = 1
        for j in nums2:
            if num[j]==1:
                set_num.add(j)
        return list(set_num)
2.3 本题小结
  1. 集合方式在python中非常简单,即判断两个集合的交集即可进行输出

  2. 数组的方式则很重要的一点就是数组啥时候对数据相加,则是其值相乘大于0的时候。

3. leetcode 202.快乐数

题目链接:202. 快乐数 - 力扣(LeetCode)

文章链接:代码随想录

自己的思路:首先就是有一个东西去存储,存储的是n的每个位数数值平方的和,然后对这个数据进行判断,如果等于1了就返回真,否则就返回假。但是自己无法编译出来,其实,,,

3.1 集合的思路

思路

  1. 首先就是计算这个每位数平方的和

  2. 创建一个空集合,进入循环体内部,如果其值为1,返回True

  3. 如果这个值不为1,首先看看这个值在不在创建的集合中,如果在就输出False,陷入死循环了,否则就将这个输出值加入到所创建的集合中

class Solution:
    def isHappy(self, n: int) -> bool:
        record = set()
        while True:
            n = self.get_sum(n)
            if  n==1:
                return True
            if n in record:
                return False
            else:
                record.add(n)
            
    def get_sum(self,n: int) -> int:
        new_num =0
        while n:
            n,r = divmod(n,10)
            new_num +=r**2
        return new_num 
3.2 数组的思路

这种方法的精髓就在于将这个数字转换成字符串,然后在循环内部对其进行相乘,判断其值是否符合要求

class Solution:
    def isHappy(self, n: int) -> bool:
        record = []
        while n not in record:
            record.append(n)
            new_sum = 0
            n_str = str(n)
            for i in n_str:
                new_sum += int(i)**2
            if new_sum == 1: 
                return True
            else:
                n = new_sum
        return False
3.3 本题小结
  1. 计算一个数字的整数部分和余数部分,在python中可以使用divmod函数,例如m,n=divmod(23,10),那么m=2,n=3,这个就是计算方法

  2. 其他的需要注意就是将已经算出的新的sum值进行增加到列表或者集合中,如果在里面出现了相同的值,可以判断出这个代码已经死循环,则可以结束了

4. leetcode 1.两数之和

题目链接:349. 两个数组的交集 - 力扣(LeetCode)

文章链接:代码随想录

视频链接:学透哈希表,set使用有技巧!Leetcode:349. 两个数组的交集哔哩哔哩bilibili

自己的思路:首先就是对nums进行循环,然后再使用第二层循环从第一层循环的后面开始走,如果找到了一个i+j的数与目标值相等,则输出这个值即可

4.1 第一次写的代码
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if nums[i]+nums[j] ==target:
                    return [i,j]
4.2 哈希表的写法

思路

  1. 这道题返回的是值的下标,即索引位置,所以就想到了每个值对应一个下标,即键值对的对应关系

  2. 键值对就使用字典的方式,返回值为字典中的值

  3. 那么就对nums进行一个循环,循环包含其值和下标,所以使用enumerate函数,这样循环过程有两个数,下标和值本身

  4. 判断所需要两个值是否在里面呢,就需要进行一个计算,已知target的值,所以减去现在索引处的值,看得到的那个值在不在字典中,在就返回这两个的索引值

  5. 否则就将这个数值和索引值加到字典中

4.2.1字典的方法
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        recorde = dict()
        for index,value in enumerate(nums):
            if target-value in recorde:
                return [recorde[target-value],index]
            recorde[value] = index
        return []               
4.2.2 集合的方法

这个方法有点绕,就是找值对应的索引,所以需要用到index函数。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        recorde = set()
        for i,value in enumerate(nums):
            complement = target-value
            if complement in recorde:
                return [nums.index(complement),i]
            recorde.add(value)
        return []               
4.3 本题小结
  1. 这道题主要掌握的思路就是字典的查询,明白这里面存储的值是什么值,一般情况下其内部所存储的值为键和值

  2. 为什么这道题索引为值,数值为键:因为我们要进行计算,判断过程就是看键在不在这个字典中,如果在的话再返回键所对应的值,所以这么选择

5 本章小结

5.1 选择哈希表的方法
  1. 哈希表一般出现在列表集合和字典中,就是对值和索引有要求的时候是较好用的一种方法

  2. 列表:选择这个的时候,是因为其数据内部的长度较短,不会报索引太长的时候用这种方法最简单,一般就是比较一个数组中的数是不是在另一个数组,有多少在里面的情况

  3. 集合:选择集合就是真内部需要存储的数据足够的长,而且要求内部不重复的话会很好用

  4. 字典:这个时候就是即需要对值和下标都有判断的时候,就比较好用,例如两数之和的题目,对键进行判断其值,返回的是其所对应的值

5.2 python中的一些函数
  1. 计算一个值的整数和余数部分的方法r,n=divmod(23,10),这个就是计算23/10的整数和余数,r=2,n=3

  2. 计算一个值的ASCII码的函数ord(a)是计算ASCII中的数值

  3. 在集合中添加数组方式set().add(1)就是将1添加到集合中

  4. 两集合的交集的求法set(a) & set(b)

  5. 对字典添加数据的方法num = dict(), num[key]=val

  6. 索引数组中值对应的下标num.index[1]就是索引数值1在列表中的索引位置

标签:leetcode242,set,return,int,List,随想录,num,哈希,两数
From: https://blog.csdn.net/angela3264/article/details/143322518

相关文章

  • 【LeetCode】两数之和、大数相加
    主页:HABUO......
  • 代码随想录——栈与队列8-前K个高频元素
    法一、用数组排序思路用map保存元素和频率关系将元素和频率的键值对pair作为vector的基本元素,以频率为准进行从大到小的排序——O(nlogn)输出前K个pair的first,即数字本身代码classSolution{public:std::vector<int>topKFrequent(std::vector<int......
  • 代码随想录算法训练营day30| 452. 用最少数量的箭引爆气球 435. 无重叠区间 763.
    学习资料:https://programmercarl.com/0452.用最少数量的箭引爆气球.html重叠区域问题最远位置问题452.用最少数量的箭引爆气球(重叠区域;按左边界排序;i区间的左边界与i-1区间的右边界比较来确定是否重叠;更新i的右边界,取i与i-1区域右边界的最小值)点击查看代码classSolution(ob......
  • 代码随想录一刷-day3
    T209长度最小子数组核心:滑动窗口思想,如何用一个for循环达到两个循环的效果for(intj=0;j<num.size();j++){sum+=nums[j];//外层for循环内负责将窗口结束的坐标++;while(sum>=target){window_length=j-i+1;result=min(result,window_length);sum-=nums[i++];......
  • 代码随想录day14 二叉树(2)
    文章目录day11栈与队列(2)栈与队列的总结day13二叉树(1)day14二叉树(2)day11栈与队列(2)逆波兰表达式求值https://leetcode.cn/problems/evaluate-reverse-polish-notation/逆波兰表达式,也就是后缀表达式,所谓后缀就是指运算符写在后面。平常使用的算式则是一种......
  • 代码随想录-栈与队列6、7
    逆波兰表达式思路用栈操作运算:遇到数字则入栈;遇到算符则取出栈顶两个数字进行计算,并将结果压入栈中这里记录string类型相关操作:判断token是否是数字,不可像char类型用string重载的>=,<=,前者由于用ASCII码表示,后者按字典序比较,例如1<2所以字符串比较"10"<"2"。所以直接......
  • 代码随想录:路径总和系列
    112.路径总和使用前序遍历/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*TreeNode(){}*TreeNode(intval){this.val=val;}*TreeNode(intval,TreeNode......
  • 代码随想录 -- 动态规划 -- 不同路径
    62.不同路径-力扣(LeetCode)思路:dp[i][j]含义:到达第(i,j)个格子有多少种走法递推公式:dp[i][j]=dp[i-1][j]+dp[i][j-1]初始化:dp[0][j]=1:到达第一行的格子都只有一种走法;dp[i][0]=1:到达第一列的格子也都只有一种走法遍历顺序:从上到下,从左到右classSolution(object):def......
  • 代码随想录算法训练营第十一天|leetcode150. 逆波兰表达式求值、leetcode239. 滑动窗
    1leetcode150.逆波兰表达式求值题目链接:150.逆波兰表达式求值-力扣(LeetCode)文章链接:代码随想录视频链接:栈的最后表演!|LeetCode:150.逆波兰表达式求值_哔哩哔哩_bilibili自己的思路:这是一道有思路,但是思路并不多的题目,就是我会觉得是先将数据进行添加,然后对于符号通过倒......
  • 代码随想录算法训练营day27| 122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃
    学习资料:https://programmercarl.com/0122.买卖股票的最佳时机II.html#算法公开课贪心PART2学习记录:122.买卖股票的最佳时间2(求最大利润,贪心:把所有正数相加;后一天与当天的股票价格差值,若为正就加入利润,若为负,则不加)点击查看代码classSolution:defmaxProfit(self,pr......