Documenting LeetCode solving.

Q120

494. Target Sum

Medium. DP

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        dp = {} # (index, total) -> number of ways

        def backtrack(i, total):
            if i == len(nums):
                return 1 if total == target else 0
            if (i, total) in dp:
                return dp[(i, total)]
            # Number of ways to build the expression when index == i,
            # total == total
            dp[(i, total)] = (backtrack(i + 1, total + nums[i]) +
                              backtrack(i + 1, total - nums[i]))

            return dp[(i, total)]

        return backtrack(0, 0)

R22

150. Evaluate Reverse Polish Notation

Medium. Stack

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []

        for c in tokens:
            if c == '+':
                stack.append(stack.pop() + stack.pop())
            elif c == '-':
                b, a = stack.pop(), stack.pop()
                stack.append(a - b)
            elif c == '*':
                stack.append(stack.pop() * stack.pop())
            elif c == '/':
                b, a = stack.pop(), stack.pop()
                stack.append(int(a / b))
            else:
                stack.append(int(c))

        return stack[0]