Media is too big
VIEW IN TELEGRAM
#leetcode簽到
2070. Most Beautiful Item for Each Query

找最大 => heap
每次重新長heap 太慢？
把queries也sort 然後建dict 去映射回原本的queries 大偷懶

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        items.sort(key=lambda x:x[0])
        ans=[]
        h=[]
        ind=0
        d=defaultdict(int)
        for i in sorted(queries):
            while ind<len(items) and items[ind][0]<=i :
                heapq.heappush(h,-items[ind][1])
                ind+=1
            if h:
                d[i]=-h[0]     
            
        for i in queries:
            ans.append(d[i])        
        return ans
leetcode簽到
#leetcode簽到
Day 7
264. Ugly Number II
一開始是沒想法的 討論區的很直觀
minheap 彈出來 *2 *3 *5 就是新的ugly number
塞回去繼續做一樣的事情 + dedup就可以了
class Solution:
    def nthUglyNumber(self, n: int) -> int:
        heap=[1]
        cnt=1
        mem={1}
        multi=[2,3,5]
        while cnt<n:
            
            k=heapq.heappop(heap)
            cnt+=1
            for i in multi:
                a=k*i
                if a not in mem:
                    heapq.heappush(heap,a)
                    mem.add(a)
        return heap[0]
leetcode簽到
#leetcode簽到
Day 6
1937. Maximum Number of Points with Cost
留一個位置 recursion dp + cache TLE
leetcode簽到
#leetcode簽到
Day 5
624. Maximum Distance in Arrays

給多個升序排序好的陣列
找不同陣列間最大的距離 距離定義為 |a-b|

一開始搞了一個n^2解 TLE
後面就偷看discussion
class Solution:
    def maxDistance(self, arrays: List[List[int]]) -> int:
        f_min, f_max = arrays[0][0], arrays[0][-1]
        diff = 0
        for i in range(1, len(arrays)):
            diff = max(max(f_max - arrays[i][0], arrays[i][-1] - f_min), diff)

            f_min = min(f_min, arrays[i][0])
            f_max = max(f_max, arrays[i][-1])

        return diff
leetcode簽到
#leetcode簽到
Day 4
860. Lemonade Change
恩 Easy
會有人來買檸檬水 檸檬水5元 客人會帶 5 10 20元來買
你要看手上收到的錢可不可以找給所有客人
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        d = {5: 0, 10: 0, 20: 0}

        for i in bills:
            if i == 5:
                d[i] += 1
            if i == 10:
                if d[5] > 0:
                    d[5] -= 1
                    d[i] += 1
                else:
                    return False
            if i == 20:
                if d[10] > 0 and d[5] > 0:
                    d[10] -= 1
                    d[5] -= 1
                    d[i] += 1
                elif d[5] > 2:
                    d[5] -= 3
                    d[i] += 1
                else: return False
        return True
leetcode簽到
#leetcode簽到
Day 3
719. Find K-th Smallest Pair Distance
我一開始把距離全取
然後塞進heap TLE...
我以為我很快(X
後來還是偷看答案了
要sort之後走二分搜尋法
2分搜的對象是距離
所以要多生一個新的function去算現在的範圍 (<mid)的 有沒有k個 如果有 mid就是第k個
class Solution:
    def smallestDistancePair(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        low, high = 0, nums[-1] - nums[0]

        def count_p(m_d):
            cnt, j = 0, 0
            for i in range(n):
                while j < n and nums[j] - nums[i] <= m_d:
                    j += 1
                cnt += j - i - 1
            return cnt

        while low < high:
            mid = (low + high) // 2
            if count_p(mid) < k:
                low = mid + 1
            else:
                high = mid
        return low
leetcode簽到
小八汪汪的MurMur
#leetcode簽到 Day 2 40. Combination Sum II 問題 : 怎麼組合可以sum==target (回傳數列不能有重複組合) 一開始寫了DP 發現不會全組合XD 後來改成用for append+pop(backtracking) 但是也沒有dedup 最後還是偷看人家的 class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:…
補一兩句好了
a=list()
a[:]
a.copy()

都可以做拷貝
#leetcode簽到
Day 2

40. Combination Sum II

問題 : 怎麼組合可以sum==target (回傳數列不能有重複組合)

一開始寫了DP
發現不會全組合XD 後來改成用for append+pop(backtracking)
但是也沒有dedup
最後還是偷看人家的
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        candidates.sort()

        def dp(i, now,target):


            if target == 0:
                res.append(now[:])
                return
            if target < 0:
                return

            for t in range(i, len(candidates)):
                if t > i and candidates[t] == candidates[t - 1]:
                    continue

                now.append(candidates[t])
                dp(t + 1, now, target - candidates[t])
                now.pop()

        dp(0,[],target)
        return res
leetcode簽到
尚可
有點少
變色龍超暖
Before
After
Back to Top