23.03.12 Today’s Leetcode

23. Merge k Sorted Lists (hard)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        q = []
        for head in lists:
            cur = head
            while cur:
                heappush(q, cur.val)
                cur = cur.next
            
        res = ListNode(0)
        cur = res
        while q:
            target = heappop(q)
            cur.next = ListNode(target)
            cur = cur.next

        return res.next

220. Contains Duplicate III (hard)

class Solution:
    def containsNearbyAlmostDuplicate(self, nums, indexDiff, valueDiff):
        if valueDiff < 0: return False
        n = len(nums)
        d = {}
        w = valueDiff + 1
        for i in range(n):
            m = nums[i] // w
            if m in d:
                return True
            if m - 1 in d and abs(nums[i] - d[m - 1]) < w:
                return True
            if m + 1 in d and abs(nums[i] - d[m + 1]) < w:
                return True
            d[m] = nums[i]
            if i >= indexDiff: del d[nums[i - indexDiff] // w]
        return False

213. House Robber II (medium)

Approach to DP Problems link

class Solution(object):
    def rob(self, nums):
        def simple_rob(nums):
            rob, not_rob = 0, 0
            for num in nums:
                rob, not_rob = not_rob + num, max(rob, not_rob)
            return max(rob, not_rob)
        
        if not nums:
            return 0
        elif len(nums) == 1:
            return nums[0]
        else:
            return max(simple_rob(nums[1:]), simple_rob(nums[:-1]))