More algorithms today. Pretty efficient ones at that. All above 90% ranked on the first submission. I'm beginning to find a lot of patterns that can be applied to the different problems. Most of the Easy binary tree questions are guilty of this.
I'm really happy that I finally solved Flipping an Image -- I had been in the thicket of a messy solution for a couple days but I was able to Pythonize it (read: refactor it)! I got hung up on solving it optimally before peaking at any resources.
Problem: Flip a binary matrix and then invert it.
The trick is doing both steps at once. In other words, you don't want two for loops.
class Solution(object):def flipAndInvertImage(self, A):""":type A: List[List[int]]:rtype: List[List[int]]"""for x in range(len(A)):A[x] = A[x][::-1]for y in range(len(A[x])):A[x][y] ^= 1return A
Outrageously straightforwards when it's reduced down to four lines.
Problem: Do these two trees have similar leaves -- read left-to-right.
We're going to the edge of these trees and comparing the concatenated values found therein, or, there-out-there.
# Definition for a binary tree node.# class TreeNode(object):# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object):def leafSimilar(self, root1, root2):""":type root1: TreeNode:type root2: TreeNode:rtype: bool"""self.root1_store = self.root2_store = def bfs_recurse(node, store):if not node.left and not node.right:store.append(node.val)else:if node.left:bfs_recurse(node.left, store)if node.right:bfs_recurse(node.right, store)if root1:bfs_recurse(root1, self.root1_store)if root2:bfs_recurse(root2, self.root2_store)return self.root1_store == self.root2_store
First try, pre-optimization:
Runtime: 32 ms, faster than 99.02% of Python online submissions..
Problem: What is the deepest level of this n-ary tree?
For this, we'll need a full tree traversal and some way of keeping track of the maximum depth so far. Lately, I've been reaching for instance variables in situations like this.
"""# Definition for a Node.class Node(object):def __init__(self, val, children):self.val = valself.children = children"""class Solution(object):def maxDepth(self, root):""":type root: Node:rtype: int"""self.depth = 0def dfs_recurse(node, depth):depth += 1for c in node.children:dfs_recurse(c, depth)self.depth = max(depth, self.depth)if root:dfs_recurse(root, 0)return self.depth
I'm going to check out some other solutions that don't use pseudo-globals.