十. 哈希表
- 1.1 列表(list)
list是一種有序的集合，可以隨時(shí)添加和刪除其中的元素。
classmates = ['Michael', 'Bob', 'Tracy']
- 1.2 字典(dict)
dict在其他語(yǔ)言中也稱為map，使用鍵-值（key-value）存儲(chǔ)，具有極快的查找速度。
fruit={'apple':10, 'pears':5, 'bananas':20, 'orange':4}
- 1.3 集合(set)
set是一個(gè)無(wú)重復(fù)的數(shù)據(jù)集合。
s = set([1, 1, 2, 2, 3, 3])
# 等價(jià)于 s = {1, 2, 3}
-1.4 元組(tuple)
有序列表,tuple一旦初始化就不能修改。如果可能，能用tuple代替list就盡量用tuple,代碼更安全。
classmates = ('Michael', 'Bob', 'Tracy')
1. 兩數(shù)之和
題目：找到兩數(shù)之和為target，返回下標(biāo)
輸入：nums = [2,7,11,15], target = 9
輸出：[0,1] # 2+7=9
def twoSum(self, nums: List[int], target: int):
hashtable = dict()
for i, num in enumerate(nums):
if target - num in hashtable:
return [hashtable[target - num], i]
hashtable[nums[i]] = i # key: nums[i] -> value: i
return []
167. 兩數(shù)之和II-輸入有序數(shù)組
題目：找到兩數(shù)之和為target，返回下標(biāo)，輸入有序數(shù)組
輸入：nums = [2,7,11,15], target = 9
輸出：[1,2] # 2+7=9
思考：用1的解法即可，不過(guò)如果能用上有序這個(gè)條件，可以進(jìn)一步減少?gòu)?fù)雜度。
def twoSum(self, numbers: List[int], target: int) -> List[int]:
hashtable = dict()
for i, num in enumerate(numbers):
if target - num in hashtable:
return [hashtable[target - num], i+1]
hashtable[numbers[i]] = i+1
return []
20. 有效的括號(hào)
題目：有效的括號(hào)
輸入：s = "()[]{}"
輸出：true
def isValid(self, s: str) -> bool:
stack = []
p_map = {')':'(', ']':'[', '}':'{'}
for c in s:
if c not in p_map:
stack.append(c)
elif not stack or p_map[c] != stack.pop():
return False
return not stack
27. 移除元素
題目：給你一個(gè)數(shù)組 nums和一個(gè)值 val，你需要原地移除所有數(shù)值等于 val的元素，并返回移除后數(shù)組的新長(zhǎng)度。
輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2]
解釋：函數(shù)應(yīng)該返回新的長(zhǎng)度 2, 并且 nums 中的前兩個(gè)元素均為 2。
def removeElement(self, nums: List[int], val: int) -> int:
while(val in nums):
nums.pop(nums.index(val))
return len(nums)
169. 多數(shù)元素
題目：給定一個(gè)大小為 n 的數(shù)組，找到其中的多數(shù)元素。多數(shù)元素是指在數(shù)組中出現(xiàn)次數(shù) 大于 ? n/2 ? 的元素。
輸入：[2,2,1,1,1,2,2]
輸出：2
def majorityElement(self, nums: List[int]) -> int:
# create a set
d = dict()
for x in nums:
# 若不存在
if x in d.keys():
d[x] = d[x] + 1
else:
d[x] = 1
# find max value, then get key
max_value = -1
for x in d:
if d[x] > max_value:
max_value = d[x]
res = x
return res
217. 存在重復(fù)元素
題目：給定一個(gè)整數(shù)數(shù)組，判斷是否存在重復(fù)元素。如果存在一值在數(shù)組中出現(xiàn)至少兩次，函數(shù)返回 true 。如果數(shù)組中每個(gè)元素都不相同，則返回 false 。
輸入：[1,2,3,1]
輸出：true
def containsDuplicate(self, nums: List[int]) -> bool:
s = set() # 維護(hù)一個(gè)hash表即可
for i, x in enumerate(nums):
if x in s:
return True
else:
s.add(x)
return False
219. 存在重復(fù)元素 II
題目：給定一個(gè)整數(shù)數(shù)組和一個(gè)整數(shù) k，判斷數(shù)組中是否存在兩個(gè)不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的 絕對(duì)值 至多為 k。
輸入：nums = [1,2,3,1], k = 3
輸出：true
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
d = dict()
for idx, i in enumerate(nums):
if not i in d:
d[i] = idx # 如果沒(méi)有收錄，收錄它
elif abs(d[i] - idx)<=k:
return True # 如果存在重復(fù)且距離在k以內(nèi)，返回
else: d[i] = idx # 如果距離不滿足，更新標(biāo)記
return False
242. 有效的字母異位詞
題目：給定兩個(gè)字符串 s 和 t ，編寫一個(gè)函數(shù)來(lái)判斷 t 是否是 s 的字母異位詞。
輸入： s = "anagram", t = "nagaram"
輸出：true
def isAnagram(self, s: str, t: str) -> bool:
dic1, dic2 = {}, {}
for item in s: # 需要dict1和dict2互相檢查
dic1[item] = dic1.get(item, 0)+1
for item in t:
dic2[item] = dic2.get(item, 0)+1
return dic1 == dic2
290. 單詞規(guī)律
題目：給定一種規(guī)律 pattern 和一個(gè)字符串 str ，判斷 str 是否遵循相同的規(guī)律。
輸入：pattern = "abba", str = "dog cat cat dog"
輸出：true
思考：這是242的進(jìn)化版本。
def wordPattern(self, pattern: str, s: str) -> bool:
s = s.split()
if len(s) != len(pattern):
return False
dp = dict()
ds = dict()
for i in range(0, len(pattern)):
if pattern[i] in dp:
if s[i] != dp[pattern[i]]:
return False
elif s[i] in ds:
if pattern[i] != ds[s[i]]:
return False
else:
dp[pattern[i]] = s[i]
ds[s[i]] = pattern[i]
return True
13. 羅馬數(shù)字轉(zhuǎn)整數(shù)
題目：羅馬數(shù)字轉(zhuǎn)整數(shù)
class Solution:
SYMBOL_VALUES = {
'I': 1,
'V': 5,
'X': 10,
'L': 50,
'C': 100,
'D': 500,
'M': 1000,
}
def romanToInt(self, s: str) -> int:
ans = 0
n = len(s)
for i, ch in enumerate(s):
value = Solution.SYMBOL_VALUES[ch] # 當(dāng)前值
if i < n - 1 and value < Solution.SYMBOL_VALUES[s[i + 1]]:
ans -= value # 左減
else:
ans += value # 右加
return ans
168. Excel表列名稱
題目：給你一個(gè)整數(shù) columnNumber ，返回它在 Excel 表中相對(duì)應(yīng)的列名稱。
def convertToTitle(self, columnNumber: int) -> str:
ans = list()
while columnNumber > 0:
a0 = (columnNumber - 1) % 26 + 1
ans.append(chr(a0 - 1 + ord("A")))
columnNumber = (columnNumber - a0) // 26
return "".join(ans[::-1])
171. Excel 表列序號(hào)
題目：給你一個(gè)字符串 columnTitle ，表示 Excel 表格中的列名稱。返回該列名稱對(duì)應(yīng)的列序號(hào)。
def titleToNumber(self, columnTitle: str) -> int:
number, multiple = 0, 1
for i in range(len(columnTitle) - 1, -1, -1):
k = ord(columnTitle[i]) - ord("A") + 1
number += k * multiple
multiple *= 26
return number
