25期代码随想录算法训练营第一天

目录

  • 704. 二分查找
    • 代码
  • 27. 移除元素
    • 代码
  • 二分题练习
    • 875. 爱吃香蕉的珂珂
      • 代码

704. 二分查找

链接

代码

左闭右闭 – [left, right]

class Solution:def search(self, nums: List[int], target: int) -> int:l, r = 0, len(nums)-1while l <= r:mid = l + (r - l) // 2 #C++ 里面防止溢出，python中没这个考虑if nums[mid] < target:l = mid + 1elif nums[mid] > target:r = mid - 1else:return midreturn -1

左闭右开 – [left, right)
因为取值取不到nums[r]，所以我们有l < r和r = mid的改动。

class Solution:def search(self, nums: List[int], target: int) -> int:l, r = 0, len(nums)while l < r:mid = l + (r - l) // 2if nums[mid] < target:l = mid + 1elif nums[mid] > target:r = midelse:return midreturn -1

27. 移除元素

链接

代码

双指针

class Solution:def removeElement(self, nums: List[int], val: int) -> int:l, r = 0, len(nums) - 1 while l <= r:if nums[l] == val:nums[l] = nums[r]r -= 1else:l += 1return l

二分题练习

875. 爱吃香蕉的珂珂

链接

代码

class Solution:def minEatingSpeed(self, piles: List[int], h: int) -> int:l, r = 1, max(piles)res = rwhile l <= r:speed = l + (r - l) // 2total_time = 0for p in piles:total_time += math.ceil(float(p) / speed)if total_time <= h:res = speedr = speed - 1else:l = speed + 1return res