iT邦幫忙

2022 iThome 鐵人賽

DAY 22
0
自我挑戰組

leetcode 30天 不中斷解題挑戰系列 第 22

Day22 leetcode隨機挑題 (Design、Matrix、Search)

  • 分享至 

  • xImage
  •  

首先是 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

以上為今天的練習感謝大家


上一篇
Day21 leetcode 隨機挑題 (Tree、Math、Matrix)
下一篇
Day23 leetcode隨機挑題 (Matrix、Math)沒錯周五就是要偷懶
系列文
leetcode 30天 不中斷解題挑戰30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言