Skip to content

Instantly share code, notes, and snippets.

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從後面遍歷到前面, ji遍歷到後面
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 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 237. Delete Node in a Linked List.py
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
"""
PC:
-we're not allowed to access head of linked list
View 234. Palindrome Linked List.py
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
"""
d->1->2->2->1
Optimal solution with O(1) space