哈希表理論基礎(chǔ)
- 當(dāng)我們遇到了要快速判斷一個(gè)元素是否出現(xiàn)集合里的時(shí)候仿村，就要考慮哈希法。
242. 有效的字母異位詞 - 力扣（LeetCode）
解題思路
- 用一個(gè)哈希表缩抡，先記錄s中字母出現(xiàn)次數(shù)奠宜，然后如果t中出現(xiàn)一樣字母就-1包颁，最后如果哈希表中存在非0值瞻想，則返回false；
- 也可以直接調(diào)用函數(shù)
方法一
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
hashtable = {}
for i in s:
if i in hashtable:
hashtable[i] += 1
else:
hashtable[i] = 1
for i in t:
if i in hashtable:
hashtable[i] -= 1
for i in hashtable:
if hashtable[i] != 0:
return False
return True
方法二
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
from collections import Counter
s = Counter(s)
t = Counter(t)
return s==t
349. 兩個(gè)數(shù)組的交集 - 力扣（LeetCode）
直接用set
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
return list(set(nums1) & set(nums2))
- 還是沒明白什么時(shí)候用數(shù)組娩嚼，什么時(shí)候用set：如果范圍可控蘑险、數(shù)字不大，可用數(shù)組
- "如果哈希值比較少岳悟、特別分散佃迄、跨度非常大，使用數(shù)組就造成空間的極大浪費(fèi)贵少！" ???
202. 快樂數(shù) - 力扣（LeetCode）
class Solution(object):
def isHappy(self, n):
"""
:type n: int
:rtype: bool
"""
hashtable = {}
while True:
n_temp = 0
for ch in str(n):
n_temp += int(ch)**2
n = n_temp
if n == 1:
return True
if n in hashtable:
return False
else:
hashtable[n] = 0
- 用set呵俏、hashtable都行
1. 兩數(shù)之和 - 力扣（LeetCode）
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
hashtable = {}
for index, value in enumerate(nums):
if target-value in hashtable:
return [hashtable[target-value], index]
else:
hashtable[value] = index
- 還可以深挖，埋個(gè)坑
