23.07.17 Today’s Leetcode

445. Add Two Numbers II (medium)

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        def to_list(node):
            arr = []
            while node:
                arr.append(node.val)
                node = node.next
            return arr

        a, b = to_list(l1)[::-1], to_list(l2)[::-1]
        n1, n2 = len(a), len(b)
        # print(a, b)
        
        p = 0

        arr = []
        for i in range(max(n1, n2)):
            x = a[i] if i < n1 else 0
            y = b[i] if i < n2 else 0
            num = (x + y + p) % 10
            p = (x + y + p) // 10
            arr.append(num)
        
        if p > 0:
            arr.append(p)

        res = ListNode(0)
        cur = res
        for num in arr[::-1]:
            cur.next = ListNode(num)
            cur = cur.next

        return res.next

with Stack

class Solution:
    def helper(self, l1: ListNode, l2: ListNode) -> ListNode:
        stack1 = []
        stack2 = []

        while l1:
            stack1.append(l1.val)
            l1 = l1.next

        while l2:
            stack2.append(l2.val)
            l2 = l2.next

        result = None
        carry = 0

        while stack1 or stack2 or carry:
            digit1 = stack1.pop() if stack1 else 0
            digit2 = stack2.pop() if stack2 else 0

            total = digit1 + digit2 + carry
            digit = total % 10
            carry = total // 10

            newNode = ListNode(digit)
            newNode.next = result
            result = newNode

        return result

    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        ans = self.helper(l1, l2)
        return ans

446. Arithmetic Slices II - Subsequence (hard)

DFS

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        
        n = len(nums)
        count = 0

        def dfs(index, size, diff):
            nonlocal count
            if size >= 3:
                count += 1
            if index >= n:
                return

            for i in range(index + 1, n):
                d = nums[i] - nums[index]
                if diff < 0:
                    dfs(i, size + 1, d)
                elif d == diff:
                    dfs(i, size + 1, diff)

        for i in range(n):
            dfs(i, 1, -1)

        return count

DP

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        res = 0
        dp = [defaultdict(int) for i in range(len(nums))]
		
        for i in range(1, len(nums)):
            for j in range(i):
                dif = nums[i] - nums[j]
                dp[i][dif] += 1
                if dif in dp[j]:
                    dp[i][dif] += dp[j][dif]
                    res += dp[j][dif]
        return res