35. 搜索插入位置
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums) - 1
while l <= r:
mid = (l + r) // 2
if target == nums[mid]: return mid
elif nums[mid] > target: r = mid - 1
else: l = mid + 1
return l
34. 在排序数组中查找元素的第一个和最后一个位置
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def binary_search_01(nums, x):
l = 0
r = len(nums) - 1
while r - l > 3:
mid = (l + r) // 2
if nums[mid] >= x: r =mid
else: l = mid + 1
for i in range(l, r + 1):
if nums[i] >= x: return i
return len(nums)
left = binary_search_01(nums, target)
if left == len(nums) or nums[left] != target:
return [-1, -1]
right = binary_search_01(nums, target + 1) -1
return [left, right]
1. 两数之和
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
def binary_search(nums, idxs, l, x):
r = len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[idxs[mid]] == x: return mid
elif nums[idxs[mid]] > x: r = mid - 1
else: l = mid + 1
return -1
idxs = [i for i in range(len(nums))]
idxs.sort(key = lambda x: nums[x])
for i in range(len(nums)):
find_val = target - nums[idxs[i]]
j = binary_search(nums, idxs, i + 1, find_val)
if j == -1: continue
return [idxs[i], idxs[j]]
return [-1, -1]
69. x 的平方根
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0 or x == 1:
return x
l = 1
r = x
while l < r:
mid = (l + r) // 2
if mid * mid > x:
if r == mid: break
r = mid
else:
if l == mid: break
l = mid
return l
1658. 将 x 减到 0 的最小操作数
class Solution:
def minOperations(self, nums: List[int], x: int) -> int:
def binary_search(nums, findval):
l = 0
r = len(nums) - 1
while l <= r:
mid = (l + r) // 2
if nums[mid] == findval: return mid
elif nums[mid] > findval: r = mid - 1
else: l = mid + 1
return -1
presuml = [0] * (len(nums) + 1)
presumr = [0] * (len(nums) + 1)
for i in range(len(nums)):
presuml[i + 1] = presuml[i] + nums[i]
for i in range(len(nums)):
presumr[i + 1] = presumr[i] + nums[-1 - i]
ans = 100001
for i in range(len(nums) + 1):
j = binary_search(presumr, x - presuml[i])
if j == -1: continue
if i + j > len(nums): continue
ans = min(ans, j + i)
return ans if ans != 100001 else -1
81. 搜索旋转排序数组 II
class Solution:
def search(self, nums: List[int], target: int) -> bool:
if target == nums[0] or target == nums[-1]:
return True
l = 0
r = len(nums) - 1
while l < len(nums) and nums[l] == nums[0]: l += 1
while r >= 0 and nums[r] == nums[0]: r -= 1
head = l
tail = r
while l <= r:
mid = (l + r) // 2
if target == nums[mid]: return True
if nums[mid] <= nums[tail]:
if target <= nums[tail] and target > nums[mid]: l = mid + 1
else: r = mid - 1
else:
if target >= nums[head] and target < nums[mid]: r = mid - 1
else: l = mid + 1
return False
475. 供暖器
class Solution:
def findRadius(self, houses: List[int], heaters: List[int]) -> int:
def binary_search_01(nums, x):
l = 0
r = len(nums) - 1
while r - l > 3:
mid = (l + r) // 2
if nums[mid] >= x: r = mid
else: l = mid + 1
for i in range(l, r + 1):
if nums[i] >= x: return i
return len(nums)
heaters.sort()
ans = 0
for house in houses:
j = binary_search_01(heaters, house)
a = abs(heaters[j] - house) if j < len(heaters) else 1000000000
b = abs(house - heaters[j - 1]) if j else a + 1
ans = max(ans, min(a, b))
return ans
300. 最长递增子序列
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
dp = []
for i in range(len(nums)):
if not dp or nums[i] > dp[-1]:
dp.append(nums[i])
else:
l = 0
r = len(dp) - 1
tmp = 0
while l <= r:
mid = (l + r) // 2
if dp[mid] >= nums[i]:
tmp = mid
r = mid - 1
else: l = mid + 1
dp[tmp] = nums[i]
return len(dp)
1011. 在 D 天内送达包裹的能力
class Solution:
def shipWithinDays(self, weights: List[int], days: int) -> int:
def ship_capacity(capacity):
count = 1
tmp = 0
for weight in weights:
if tmp + weight > capacity:
tmp = 0
count += 1
tmp += weight
return count
l = max(weights)
r = sum(weights)
while l < r:
mid = (l + r) // 2
day = ship_capacity(mid)
if day <= days:
r = mid
else:
l = mid + 1
return l
4. 寻找两个正序数组的中位数
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
def find_k(nums1, nums2,i, j, k):
if len(nums2) == j: return nums1[i + k - 1]
if len(nums1) == i: return nums2[j + k - 1]
if k == 1: return min(nums1[i], nums2[j])
k_1 = min(k // 2, len(nums1) - i)
k_2 = min(k - k_1, len(nums2) - j)
if nums1[i + k_1 - 1] > nums2[j + k_2 -1]:
return find_k(nums1, nums2, i, j + k_2, k - k_2)
else:
return find_k(nums1, nums2, i + k_1,j, k - k_1)
n = len(nums1)
m = len(nums2)
mid = (n + m + 1) // 2
a = find_k(nums1, nums2, 0, 0, mid)
if (n + m) % 2 == 1: return a
b = find_k(nums1, nums2,0, 0, mid + 1)
return (a + b) / 2
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/76885.html
