文章目录
- 前言
- 一、242. 有效的字母异位词
-
- 题解
- 代码
- 二、349. 两个数组的交集
-
- 题解
- 代码
- 三、202. 快乐数
-
- 题解
- 代码
- 四、1. 两数之和
-
- 题解
- 代码
- 五、454. 四数相加 II
-
- 题解
- 代码
- 六、383. 赎金信
-
- 题解
- 代码
- 七、15. 三数之和
-
- 题解
- 代码
- 八、18. 四数之和
-
- 题解
- 代码
前言 本文的例题都将通过python来实现，但是哈希表在python中的表示为字典形式。所以与其他语言还是有较大的冲突。在python中，其实有一个非常好用的类——defaultdict。具体用法见：
https://blog.csdn.net/yangsong95/article/details/82319675
一、242. 有效的字母异位词
文章图片
题解 数组其实也是一个特殊的哈希表，而且这道题目中字符串只有小写字符，那么就可以定义一个数组，来记录字符串s里字符出现的次数。数组的长度可以定为26，初始化为0，因为a到z的ASCII也是26个连续的值。定义一个数组叫做record用来上记录字符串s里字符出现的次数。
需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。
再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。
那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。
那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。
最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。
代码
'''
新建一个0-25数组，在遍历s的时候，相应位置加一，遍历t的时候，相应位置减一，
如果最后数组全为0，则返回True，否则返回false
'''class Solution:
def isAnagram(self, s: str, t: str) -> bool:
res = [0]*26
for i in range(len(s)):
res[ord(s[i])-ord('a')] += 1 #ord()函数为python内置函数，可以求出ASCII码，此题只需要求出与a的相对距离就好了
print(res)
for j in range(len(t)):
res[ord(t[j])-ord('a')] -= 1
print(res)
for k in range(len(res)):
if res[k] != 0:
return False
breakreturn True
下面这个写法没有使用数组作为哈希表，使用了上文提到的defaultdict
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
from collections import defaultdicts_dict = defaultdict(int)
t_dict = defaultdict(int)for x in s:
s_dict[x] += 1for x in t:
t_dict[x] += 1return s_dict == t_dict
二、349. 两个数组的交集
文章图片
题解 其实这个题目可以使用直接遍历的方式来暴力求解，但是时间复杂度太高，这里使用set来解决这个问题。
set和list其实有着本质的区别，set会去重，list不会
代码 代码很简单，因为经过set处理后，列表里的元素就没有重复的了
'''
其实这个题目可以通过遍历来实现，但是时间复杂度太高，可以用set来解决这个问题
set会去重
'''
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return list(set(nums1) & set(nums2))
三、202. 快乐数
文章图片
题解 这个题需要理解什么是快乐数，其实只要搞明白，当一个数在计算过程中重复出现某一个结果的时候，这个数就必然不是快乐数了，因为已经陷入了无限循环中，如果最后的计算结果为一，那它就是快乐数。还有一点要求，理解对一个数分解的逻辑。
代码
'''
如果一个数重复出现，则说明进入了死循环，必不是快乐数'''
class Solution:
def isHappy(self, n: int) -> bool:
#计算过程
def cal_happy(num):
sum = 0
#从个位开始计算
while num:
sum += (num%10)**2
num = num//10
return sum
#新建一个集合存储已经出现过的数
record = set()while True:
n = cal_happy(n)
#如果n=1，，说明是快乐数
if n == 1:
return True
#如果已经在集合中，则直接返回False
if n in record:
return False
else:
record.add(n)
四、1. 两数之和
文章图片
题解 这个题目给出了一个数组，但是在返回时要求返回下标。我们可以想一下，在Python中有什么存储结构可以同时存储两种互相对应的数据呢？没错，那就是字典。我们可以让key保存数值，value保存数值所在的下标。
代码
'''
使用字典，因为我们要存储值和下标
'''
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
record = dict()
#用枚举更方便，就不需要通过索引再去取当前位置的值
for idx,val in enumerate(nums):
if target-val not in record:
record[val]=idx
else:
#如果存在就返回字典记录索引和当前索引
return [record[target-val],idx]
五、454. 四数相加 II
文章图片
题解 首先先定义一个dict1，将num1和num2的和放入字典中，key为和,value为出现的次数
然后再定义一个dict2，判断num3和num4的和的相反数是否在dict2中，若存在就用count统计value
代码
'''
首先先定义一个dict1，将num1和num2的和放入字典中，key为和,value为出现的次数
然后再定义一个dict2，判断num3和num4的和的相反数是否在dict2中，若存在就用count统计value
'''
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
dict1 = dict()
for i in nums1:
for j in nums2:
if i+j in dict1:
dict1[i+j] += 1
else:
dict1[i+j] = 1count = 0
for i in nums3:
for j in nums4:
key = -(i+j)
if key in dict1:
count += dict1[key]
return count
六、383. 赎金信
文章图片
题解 这道题目和242.有效的字母异位词很像，有效的字母异位词 (opens new window)相当于求字符串a 和 字符串b是否可以相互组成 ，而这道题目是求字符串a能否组成字符串b，而不用管字符串b能不能组成字符串a。
代码
'''这个题目其实和那个异位词的差不多'''class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
record = [0]*26
#首先遍历magazine，将出现的字母在与a的相对位置上加一
for i in magazine:
record[ord(i)-ord('a')] += 1
#遍历ransomNote
for i in ransomNote:
#如果没有出现过，则一定返回false
if record[ord(i)-ord('a')] == 0:
return False
else:
record[ord(i)-ord('a')] -= 1return True
使用defaultdict
'''
这个题目其实和那个异位词的差不多，使用defaultdict()
'''class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
from collections import defaultdict
#记录每个字母出现的次数，key为字母，value为出现的次数
hashmap = defaultdict(int)
#出现一次就加一
for x in magazine:
hashmap[x] += 1for x in ransomNote:
#获取x出现的次数
val = hashmap.get(x)
#如果ran中的字母在mag中没有出现过，或者已经被用完了，false
if val is None or val ==0:
return False
#次数减一
else:
hashmap[x] -= 1return True
七、15. 三数之和
文章图片
题解 这道题我们采取双指针的方法，首先将数组排序（在做数组相关的题目中，如果没有思路，就先对数组进行排序），然后有一层for循环，i从下标为零的地方开始遍历，left=i+1，right在数组结束的位置上。
如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下标就应该向左移动，这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了，left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
代码 在代码中，有两个地方体现出了去重的操作，一定要举个例子自己手动实现一下，这样才可以更好的理解。在一开始时，我没有想到在第一个地方的去重，所以导致结果一直有个重复的。
'''
关于数组相关的题目，先考虑排序是否可以更好的处理
'''class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = [] #返回数组
nums = sorted(nums) #先排序for i in range(len(nums)):
if nums[i]>0:
return res
left = i+1
right = len(nums)-1
#去重
if i>0 and nums[i] == nums[i-1]:
continuetotal = 0
while left < right:
total = nums[i]+nums[left]+nums[right]
if total<0:
left += 1
elif total>0:
right -= 1
else:
res.append([nums[i],nums[left],nums[right]])
#去重
while left八、18. 四数之和
文章图片
题解 【leetcode算法|LeetCode——哈希表篇】这个题目和三数之和没有什么区别，只是在三数之和的基础上再多加一层循环，其实就类似于三指针。
代码
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
n = len(nums)
res = []
for i in range(n):
if i > 0 and nums[i] == nums[i - 1]: continue
for k in range(i+1, n):
if k > i + 1 and nums[k] == nums[k-1]: continue
p = k + 1
q = n - 1while p < q:
if nums[i] + nums[k] + nums[p] + nums[q] > target: q -= 1
elif nums[i] + nums[k] + nums[p] + nums[q] < target: p += 1
else:
res.append([nums[i], nums[k], nums[p], nums[q]])
while p < q and nums[p] == nums[p + 1]: p += 1
while p < q and nums[q] == nums[q - 1]: q -= 1
p += 1
q -= 1
return res
推荐阅读
- 晓飞的算法工程笔记|MicroNet: 低秩近似分解卷积以及超强激活函数，碾压MobileNet | 2020新文分析
- Nginx负载均衡中常见的算法及原理
- 玩转算法复杂度
- 看完微信抢红包算法你就明白，为啥你不是手气最佳
- 算法|一个组合加全排列的面试算法题及其解
- 数据结构与算法|「数据结构与算法Javascript描述」二叉树
- 算法|101道算法javaScript描述
- 老王和他的IT界朋友们|如果重来一次高考，我要好好学数学！
- #|语谱图（四） Mel spectrogram 梅尔语谱图