一周编程集训day1:Hash和数组
一周编程集训day1:Hash和数组
1 任务
数组:学习哈希表思想,并完成leetcode上的两数之和(1)及Happy Number(202)!(要求全部用哈希思想实现!)
2 概念介绍
哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。
哈希表的原理非常简单,通过一个固定的算法将Key转为一个数字,然后将该数字对数组长度取余,将取余结果作为数组下标,然后将Value存储在该数字为下标的数组里。
不过想要找到一个好的哈希表非常难。原因就是通过那个固定算法得出的数字有可能会相同。显然一个下标指向的数组空间里是没有办法存储两个元素的,只能通过一些其他方法来解决冲突。这些方法虽然能够解决冲突,但是会使得查询等操作的操作速度下降。所以一个好的哈希表这样的冲突应该是要很少的。
解决哈希冲突的常见方法有两种:(1)开放定址法 (2)拉链法
具有详情参加参考
3 leetcode
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
python解答思路:用哈希表反存索引,以原数组的value为dict的key。当 目标值-当前值 在dict中时,即按顺序返回索引。
class Solution:
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
keys = {}
for i in range(len(nums)):
if (target - nums[i]) in keys:
return[keys[target - nums[i]],i]
if nums[i] not in keys:
keys[nums[i]] = i
2. 202.快乐树
编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无限循环但始终变不到 1。如果可以变为 1,那么这个数就是快乐数。
示例:
输入: 19
输出: true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
python解答思路:两种结果,和为1:return True;进入循环且不含1:return False。 用哈希表存放出现过的数字,进入循环即当前数字在哈希表中。
class Solution:
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
loop_flag = False
num_dict = {}
while True:
num_dict[n] =True
sum = 0
while(n>0):
tmp = n%10
sum += tmp**2
n //= 10
if sum == 1:
return True
elif sum in num_dict:
return False
else:
n =sum