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
class Solution: | |
def rotate(self, matrix: List[List[int]]) -> None: | |
""" | |
Do not return anything, modify matrix in-place instead. | |
""" | |
m = len(matrix) | |
n = len(matrix[0]) | |
row_b = 0 # 0-> 1 | |
row_e = m-1 # 2->1 | |
col_b = 0 |
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: | |
""" | |
[3,5,2,1,6,4] | |
n = 6 | |
mid = 3 | |
[1,2,3,5,6,4] | |
i j | |
i = mid-1 if n%2==0 | |
tmp_arr = [3,4,2,6,1,5] | |
在把tmp_arr猜回array |
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: | |
""" | |
Divide and Conquer: | |
我們可以把我們要求的問題拆成不重複的子問題 | |
1.左邊subarray的最大連續合 | |
2.右邊subarray的最大連續合 | |
3.包含當前元素的的最大連續和 | |
用一個最小的例子[-2, 1]去展示你的idea | |
[-2,1,-3,4,-1,2,1,-5,4] | |
0 1. 2 3. 4 5. 6 7 8 |
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: | |
""" | |
PC: there might be multiple valid answer | |
<---i | |
s = "babad" | |
i | |
j | |
i從後面遍歷到前面, j從i遍歷到後面 | |
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 UnionFind: | |
def __init__(self, n): | |
self._parents = [node for node in range(n)] | |
self._rank = [1 for _ in range(n)] | |
def find(self, u): | |
while u != self._parents[u]: | |
self._parents[u] = self._parents[self._parents[u]] | |
u = self._parents[u] | |
return u |
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 findMin(self, nums: List[int]) -> int: | |
def find_pivot_element(nums, l, r): | |
mid = l + (r-l) // 2 | |
if r-l <= 1: | |
return min(nums[l], nums[r]) | |
if nums[l] < nums[r]: | |
return nums[l] | |
left_min = find_pivot_element(nums, l, mid-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
# Definition for singly-linked list. | |
# class ListNode: | |
# def __init__(self, val=0, next=None): | |
# self.val = val | |
# self.next = next | |
class Solution: | |
""" | |
Solution: using stack -> O(n) in space | |
we use stack to simulate addition. |
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 singly-linked list. | |
# class ListNode: | |
# def __init__(self, val=0, next=None): | |
# self.val = val | |
# self.next = next | |
class Solution: | |
""" | |
Naive Solution(如果你不懂binary representation) | |
step1: reverse the linked list | |
step2: travser the linked list and progressivly build the res |