23.03.09 Today’s Leetcode

142. Linked List Cycle II (medium)

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        temp = set()
        cur = head
        while cur:
            if cur not in temp:
                temp.add(cur)
            else:
                return cur
            cur = cur.next
    
        return None

216. Combination Sum III (medium)

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        
        res = []

        def dfs(cur, his):
            # print(his)
            if len(his) == k:
                if sum(his) == n:
                    res.append(his[:])
                return
            if len(his) > k:
                return
            start = his[-1] + 1 if his else 1
            end = min(10, n - sum(his) + 1)
            for i in range(start, end):
                his.append(i)
                dfs(cur + i, his)
                his.pop()
        
        dfs(0, [])
        return res

237. Delete Node in a Linked List (medium)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def deleteNode(self, node: ListNode) -> None:
        node.val = node.next.val
        node.next = node.next.next

238. Product of Array Except Self (medium)

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        right, left = [], []
        temp = 1
        for num in nums:
            temp *= num
            left.append(temp)
        
        temp = 1
        for num in nums[::-1]:
            temp *= num
            right.append(temp)

        right = right[::-1]
        # print(left, right)

        n = len(nums)
        res = [0] * n
        for i in range(n):
            l = left[i - 1] if i - 1 >= 0 else 1
            r = right[i + 1] if i + 1 < n else 1
            res[i] = l * r
        return res

229. Majority Element II (medium)

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        target = math.floor(len(nums) / 3)
        counter = Counter(nums)
        res = []
        for key in counter.keys():
            if counter[key] > target:
                res.append(key)
        return res

228. Summary Ranges (easy)

class Solution:
    def summaryRanges(self, nums: List[int]) -> List[str]:
        i = 0
        n = len(nums)
        res = list()
        while i < n:
            j = i
            while j + 1 < n and nums[j + 1] - nums[j] == 1:
                j += 1
            
            temp = str(nums[i])
            if j > i:
                temp += '->'
                temp += str(nums[j])
            res.append(temp)
            i = j + 1
        return res

223. Rectangle Area (medium)

class Solution:
    def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int:

        def intersect(inv1, inv2):
            return min(inv1[1], inv2[1]) - max(inv1[0], inv2[0])

        a, b = intersect([ax1, ax2], [bx1, bx2]), intersect([ay1, ay2], [by1, by2])
        r = 0
        if a > 0 and b > 0:
            r = a * b
        return (ax2 - ax1) * (ay2 - ay1) + (bx2 - bx1) * (by2 - by1) - r