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] |
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 sortArray(self, nums: List[int]) -> List[int]: | |
return self.bucketSort(nums) | |
def bucketSort(self, A): | |
""" | |
1. It's in-place sorting. | |
2. Bucket sort is mainly useful when input is uniformly distributed over a range.(floating number is allowed) | |
step1: create n buckets | |
step2: put element into buckets |
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: | |
""" | |
{ | |
i:2 | |
love:2 | |
leetcode:1 | |
codong:1 | |
} | |
怎麼處理k=1 | |
heqp可能會丟掉i而不是丟掉love |
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: | |
""" | |
Thought Process: | |
Sorting | |
PQ: | |
if k == n: | |
we return min elememnt | |
So we use a pq with size k to maintain a top k elements out of n. | |
after looping over all elements in the given array. Return the topmost one, the smallest one inside the pq with size k, which is kth largest elememnt | |
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
""" | |
Given a bst | |
5 | |
/ \ | |
3 7 | |
/ \ / | |
1 4 6 | |
pre-order: 5-> 3 -> 7 ==> 5->3->1->4->7->6 | |
/ \ / | |
1 4 6 |
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 sortArray(self, nums: List[int]) -> List[int]: | |
return self.insertionSort(nums) | |
def insertionSort(self, A): | |
""" | |
思路: | |
i這個指針的元素代表我們需要插入的元素, 經過一輪處理後我們希望i的左邊是partial sorted的. | |
所以當i走到最後, 整個array就sort完. | |
為了做到這部, 每次都create 一個指針j從i開始遞減到index 0.每一次遞減都跟上一個元素比如果比較大就交換. |