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哈希表的思路
-
字符串总共有26个,所以建立一个可以容纳26个字符串的哈希表,初始值为0
-
统计第一个字符串
s
中每个字母出现的次数,这里计算就是用字符串位置减去第一个字母即'a'
的值,计算两个字符串的值在python中转化为对ASCII码计算,函数是ord()
,然后就是统计每个字符串出现的次数,对其数值进行相加 -
对第二个字符串
t
中的数据对哈希表进行一个减法的操作 -
对字符串中的字符进行循环,如果哈希表的值有不等于
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 本题小结
-
定义哈希表为数组的方法:
recode= [0]*26
-
这种题一般就是会有一个简单的思路来做,但是这种思路的缺点就是计算时间会比较久,用哈希表的方法会节省很多的计算时间
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
思路:
-
首先建立两个空数组,初始值都为0
-
对两个数组进行判断,然后存储至这个空列表中
-
出错点:如何判断这两个已有数组的值是否相等,不是对其直接进行等于,这样没有用的哈希表的值也会进行相加,所以这里就是对二者的数值进行乘,然后判断有的话进行列表数组加,没有则继续循环
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
思路:
-
创建一个空集合
-
对第一个数组的数进行循环,然后将其值添加值哈希表中
-
对第二个数组的值进行判断,如果第二个值的索引值和哈希表中规定的值相等,在空集合中添加第二个数组的下标
-
最后对这个集合使用列表进行返回即可
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 本题小结
-
集合方式在python中非常简单,即判断两个集合的交集即可进行输出
-
数组的方式则很重要的一点就是数组啥时候对数据相加,则是其值相乘大于0的时候。
3. leetcode 202.快乐数
文章链接:代码随想录
自己的思路:首先就是有一个东西去存储,存储的是n
的每个位数数值平方的和,然后对这个数据进行判断,如果等于1了就返回真,否则就返回假。但是自己无法编译出来,其实,,,
3.1 集合的思路
思路:
-
首先就是计算这个每位数平方的和
-
创建一个空集合,进入循环体内部,如果其值为1,返回True
-
如果这个值不为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 本题小结
-
计算一个数字的整数部分和余数部分,在python中可以使用
divmod
函数,例如m,n=divmod(23,10)
,那么m=2,n=3
,这个就是计算方法 -
其他的需要注意就是将已经算出的新的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 哈希表的写法
思路:
-
这道题返回的是值的下标,即索引位置,所以就想到了每个值对应一个下标,即键值对的对应关系
-
键值对就使用字典的方式,返回值为字典中的值
-
那么就对nums进行一个循环,循环包含其值和下标,所以使用
enumerate
函数,这样循环过程有两个数,下标和值本身 -
判断所需要两个值是否在里面呢,就需要进行一个计算,已知
target
的值,所以减去现在索引处的值,看得到的那个值在不在字典中,在就返回这两个的索引值 -
否则就将这个数值和索引值加到字典中
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 本题小结
-
这道题主要掌握的思路就是字典的查询,明白这里面存储的值是什么值,一般情况下其内部所存储的值为键和值
-
为什么这道题索引为值,数值为键:因为我们要进行计算,判断过程就是看键在不在这个字典中,如果在的话再返回键所对应的值,所以这么选择
5 本章小结
5.1 选择哈希表的方法
-
哈希表一般出现在列表集合和字典中,就是对值和索引有要求的时候是较好用的一种方法
-
列表:选择这个的时候,是因为其数据内部的长度较短,不会报索引太长的时候用这种方法最简单,一般就是比较一个数组中的数是不是在另一个数组,有多少在里面的情况
-
集合:选择集合就是真内部需要存储的数据足够的长,而且要求内部不重复的话会很好用
-
字典:这个时候就是即需要对值和下标都有判断的时候,就比较好用,例如两数之和的题目,对键进行判断其值,返回的是其所对应的值
5.2 python中的一些函数
-
计算一个值的整数和余数部分的方法
r,n=divmod(23,10)
,这个就是计算23/10的整数和余数,r=2,n=3
-
计算一个值的ASCII码的函数
ord(a)
是计算ASCII中的数值 -
在集合中添加数组方式
set().add(1)
就是将1添加到集合中 -
两集合的交集的求法
set(a) & set(b)
-
对字典添加数据的方法
num = dict(), num[key]=val
-
索引数组中值对应的下标
num.index[1]
就是索引数值1在列表中的索引位置