Month: December 2018

Link: https://leetcode.com/problems/flip-equivalent-binary-trees/ 

Thought

If 2 nodes are equivalent, either their left and right side match, or they are flipped match. So using a recursion(why recursion? It is a Tree!), and try to match each node pairs from root1 and root2.

For each recursion level, I will first compare if current node pair have the same value. (I can return False immediately if not match). If it matches, there are 3 cases:

1. They are identical -> recursion with (root1.left, root2.left,) and  (root1.right, root2.right) should return True
2. They are flipped -> recursion with (root1.right, root2.left,) and  (root1.left, root2.right) should return True
   
3. They are different -> Otherwise

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def flipEquiv(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: bool
        """
        def compare(node1,node2):
            if node1 == None and node2 == None:
                return True
            if node1 == None or node2 == None:
                return False
            if node1.val != node2.val:
                return False
            res = compare(node1.left, node2.left) and compare(node1.right, node2.right)
            res = res or compare(node1.left, node2.right) and compare(node1.right, node2.left)
            return res
        return compare(root1, root2)

Runtime

Time: O(n)

Space: O(1)

link: https://leetcode.com/problems/reveal-cards-in-increasing-order/

Thought

So the rule is if you pop anything from front, then you shall move next head to tail. Reversely, if we want to build the original sequence, we could assume if you want to insert anything in head, you should pop your tail, and push the tail to head

Code

class Solution:
    def deckRevealedIncreasing(self, deck):
        """
        :type deck: List[int]
        :rtype: List[int]
        """
        deck.sort(reverse= True)
        res = collections.deque()
        for i in deck:
            if not res:
                res.append(i)
            else:
                p = res[-1]
                res.pop()
                res.appendleft(p)
                res.appendleft(i)
        return list(res)
            

Runtime

Time: O(n)
Space: O(n)

link: https://leetcode.com/problems/largest-time-for-given-digits/

Thought

Its easy to think use DFS to solve it: it has limit data(4 digits), and DFS will enumerates all possible combinations

Code

class Solution:
    def largestTimeFromDigits(self, A):
        """
        :type A: List[int]
        :rtype: str
        """
        self.res = -1
        def dfs(A, res, visited):
            if len(res) == 4:
                if res[0] * 10 + res[1] < 24 and res[2] * 10 + res[3] < 60:
                    self.res = max(self.res, res[0]* 1000 + res[1] * 100 + res[2] * 10 + res[3])
            for j in range(4):
                if not visited[j]:
                    visited[j] = True
                    res.append(A[j])
                    dfs(A,res, visited)
                    visited[j] = False
                    res.pop(-1)
        dfs(A, [], [False, False, False,False]) 
        if self.res == -1:
            return ""
        return str(self.res// 100).zfill(2) + ":" + str(self.res % 100).zfill(2)

Runtime

Time: O(n!)
Space: O(n!)