Re: [閒聊] 每日leetcode

看板Marginalman作者dont (dont)時間1年前 (2024/08/16 00:08)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串719/1548 (看更多)

860. Lemonade Change ## 思路就照題目模擬, 5元直接收下, 10元找5元, 20元找15元 ## Code ```python class Solution: def lemonadeChange(self, bills: List[int]) -> bool: coin = [0, 0] for bill in bills: if bill == 5: coin[0] += 1 elif bill == 10: if coin[0]: coin[0] -= 1 else: return False coin[1] += 1 else: if coin[1] and coin[0]: coin[0] -= 1 coin[1] -= 1 elif coin[0] > 2: coin[0] -= 3 else: return False return True ``` --- 407. Trapping Rain Water II ## 思路計算並加總每個cell的水量 cell的水量會是包圍住cell的邊界最大值跟該cell的高度差 ex. 33333 21112 21012 21112 22222 <-- 裡面0的水量會是(2-0) 從外圍開始往內計算把邊界都加到heap 每次pop再把鄰居加進heap, 如果鄰居比當前最大高度低, 就表示該cell的會有curr_max - height的水量 ## Code ```python class Solution: def trapRainWater(self, heightMap: List[List[int]]) -> int: len_r, len_c = len(heightMap), len(heightMap[0]) if len_r < 3 or len_c < 3: return 0 heap = [] # (height, r, c) for r in range(len_r): heapq.heappush(heap, (heightMap[r][0], r, 0)) heapq.heappush(heap, (heightMap[r][-1], r, len_c-1)) heightMap[r][0] = heightMap[r][-1] = -1 for c in range(len_c): heapq.heappush(heap, (heightMap[0][c], 0, c)) heapq.heappush(heap, (heightMap[-1][c], len_r-1, c)) heightMap[0][c] = heightMap[-1][c] = -1 curr_max = ans = 0 while heap: height, r, c = heapq.heappop(heap) curr_max = max(curr_max, height) for nr, nc in (r+1, c), (r-1, c), (r, c+1), (r, c-1): if 0 <= nr < len_r and 0 <= nc < len_c and heightMap[nr][nc] != -1: if heightMap[nr][nc] < curr_max: ans += (curr_max - heightMap[nr][nc]) heapq.heappush(heap, (heightMap[nr][nc], nr, nc)) heightMap[nr][nc] = -1 return ans ``` -- http://i.imgur.com/OLvBn3b.jpg