首先是 981. Time Based Key-Value Store (medium)
https://leetcode.com/problems/time-based-key-value-store/
題目滿麻煩的,直接G翻
設計一個基於時間的鍵值數據結構,可以為同一個鍵存儲不同時間戳的多個值,並在某個時間戳檢索該鍵的值。
實現TimeMap類:
TimeMap()初始化數據結構的對象。
void set(String key, String value, int timestamp)在給定時間存儲key帶有值的鍵。value timestamp
String get(String key, int timestamp)返回一個set以前調用過的值,使用timestamp_prev <= timestamp. 如果有多個這樣的值,它會返回與最大關聯的值timestamp_prev。如果沒有值,則返回"".
除此之外他有一個沒寫在題目敘述的重點,他寫在下面的地方,沒看到真的會被坑
「timestamp」嚴格遞增
class TimeMap:
def __init__(self):
self.d = defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.d[key].append([timestamp,value])
def get(self, key: str, timestamp: int) -> str:
temp = self.d[key]
L,R = 0,len(temp)-1
if temp == [] or temp[L][0]>timestamp:
return ""
if temp[R][0]<=timestamp:
return temp[R][1]
while L<R:
# print(L,R)
mid = (L+R)//2
if temp[mid][0] == timestamp:
return temp[mid][1]
elif temp[mid][0] > timestamp:
L = mid+1
else:
R = mid
return temp[L][1]
# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)
再來是 766. Toeplitz Matrix (easy)
https://leetcode.com/problems/toeplitz-matrix/
給一個矩陣,檢查左上至右下的元素是否都相同
想法1:
兩次for迴圈,一次檢查第一列、一次檢查第一行
class Solution:
#左上到右下同個元素
def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
L,W = len(matrix),len(matrix[0])
for i in range(L):
x,y = 0+i,0
temp = matrix[x][y]
while x<L and y<W:
if temp !=matrix[x][y]:
return 0
x+=1
y+=1
for i in range(W):
x,y = 0,0+i
temp = matrix[x][y]
while x<L and y<W:
if temp !=matrix[x][y]:
return 0
x+=1
y+=1
return 1
想法2:
每一列元素(除了第0個)必等於上一列元素(除了最後一個)
因此只需一次迴圈,檢查上下列元素是否相等即可
class Solution:
def isToeplitzMatrix(self, matrix: List[List[int]]) -> bool:
temp = matrix[0][:-1]#複製第0列
for i in matrix[1:]:#矩陣第1列之後
if i[1:] != temp:#上一列(扣掉最後一個元素)會等於下一列(扣掉第一個元素)
return False
else:
temp = i[:-1]#刪掉最後一個元素
return True
再來是 350. Intersection of Two Arrays II (easy)
https://leetcode.com/problems/intersection-of-two-arrays-ii/
找出共同擁有的元素,包含個數也要計算
想法1:
1.利用Counter計算nums1各個元素的數量
2.看要迭代nums1的Counter還是nums,個人覺得迭代nums2比較方便
3.每檢查到nums2有該元素,即刪除在nums1的Counter所統計的數量即可
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
n1C = Counter(nums1)
ans = []
for i in n1C:
if i in nums2:
ans += min(n1C[i],nums2.count(i)) * [i]
return ans
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
n1C= Counter(nums1)
ans = []
for i in nums2:
if n1C[i]>0:
ans.append(i)
n1C[i]-=1
return ans
想法2:
既然都用Counter了,那為什麼不直接交集後選出所有elements就好呢?
class Solution:
def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
n1C = Counter(nums1)
n2C = Counter(nums2)
ans = (n1C & n2C).elements()
return ans
以上為今天的練習感謝大家