 # Leetcode-Binary Tree Traversal

For recursion, it’s too easy. 3 BT traversals using stack(iterative way to solve it).

• 就記得pre-order和in-order用幾乎百分之99一樣的模板, 差別是一個 root node first另外一個是left order first
• post-order最tricky, 就記得我們最後會reverse postorder, 所以root node就直接給他放進去postorder.

Code:

--

--

# Leetcode-Combination Series

Usually, when it comes to combination problems, the most naive way to solve the problem is generate all possible solutions. And, we use depth-first-search(DFS) or called backtracking technique.

For backtracking, when we do time and space complexity analysis, they follow a certain pattern:

T: O(n**m), n raise to power of m, where n represents at most we have n branches can search for current state and m is maximum depth of recursion tree.

Note: O(n**m) will be upper bound of time complexity. For some cases, if we generate all possible combinations or partitions , given an integer or a string, running time will be O(2**n), lower than upper bound.

S:O(m), where m is maximum depth of recursion tree. (if we don’t consider space of storing answer)

• 39. Combination Sum
• 131. Palindrome Partitioning
• 291. Word Pattern II

--

--

# Leetcode-Basic Calculator Series

Given 一個string expression, 我們要去計算result of expression.

1.是string裡面只有+-(), 沒有乘除. (See LC 224)

2.再來是有+-*/但沒有() (See LC 227)

3.最難版本是+-*/和()都有(See LC 772)

Note:

1. 上面這些題型都可以假設沒有leading negative integers. For example, “-3+2” or “(-3+2)”
2. 只要是有括號的題目, 我們都會再遇到右括號(close parentheses)的時候, 需要先計算括號內的res_in_paren再把這個res_in_paren和左括號(open parentheses)左邊的res做合併.
3. 這是經典的string parsing 算法題, 我們都是用stack來破題, 時間複雜度是O(n), 因為我們算法只需要掃過一遍字串,空間複雜度是O(n) 因為我們用了stack.

Related Problems in LC:

224. Basic Calculator

227. Basic Calculator II

772. Basic Calculator III

--

--

# How to practice LeetCode efficiently?

2021–2022刷題重點:

• 多总结
• 做related的题目
• 重复做了之前做过的题目
• 总结是王道
• 另外我没有遇到原题所以刷那么多题没有用
• 关键是做过了的就会
• 我都是一道题刷几遍最后我面之前
• 我只要做过的题目我能bugfree或者只有typo的写出来
• 為了增加coding 速度和實際面試一樣, 有個初步想法就可以開始尻code, 在做dry run 的動作.

• 題號前400題
• 刷高頻提升會考的知識點覆蓋率(廣度)
• 刷tag提升會考的知識點熟練度(深度)
• 週末做contest or mock interview, 有計時, 增加臨場感, 且也可以查漏補缺知識點.
• 每兩週換一個topic

--

--

Problem Statement

Model

Rule-Based:把given user的所有follower的tweet根據時間反向排序(reverse chronological order)

--

--

# ML-Evaluation Metrics

Why do you need to be familiar with evaluation metric?

--

--

# Leetcode-subarray

Some pattern about continuous subarray related problem. Usually, naive solution is generate all possible subarray, which takes O(n²) times at least. And optimal solution is the one with special data structure such as prefix sum, monotone stack, in most of cases. And, this is tricky. So, I try to summarize what I learned in this post.

Note

1.包含當前element cur, 有多少個subarray的公式?

2.做subarray要注意的edge case:

--

--