- Remove Duplicates from Sorted Array
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
curr_idx = 0
while curr_idx < len(nums) - 1:
if nums[curr_idx] == nums[curr_idx+1]:
del nums[curr_idx]
curr_idx -= 1
curr_idx += 1
return len(nums)
- Merge Sorted Array
# Merge Sorted Array
# two sorted integer arrays nums1 and nums2
# merge nums2 into nums1 as one sorted array.
# ==>
class Solution:
def merge(self, nums1, m, nums2, n):
m, n = m-1, n-1
while m >= 0 and n >= 0:
if nums1[m] > nums2[n]:
nums1[m+n+1] = nums1[m]
m -= 1
else:
nums1[m+n+1] = nums2[n]
n -= 1
if n != -1: # nums2 is still left
nums1[:n+1] = nums2[:n+1]
- Sort Colors
# 75. Sort Colors
# Given an array with n objects colored red, white or blue,
# sort them in-place
# =>the same color are adjacent, red, white and blue.
class Solution:
def sortColors(self, nums):
i = j = 0
for k in range(len(nums)):
v = nums[k]
nums[k] = 2
if v < 2:
nums[j] = 1
j += 1
if v == 0:
nums[i] = 0
i += 1
- Find Minimum in Rotated Sorted Array
# 153. Find Minimum in Rotated Sorted Array
# array sorted in ascending order is rotated at some pivot
class Solution:
def findMin(self, nums):
left, right = 0, len(nums)-1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
else:
right = mid
return nums[left]
- Find Minimum in Rotated Sorted Array II
# Find Minimum in Rotated Sorted Array II
# Suppose an array sorted in ascending order is rotated
# (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
# Find the minimum element.
# The array may contain duplicates.
class Solution:
def findMin(self, nums: List[int]) -> int:
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi -lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid if nums[hi] != nums[mid] else hi - 1
return nums[lo]
- Search in Rotated Sorted Array
# 33. Search in Rotated Sorted Array
# Suppose an array sorted in ascending order
# rotated at some pivot unknown to you beforehand.
class Solution:
def search(self, nums: List[int], target: int) -> int:
if not nums: return -1
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if target == nums[mid]:return mid
if nums[low] <= nums[mid]:
if nums[low] <= target <= nums[mid]:
high = mid - 1
else:low = mid + 1
else:
if nums[mid] <= target <= nums[high]:
low = mid + 1
else: high = mid - 1
return -1
- Search a 2D Matrix
# Search a 2D Matrix
# searches for a value in an m x n matrix. Matrix properties:
# Integers in each row are sorted from left to right.
# The first integer of each row is greater than the last integer of the previous row.
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
n = len(matrix[0])
lo, hi = 0, len(matrix) * n
while lo < hi:
mid = (lo + hi) // 2
x = matrix[mid//n][mid%n]
if x < target:
lo = mid + 1
elif x > target:
hi = mid
else:
return True
return False
- Search a 2D Matrix II
# 240. Search a 2D Matrix II
# searches for a value in an m x n matrix.
# ascending from left to right; from top to bottom.
class Solution:
def searchMatrix(self, matrix, target):
j = -1
for row in matrix:
while j + len(row) and row[j] > target:
j -= 1
if row[j] == target:
return True
return False
- Search a 2D Matrix II
# 240. Search a 2D Matrix II
# searches for a value in an m x n matrix.
# ascending from left to right; from top to bottom.
class Solution:
def searchMatrix(self, matrix, target):
j = -1
for row in matrix:
while j + len(row) and row[j] > target:
j -= 1 # 每一行 自尾向前
if row[j] == target:
return True
return False
- Median of Two Sorted Arrays
# 4. Median of Two Sorted Arrays
# two sorted arrays nums1 and nums2 of size m and n
# Find the median of the two sorted arrays
class Solution:
def findMedianSortedArrays(self, A,B) -> float:
l = len(A) + len(B)
if l % 2 == 1:
return self.kth(A, B, l // 2)
else:
return (self.kth(A, B, l // 2) + self.kth(A, B, l // 2 - 1)) / 2.
def kth(self, a, b, k):
if not a:
return b[k]
if not b:
return a[k]
ia, ib = len(a) // 2 , len(b) // 2
ma, mb = a[ia], b[ib]
# when k is bigger than the sum of a and b's median indices
if ia + ib < k:
# if a's median is bigger than b's, b's first half doesn't include k
if ma > mb:
return self.kth(a, b[ib + 1:], k - ib - 1)
else:
return self.kth(a[ia + 1:], b, k - ia - 1)
# when k is smaller than the sum of a and b's indices
else:
# if a's median is bigger than b's, a's second half doesn't include k
if ma > mb:
return self.kth(a[:ia], b, k)
else:
return self.kth(a, b[:ib], k)
- Best Time to Buy and Sell Stock
# 121. Best Time to Buy and Sell Stock
# In: ith element => price day i.
# one transaction (buy one and sell one)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices:
return 0
loc = glo = 0
for i in range(1, len(prices)):
loc = max(loc+prices[i]-prices[i-1], 0)
glo = max(glo, loc)
return glo
- Maximum Subarray
# Maximum Subarray
# In: Array
#=>contiguous subarray ; Largest Sum
class Solution:
def maxSubArray(self, A: List[int]) -> int:
if not A:
return 0
curSum = maxSum = A[0]
for num in A[1:]:
curSum = max(num, curSum + num)
maxSum = max(maxSum, curSum)
return maxSum
- Longest Increasing Subsequence
# Longest Increasing Subsequence
# Given an unsorted array of integers,
# find the length of longest increasing subsequence.
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
tails = [0] * len(nums) # [0]
size = 0
for x in nums:
i, j = 0, size
while i != j:
m = (i + j) // 2
if tails[m] < x:
i = m + 1
else:
j = m
tails[i] = x
size = max(i + 1, size)
return size
网友评论