从零开始的力扣(第二十天)~
PS.才发现leetcode有些题只有会员才能做了,难道要弃扣从牛了吗?
1.设计哈希集合
不使用任何内建的哈希表库设计一个哈希集合,具体地说,你的设计应该包含以下的功能
add(value):向哈希集合中插入一个值。 contains(value) :返回哈希集合中是否存在这个值。 remove(value):将给定值从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。
示例: MyHashSet hashSet = new MyHashSet(); hashSet.add(1); hashSet.add(2); hashSet.contains(1); // 返回 true hashSet.contains(3); // 返回 false (未找到) hashSet.add(2); hashSet.contains(2); // 返回 true hashSet.remove(2); hashSet.contains(2); // 返回 false (已经被删除)
注意: 所有的值都在 [1, 1000000]的范围内。 操作的总数目在[1, 10000]范围内。 不要使用内建的哈希集合库。 —————————————————————————————————————————
具体来说,设计哈希集合,将每个要存入的数值通过计算分入结果相同的桶内,在寻找时再通过计算在相应的桶内寻找是否有这个数值,这些桶的集合就是哈希集合
class MyHashSet(object):
def __init__(self
):
"""
Initialize your data structure here.
"""
self
.bucket
= 1000
self
.itemperbucket
= 1000000 // self
.bucket
+ 1
self
.hash = [[] for _
in range(self
.bucket
)]
def add(self
, key
):
"""
:type key: int
:rtype: None
"""
if not self
.hash[key
%self
.bucket
]:
self
.hash[key
%self
.bucket
] = [0] * self
.itemperbycket
self
.hash[key
%self
.bucket
][key
//self
.bucket
] = 1
def remove(self
, key
):
"""
:type key: int
:rtype: None
"""
if self
.hash[key
%self
.bucket
]:
self
.hash[key
%self
.bucket
][key
//self
.bucket
] = 0
def contains(self
, key
):
"""
Returns true if this set contains the specified element
:type key: int
:rtype: bool
"""
return (self
.hash[key
%self
.bucket
] != []) and (self
.hash[key
%self
.bucket
][key
//self
.bucket
] == 1)
2.设计哈希映射
不使用任何内建的哈希表库设计一个哈希映射,具体地说,你的设计应该包含以下的功能
put(key, value):向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在,更新这个值。 get(key):返回给定的键所对应的值,如果映射中不包含这个键,返回-1。 remove(key):如果映射中存在这个键,删除这个数值对。
示例: MyHashMap hashMap = new MyHashMap(); hashMap.put(1, 1); hashMap.put(2, 2); hashMap.get(1); // 返回 1 hashMap.get(3); // 返回 -1 (未找到) hashMap.put(2, 1); // 更新已有的值 hashMap.get(2); // 返回 1 hashMap.remove(2); // 删除键为2的数据 hashMap.get(2); // 返回 -1 (未找到)
注意: 所有的值都在 [1, 1000000]的范围内。 操作的总数目在[1, 10000]范围内。 不要使用内建的哈希库。 —————————————————————————————————————————
与上题大致相同,只是这次需要保存键值,将原来的0转换为键值就可以了
class MyHashMap(object):
def __init__(self
):
"""
Initialize your data structure here.
"""
self
.bucket
= 1000
self
.itemperbucket
= 1000000 // self
.bucket
+ 1
self
.hash = [[] for _
in range(self
.bucket
)]
def put(self
, key
, value
):
"""
value will always be non-negative.
:type key: int
:type value: int
:rtype: None
"""
if not self
.hash[key
%self
.bucket
]:
self
.hash[key
%self
.bucket
] = [0] * self
.itemperbucket
if value
== 0:
self
.hash[key
%self
.bucket
][key
//self
.bucket
] = '0'
else:
self
.hash[key
%self
.bucket
][key
//self
.bucket
] = value
def get(self
, key
):
"""
Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key
:type key: int
:rtype: int
"""
if not self
.hash[key
%self
.bucket
]:
return -1
if self
.hash[key
%self
.bucket
][key
//self
.bucket
] != 0:
return int(self
.hash[key
%self
.bucket
][key
//self
.bucket
])
return -1
def remove(self
, key
):
"""
Removes the mapping of the specified value key if this map contains a mapping for the key
:type key: int
:rtype: None
"""
if not self
.hash[key
%self
.bucket
]:
return
if self
.hash[key
%self
.bucket
][key
//self
.bucket
] != 0:
self
.hash[key
%self
.bucket
][key
//self
.bucket
] = 0
3.两个数组的交集
给定两个数组,编写一个函数来计算它们的交集。
示例 1: 输入: nums1 = [1,2,2,1], nums2 = [2,2] 输出: [2]
示例 2: 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出: [9,4]
说明: 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。 —————————————————————————————————————————
先去重,再判断
class Solution(object):
def intersection(self
, nums1
, nums2
):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: List[int]
"""
ans
= []
nums1
= set(nums1
)
nums2
= set(nums2
)
for i
in nums1
:
if i
in nums2
:
ans
.append
(i
)
return ans
4.快乐数
编写一个算法来判断一个数是不是“快乐数”。
一个“快乐数”定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是无限循环但始终变不到 1。如果可以变为 1,那么这个数就是快乐数。
示例: 输入: 19 输出: true
解释: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1 —————————————————————————————————————————
最初的想法是输入的数一共有几位,那么最后只需要考虑(10*位数)种情况,那么只需要20次循环就能判定快乐数
class Solution(object):
def isHappy(self
, n
):
"""
:type n: int
:rtype: bool
"""
i
= 0
while i
< 20:
if n
== 1:
return True
n
= sum(int(i
) ** 2 for i
in str(n
))
i
+= 1
return False
大神的解法:不是快乐数的数称为不快乐数(unhappy number),所有不快乐数的数位平方和计算,最後都会进入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循环中
class Solution(object):
def isHappy(self
, n
):
"""
:type n: int
:rtype: bool
"""
while n
:
if n
in [4, 16, 37, 58, 89, 145, 42, 20]:
return False
if n
== 1:
return True
n
= sum(int(i
) ** 2 for i
in str(n
))
以上就是今日经验!