class Solution:
def coinChange(self, coins: list[int], amount: int) -> int:
dp = [0] + [0xFFFFFFFF] * (amount)
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return (dp[-1], -1)[dp[-1] == 0xFFFFFFFF]
class Solution:
def search(self, nums: list[int], target: int) -> int:
lo, hi = 0, len(nums)
target_is_rotated = target < nums[0]
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
mid_is_rotated = nums[mid] < nums[0]
if (mid_is_rotated, target_is_rotated) == (True, False): # [t] [m]
hi = mid
elif (mid_is_rotated, target_is_rotated) == (False, True): # [m] [t]
lo = mid + 1
# same side
elif nums[mid] > target:
hi = mid
else:
lo = mid + 1
return -1
class Solution1:
def search(self, nums: list[int], target: int) -> int:
# https://leetcode.com/problems/search-in-rotated-sorted-array/solutions/14435/clever-idea-making-it-simple/
lo, hi = 0, len(nums)
target_is_rotated = target < nums[0]
inf = (-1) ** target_is_rotated * float('inf')
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
mid_is_rotated = nums[mid] < nums[0]
if (nums[mid], inf)[mid_is_rotated != target_is_rotated] > target:
hi = mid
else:
lo = mid + 1
return -1
class Solution:
def maxProduct(self, nums: list[int]) -> int:
result = acc_max = acc_min = nums[0]
for i in range(1, len(nums)):
cand = nums[i], nums[i] * acc_max, nums[i] * acc_min
acc_max, acc_min = max(cand), min(cand)
result = max(result, acc_max, acc_min)
return result
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution1:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
l = r = d = ListNode(next=head)
for _ in range(n - 1):
r = r.next
while r.next and r.next.next is not None:
l, r = l.next, r.next
l.next = l.next.next
return d.next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
l = r = head
for _ in range(n):
r = r.next
if r is None:
return head.next
while r.next:
l, r = l.next, r.next
l.next = l.next.next
return head
class Solution:
def multiply(self, num1: str, num2: str) -> str:
ZERO = '0'
if ZERO in (num1, num2):
return ZERO
def ord_(x):
return ord(x) - ord(ZERO)
def chr_(x):
return chr(x + ord(ZERO))
L1, L2 = len(num1) - 1, len(num2) - 1
result = []
carry = 0
i = 0
while (i <= L1 + L2) or carry:
j = max(0, i - L2)
while j <= min(i, L1):
n1, n2 = num1[L1 - j], num2[L2 - i + j]
carry += ord_(n1) * ord_(n2)
j += 1
result.append(chr_(carry % 10))
carry //= 10
i += 1
return ''.join(result)[::-1]
class Solution:
def spiralOrder(self, matrix: list[list[int]]) -> list[int]:
if not matrix or not matrix[0]:
return []
result = []
t, b, l, r = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
while t <= b and l <= r:
result.extend([matrix[t][x] for x in range(l, r + 1)])
result.extend([matrix[x][r] for x in range(t + 1, b + 1)])
if t < b and l < r:
result.extend([matrix[b][x] for x in range(r - 1, l, -1)])
result.extend([matrix[x][l] for x in range(b, t, -1)])
t, b, l, r = t + 1, b - 1, l + 1, r - 1
return result
class Solution:
def findBall(self, grid: list[list[int]]) -> list[int]:
N = len(grid[0])
def drop(pos: int) -> int:
for row in grid:
adj = pos + row[pos]
if not 0 <= adj < N:
return -1
if row[pos] != row[adj]:
return -1
pos = adj
return pos
return [drop(x) for x in range(N)]
class Solution:
def isHappy(self, n: int) -> bool:
visiteds = set()
while n not in visiteds:
if n == 1:
return True
visiteds.add(n)
n = sum(int(x) ** 2 for x in str(n))
return False
class Solution:
def longestCommonPrefix(self, strs: list[str]) -> str:
result = []
for i, c in enumerate(strs[0]):
if not all([i < len(s) and c == s[i] for s in strs]):
break
result.append(c)
return ''.join(result)