|
其实哈希表在python中实现就是字典。
1.给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）
解释：每次将tsrget的值与数组中的每个值求差值，然后在hash中找插值是否存在，若不在就存入，若在就提取下标。
class Solution:
def twoSum(self , numbers: List[int], target: int) -> List[int]: #number = [20,70,110,150], target = 90
res = []
#创建哈希表,两元组分别表示值、下标
hash = dict()
#在哈希表中查找target-numbers[i]
for i in range(len(numbers)) : #遍历数组 i=0,i=1
temp = target - numbers[i] # temp = 70, temp = 20
#若是没找到，将此信息计入哈希表
if temp not in hash: #hash为空 , temp的值在hash中
hash[numbers[i]] = i # hash = {20:0}
else:
#哈希表中记录的是之前的数字，所以该索引比当前小
res.append(hash[temp] + 1) #把之间存入hash中的下标值提取加1，res = [1]
res.append(i + 1) #把现在的索引提取出来2,res = [1,2]
break
return res #res= [1,2]
2.给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。保证数组输入非空，且保证有解
解释：遍历整个数组，将每个数值写入哈希表中，然后次数为1，若数值在表中，则次数加1，在判断是否为长度的一半。若数值不在表中，则重新写入。
class Solution:
def MoreThanHalfNum_Solution(self , numbers: List[int]) -> int: #numbers = [1, 2, 3, 2, 2, 2, 5, 4, 2]
#无序哈希表统计每个数字出现的次数
mp = dict() #空
#遍历数组
for i in range(len(numbers)): #i= 0,1,2,3,4,5,6,7,8
if numbers[i] in mp: #false,false,false,true,true,true,false,false,true
#哈希表中相应数字个数加1
mp[numbers[i]] += 1 #{1:1,2:2,3:1},{1:1,2:3,3:1},{1:1,2:4,3:1},{1:1,2:5,3:1,5:1,4:1}
else:
mp[numbers[i]] = 1 #mp = {1:1},{1:1,2:1},{1:1,2:1,3:1},{1:1,2:4,3:1,5:1},{1:1,2:4,3:1,5:1,4:1}
#一旦有个数大于长度一半的情况即可返回
if mp[numbers[i]] > (int)(len(numbers) / 2): #false,false,false,false,false,false,false,false,true
return numbers[i] #2
return 0
3.一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。提示：输出时按非降序排列。
解释：遍历两次数组，第一次记录每个数字出现的次数，第二次查看hash中的次数，是否为1，若为1则取该值出来，最后利用sort进行升序处理。
class Solution:
def FindNumsAppearOnce(self , array: List[int]) -> List[int]: #array = [1,2,3,3,2,9]
mp = dict()
res = list()
#遍历数组
for i in range(len(array)): #0,1,2,3,4,5
#统计每个数出现的频率
if array[i] in mp:#false,false,false,true,true,false
mp[array[i]] += 1 #{1:1,2:1,3:2},{1:1,2:2,3:2}
else:
mp[array[i]] = 1 #mp={1:1},{1:1,2:1},{1:1,2:1,3:1},{1:1,2:2,3:2,9:1}
#再次遍历数组
for i in range(len(array)): #i=0,1,2,3,4,5
#找到频率为1的两个数
if mp[array[i]] == 1: #true,false,false,false,false,true
res.append(array[i]) #res=[1],[1,9]
#整理次序
res.sort(reverse=False) #在将res升序排列
return res
4.给定一个未排序的整数数组nums，请你找出其中没有出现的最小的正整数。
解释：第一步遍历整个数组，统计每个数字出现的次数存入hash，防止重复浪费资源。遍历hash，从最小正整数1开始，依次递增，看是否在hsah，若在就+1，若不在就返回该最小正整数。
class Solution:
def minNumberDisappeared(self , nums: List[int]) -> int: #nums = [1,0,2]
n = len(nums) #3
mp = dict()
#哈希表记录数组中出现的每个数字
for i in range(n): #0,1,2
if nums[i] in mp: #false,false,false
mp[nums[i]] += 1
else:
mp[nums[i]] = 1 #mp = {1:1},{1:1,0:1},{1:1,0:1,2:1}
res = 1
#从1开始找到哈希表中第一个没有出现的正整数
while res in mp: #true,true,false
res += 1 #2,3
return res #3
5.给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。三元组（a、b、c）中的元素可以按任意顺序排列。解集中不能包含重复的三元组。
解释：1.排序，这一步非常的关键，就是如果我们先选左一数为负target，找其他俩数的和等于target。若最左二加最右一大于target，则从右往左。若最左二加最右一小于target，则从左往右。（因为其他就不可能了，好好理解这个排序）
?2.就是去重复，target的重复，可以在前面遍历的时候去除。后面二者和的重复值，左边就再往左推一个，右边就再往右推一个，看是否相等。
3.双指针，在python里面很简单，就是遍历数组的下标。（理解如何遍历就可以）
class Solution:
def threeSum(self , num: List[int]) -> List[List[int]]:
res = list(list())
n = len(num)
#不够三元组
if n < 3:
return res
#排序
num.sort()
for i in range(n - 2):
if i != 0 and num[i] == num[i - 1]:
continue
#后续的收尾双指针
left = i + 1
right = n - 1
#设置当前数的负值为目标
target = -num[i]
while left < right:
#双指针指向的二值相加为目标，则可以与num[i]组成0
if num[left] + num[right] == target:
res.append([num[i], num[left], num[right]])
while left + 1 < right and num[left] == num[left + 1]:
#去重
left += 1
while right - 1 > left and num[right] == num[right - 1]:
#去重
right -= 1
#双指针向中间收缩
left += 1
right -= 1
#双指针指向的二值相加大于目标，右指针向左
elif num[left] + num[right] > target:
right -= 1
#双指针指向的二值相加小于目标，左指针向右
else:
left += 1
return res
其中有些不理解的可以发邮箱hanbinbin0624@163.com，可以交流。
|