23.05.29 Today’s Leetcode

1603. Design Parking System (easy)

class ParkingSystem:

    def __init__(self, big: int, medium: int, small: int):
        self.capacity = [big, medium, small]
        self.cur = [0, 0, 0]

    def addCar(self, carType: int) -> bool:
        if self.cur[carType - 1] >= self.capacity[carType - 1]:
            return False
        self.cur[carType - 1] += 1
        return True

375. Guess Number Higher or Lower II (medium)

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        @lru_cache(None)
        def dp(l, r):
            if l >= r:
                return 0       
            res = float('inf')     
            for i in range(l, r):
                res = min(res, max(dp(l, i - 1), dp(i + 1, r)) + i)
            return res
        return dp(1, n)375. Guess Number Higher or Lower II

377. Combination Sum IV (medium)

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        d = set(nums)

        @lru_cache(None)
        def combSum(tar):
            if tar == 0:
                return 1
            if tar < 0:
                return 0
            
            res = 0
            for num in d:
                res += combSum(tar - num)
            return res
        
        return combSum(target)

##

Sliding Window : Failed

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        i = j = 0
        m, n = len(nums1), len(nums2)
        res = []
        while i < m and j < n:
            a, b = nums1[i], nums2[j]
            c = nums1[i + 1] if (i + 1 < m) else math.inf 
            d = nums2[j + 1] if (j + 1 < n)  else math.inf
            if c < d:
                i += 1
                j = 0
            else:
                j += 1
                i = 0
            res.append([a, b])
            if len(res) >= k:
                break
        
        # print(res)
        return res

Priority Queue

import heapq
class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int):
        heap = []
        heapq.heappush(heap, (nums1[0] + nums2[0], 0, 0))
        visited = set()
        visited.add((0,0))
        output = []
        while len(output) < k and heap:
            val = heapq.heappop(heap)
            output.append([nums1[val[1]], nums2[val[2]]])
            if val[1] + 1 < len(nums1) and (val[1] + 1, val[2]) not in visited:
                heapq.heappush(heap, (nums1[val[1] + 1] + nums2[val[2]], val[1] + 1, val[2]))
                visited.add((val[1] + 1, val[2]))
            if val[2] + 1 < len(nums2) and (val[1], val[2] + 1) not in visited:
                heapq.heappush(heap, (nums1[val[1]] + nums2[val[2] + 1], val[1], val[2] + 1))
                visited.add((val[1], val[2] + 1))
        return output