23.01.20 Today’s Leetcode

491. Non-decreasing Subsequences (medium)

중복되는 subsequences 들을 어떻게 처리할지가 관건인 문제이다. 그냥 not in 을 이용한 풀이는 가까스로 테스트케이스를 통과했다.

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)
        def dfs(index, current):
            nonlocal n, nums, res
            if len(current) > 1 and current not in res:
                res.append(current)
            if index >= n:
                return
            for i in range(index, n):
                if nums[i] >= current[-1]:
                    temp = current[:]
                    temp.append(nums[i])
                    dfs(i + 1, temp)
        for index, num in enumerate(nums):
            dfs(index + 1, [num])
        return res

backtracking을 이용한 풀이는 그보다 몇배는 빠르게 통과했다.

class Solution:
    def findSubsequences(self, nums: List[int]) -> List[List[int]]:
        results = []
        path = []
        def backtracking(nums,startIndex):
            if len(path) > 1:
                results.append(path[:])
            for i in range(startIndex,len(nums)):
                if path and path[-1] > nums[i]:
                    continue
                # 이 부분이 핵심이다. 이미 했던 number라면 continue 하는 것.
                if i > startIndex and nums[i] in nums[startIndex:i]:
                    continue
                path.append(nums[i])
                backtracking(nums,i+1)
                path.pop()
        backtracking(nums,0)
        return results

101. Symmetric Tree (easy)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def dfs(left, right):
            if left == None and right == None:
                return False
            elif left == None:
                return True
            elif right == None:
                return True

            res = (left.val != right.val)
            res |= dfs(left.left, right.right)
            res |= dfs(left.right, right.left)
            return res

        return not dfs(root.left, root.right)