liyunrui

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

liyunrui

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

liyunrui

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

liyunrui

class Solution:
    """
    PC: there might be multiple valid answer
         <---i
    s = "babad"
          i
             j
            
    i從後面遍歷到前面, j從i遍歷到後面
         

liyunrui

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 

liyunrui

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)

liyunrui

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:

liyunrui

# 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.

liyunrui

# 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

liyunrui

# 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
    """