This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class MaxStack: | |
""" | |
push 1, 5 | |
tmp_stack = [] | |
stack = [5,1] | |
max_stack = [5,5] | |
這題多了一個pop max 是最難的地方 | |
tmp = stakc.pop() # 1 | |
tmp_max = max_stack.pop() # 5 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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: | |
""" | |
root->left->right(pre-order) | |
left->right->root(post-order) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution: | |
""" | |
1.有加號, 減號, 乘號, 除號!沒有括號 | |
2.All the integers in the expression are non-negative integers, which means there's no leading negative sign and no 3*-5 | |
10+3-2 | |
i | |
3+5 | |
i | |
1.遇到+/-號, 我們就可以parse下一個num, 然後根據sign把num放進stack |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution: | |
""" | |
What's disibution of input string s? | |
沒有乘號, 只有加號和減號! | |
當只有加號和減號,沒有括號和乘號! | |
1-1 | |
i | |
num=1 | |
sign=-1 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution: | |
""" | |
"2*(5+5*2)/3+(6/2+8)" | |
i | |
""" | |
def calculate(self, s: str) -> int: | |
def cal_update(op, num, stack): | |
if op == "+": | |
stack.append(num) | |
elif op == "-": |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution: | |
""" | |
Brute Force: 已當前高度為邊界,去找出所有可能的rectangle | |
we traverse the array. | |
For each cur_h, we enumerate all valid rectangle and calculater area | |
by w * min_h in the subarray. | |
T:O(n^2) | |
S:O(1) | |
Can we optimise? |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class MedianFinder: | |
""" | |
Binary Search + Insert | |
T: O(logn) +O(n) = O(n) for add function O(1) for findMedian. | |
S: O(n) | |
我們用一個array不斷存放新進來的data, as time goes, it's become inefficient in terms of space(not scalable) | |
Two heaps: max heap+min_heap+balance | |
T: 3*O(logn) for add function O(1) for findMedian. | |
S: O(n) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class KthLargest: | |
""" | |
Binary Search+ Insert | |
[2,4,5,8] | |
k=3 | |
add 3 -> [2,3,4,5,8]-->return 4 | |
- | |
add 4 -> [2,3,4,5,5,8]-->return 5 | |
- | |
[2,3,4,5,5,8,10] |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution: | |
def balancedStringSplit(self, s: str) -> int: | |
balance = 0 | |
n = len(s) | |
ans = 0 | |
for i in range(n): | |
if s[i] == "R": | |
balance+=1 | |
else: | |
balance-=1 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution: | |
""" | |
what's distribution of input string s: | |
---> s consists of English letters and digits. At most, 26+10 numbers | |
Heap solution and Sorting takes O(nlogn) | |
Bucket sort | |
freq array=[0,1,2,3,..,max_freq] |
NewerOlder