It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.
As a countermeasure, it seems that a site called Let Code will take measures.
A site that trains algorithmic power that can withstand coding tests that are often done in the home.
I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.
Basically, I would like to solve the easy acceptance in descending order.
Last time Leet Code Day6 Starting from Zero "1342. Number of Steps to Reduce a Number to Zero"
It lasted for a week without skipping. Congratulations.
104. Maximum Depth of Binary Tree
It's a fairly early problem, but I felt it was a good problem to understand the structure of the binary tree.
Given a binary tree, you will be asked to write an algorithm that finds the maximum value for that depth.
example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its depth = 3.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def maxDepth(self, root: TreeNode) -> int:
depth = 0
stack = [(root,1)]
while stack:
root,length = stack.pop()
if not root:
return 0
if length > depth:
depth = length
if root.right:
stack.append((root.right,length + 1))
if root.left:
stack.append((root.left,length + 1))
return depth
# Runtime: 40 ms, faster than 70.51% of Python3 online submissions for Maximum Depth of Binary Tree.
# Memory Usage: 14.9 MB, less than 90.62% of Python3 online submissions for Maximum Depth of Binary Tree.
Written in a depth-first search as described in the previous problem with binary search trees, Leet Code Day4 "938. Range Sum of BST" starting from zero Saw.
I found out by looking it up on Discuss etc., but there is also such a way of writing.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
queue = deque([(root, 1)])
while queue:
curr, val = queue.popleft()
if not curr.left and not curr.right and not queue:
return val
if curr.left:
queue.append((curr.left, val+1))
if curr.right:
queue.append((curr.right, val+1))
# Runtime: 36 ms, faster than 89.87% of Python3 online submissions for Maximum Depth of Binary Tree.
# Memory Usage: 15 MB, less than 90.62% of Python3 online submissions for Maximum Depth of Binary Tree.
It is implemented using deque.
Deque is a generalization of stacks and queues (the name is pronounced "deck", which is an abbreviation for "double-ended queue"). Deques can be append and pop from either side, are thread-safe and memory-efficient, and can run with approximately O (1) performance from either direction.
It's as fast as it sounds. Actually, the Runtime is also faster than other answers.
Recommended Posts