linked list
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
cur = head
count = 0
while cur and count!= k:
cur = cur.next
count += 1
if count == k:
cur = self.reverseKGroup(cur, k)
while count:
tmp = head.next
head.next = cur
cur = head
head = tmp
count -= 1
head = cur
return headdp
def coinChange(self, coins: List[int], amount: int) -> int:
# dp[i] is the minimum way to get i coins
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for c in coins:
for i in range(c, amount + 1):
dp[i] = min(dp[i], dp[i - c] + 1)
ans = dp[amount]
return ans if ans != float('inf') else -1
def minDistance(self, word1: str, word2: str) -> int:
@cache
def distance(s1, s2):
if len(s1) == 0:
return len(s2)
if len(s2) == 0:
return len(s1)
if s1[-1] == s2[-1]:
return distance(s1[:-1], s2[:-1])
return 1 + min(
distance(s1[:-1], s2),
distance(s1, s2[:-1]),
distance(s1[:-1], s2[:-1])
)
return distance(word1, word2)sort
def quicksort(arr, start, end):
if start < end:
pivot_index = random.randint(start, end)
arr[pivot_index], arr[end] = arr[end], arr[pivot_index]
pi = partition(arr, start, end)
quicksort(arr, start, pi - 1)
quicksort(arr, pi + 1, end)
def partition(arr, start, end):
pivot = arr[end]
pi = start
for i in range(start, end):
if arr[i] <= pivot:
arr[i], arr[pi] = arr[pi], arr[i]
pi += 1
arr[pi], arr[end] = arr[end], arr[pi]
return pi
def heapify(arr, n, i):
largest = i # Initialize largest as root
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # swap
# Heapify to the root.
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
for i in range(n//2 - 1, -1, -1): #build heap
heapify(arr, n, i)
for i in range(n-1, 0, -1): #sort
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
def insertion_sort(arr):
# Traverse through 1 to len(arr)
for i in range(1, len(arr)):
key = arr[i]
# Move elements of arr[0..i-1], that are
# greater than key, to one position ahead
# of their current position
j = i-1
while j >= 0 and key < arr[j] :
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2 # Finding the mid of the array
L = arr[:mid] # Dividing the array elements into 2 halves
R = arr[mid:]
merge_sort(L) # Sorting the first half
merge_sort(R) # Sorting the second half
i = j = k = 0
# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# Checking if any element was left
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
while j < len(R):
arr[k] = R[j]
j += 1
k += 1
return arr回溯 backtrack
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
def dfs(x):
if x == len(nums) - 1:
res.append(list(nums)) # 添加排列方案
return
dic = set()
for i in range(x, len(nums)):
if nums[i] in dic:
continue # 重复，因此剪枝
dic.add(nums[i])
nums[i], nums[x] = nums[x], nums[i]
dfs(x + 1) # 开启固定第 x + 1 位元素
nums[i], nums[x] = nums[x], nums[i]
res = []
dfs(0)
return res
def generateParenthesis(self, n: int) -> List[str]:
sz = 2 * n
res = []
def bt(s, left, total):
if total == sz:
res.append(''.join(s))
return
if left < n:
s.append('(')
bt(s, left + 1, total + 1)
s.pop()
if total - left < left:
s.append(')')
bt(s, left, total + 1)
s.pop()
bt([], 0, 0)
return res
def restoreIpAddresses(self, s: str) -> List[str]:
res = []
seg = [0] * 4
def dfs(segid, segstart):
if segid == 4 and segstart == len(s):
res.append(".".join(str(s) for s in seg))
return
if segstart == len(s) or segid == 4:
return
if s[segstart] == '0':
seg[segid] = 0
dfs(segid + 1, segstart + 1)
return
addr = 0
for segEnd in range(segstart, len(s)):
addr = addr * 10 + int(s[segEnd])
if addr <= 255:
seg[segid] = addr
dfs(segid + 1, segEnd + 1)
else:
break
dfs(0, 0)
return res
def combinationSum(self, candidates, target):
candidates.sort() # Ensure candidates are sorted.
res = []
using = []
def dfs(start, remain):
if remain == 0:
res.append(list(using))
return
if remain < 0:
return # Early return if remain is negative.
for i in range(start, len(candidates)):
using.append(candidates[i])
dfs(i, remain - candidates[i])
using.pop()
dfs(0, target)
return ressliding window
def minWindow(self, s: str, t: str) -> str:
if not s or not t:
return ''
need = defaultdict(int)
for c in t:
need[c] += 1
need_cnt = len(t)
start, end = 0, 0
res = (float("inf"), 0, 0)
for end, c in enumerate(s):
if need[c] > 0:
need_cnt -= 1
need[c] -= 1
while need_cnt == 0:
new_len = end - start + 1
if new_len < res[0]:
res = (new_len, start, end)
c = s[start]
need[c] += 1
if need[c] > 0:
need_cnt += 1
start += 1
return "" if res[0] == float("inf") else s[res[1]: res[2] + 1]math
def mySqrt(self, x: int) -> int:
# function: f(a) = a^2 - x
if x == 0:
return 0
C, x0 = float(x), float(x)
diff = 1
while diff > 1e-7:
x1 = x0 - (x0 * x0 - C) / (x0 * 2)
diff = abs(x1 - x0)
x0 = x1
return int(x0)graph
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
edges = defaultdict(list)
indeg = [0] * numCourses
for info in prerequisites:
edges[info[1]].append(info[0])
indeg[info[0]] += 1
q = deque([u for u in range(numCourses) if indeg[u] == 0])
res = []
while q:
n = q.popleft()
res.append(n)
for v in edges[n]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
if len(res) == numCourses:
return res
else:
return []misc
def decodeString(self, s: str) -> str:
stk, cnt, res = [], 0, ""
for c in s:
if '0' <= c <= '9':
cnt = 10 * cnt + int(c)
elif c == '[':
stk.append([cnt, res])
res = ""
cnt = 0
elif c == ']':
mul, last_res = stk.pop()
res = last_res + res * mul
else:
res += c
return res