View 48. Rotate Image.py
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 |
View 280. Wiggle Sort.py
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 |
View 53. Maximum Subarray.py
class Solution: | |
def maxSubArray(self, nums: List[int]) -> int: | |
def get_cross_sum(nums, left, right, mid): | |
left_subsum = float("-inf") | |
cross_sum = 0 | |
for i in range(mid, left-1, -1): | |
cross_sum += nums[i] | |
left_subsum = max(left_subsum, cross_sum) | |
left_subsum = left_subsum if left_subsum != float("-inf") else 0 |
View 5. Longest Palindromic Substring.py
class Solution: | |
""" | |
PC: there might be multiple valid answer | |
<---i | |
s = "babad" | |
i | |
j | |
i從後面遍歷到前面, j從i遍歷到後面 | |
View 128. Longest Consecutive Sequence.py
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 |
View 153. Find Minimum in Rotated Sorted Array.py
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) |
View mergeSort.py
def merge_sort(arr): | |
""" | |
Thought Process: | |
1.Divide the array into two halves | |
2.recursively call merge sort for left half and call merge sort for right half. | |
What this return is sorted array already. | |
3.stop merge process until size of array becomes 1 | |
Time Complexity Analysis: |
View 445. Add Two Numbers II.py
# 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. |
View 1290. Convert Binary Number in a Linked List to Integer.py
# 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 |
View 203. Remove Linked List Elements.py
# Definition for singly-linked list. | |
# class ListNode: | |
# def __init__(self, val=0, next=None): | |
# self.val = val | |
# self.next = next | |
class Solution: | |
""" | |
d->7->-7>-7->7 | |
perv cur | |
""" |
NewerOlder