0X00 leetcode 刷题 7 道
- 搜索旋转排序数组(33)
- 搜索旋转排序数组 II(81)
- 寻找旋转排序数组中的最小值(153)
- 寻找旋转排序数组中的最小值 II(154)
- 寻找峰值(162)
- 山脉数组的峰顶索引(852)
- x 的平方根(852)
0X01 每道题的小小记录
首先我们从模板开始:
寻找旋转排序数组中的最小值(153)
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
if nums[left] < nums[right]:
return nums[left]
mid = left + (right - left) // 2
if nums[mid] >= nums[left]:
left = mid + 1
else:
right = mid
return nums[left]
中等难度
- 肯定是二叉搜索
- 关键要知道哪边存在最小值以及什么时候退出
首先我们得知道进行二分搜索的时候，至少有一边是有序的，我们要做的就是找到最小值那边的 left 和 right
-
如果 nums[left] < nums[right] 那么说明整个都是有序的 ，直接返回最小值 nums[left]
-
否则现在不是有序的,最小值所在的序列,还没有被找到
如果 nums[mid] > nums[left] 则左边是有序的,此时取等号是因为,当 mid == left 的时候也认为左边是有序的- 更新 left 和 right
还有一个关键是这个的退出条件: left < right,最后退出时 left == right,即要找的最小值
寻找旋转排序数组中的最小值 II(154)
class Solution:
def findMin(self, nums: List[int]) -> int:
def helper(start, end, nums):
if end == start:
return nums[start]
if end - start == 1:
return min(nums[end], nums[start])
if nums[end] > nums[start]:
return nums[start]
mid = start + (end - start) // 2
return min(helper(start, mid, nums), helper(mid+1, end, nums))
return helper(0, len(nums)-1, nums)
这个题因为有重复元素,所以二叉搜索的最坏情况是 O(n)
用递归去做,更好理解这道题:
helper 就是用来找到这个序列的最小值的
- 如果只有一个值,那这个值就是最小值
- 如果有两个值,返回两个里面最小的
- 如果这个序列中 nums[end] > nums[start] 即这个序列是有序的,直接返回 nums[start]
- 否则去递归查找
这道题的关键在于时间复杂度是 O(n) 由于有重复元素:
2 2 2 2 2 2 2 1 2
此时 nums[end] == nums[start] 无法判断是否有序,必须又遍历内部
搜索旋转排序数组(33)
class Solution:
def search(self, nums: List[int], target: int) -> int:
if len(nums) == 0: return -1
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if target == nums[mid]: return mid
if nums[mid] >= nums[left]:
# 左边是有序的
# 判断 target 在不在里面
if target < nums[mid] and target >= nums[left]:
right = mid - 1
else:
left = mid + 1
else:
# 右边是有序的
# 判断 target 在不在里面
if target > nums[mid] and target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return left if nums[left] == target else -1
用了 153 的结论改的
搜索旋转排序数组 II(81)
class Solution:
def binary_search(self,a,low,high,target):
while low<=high:
mid = (low+high)//2
if a[mid]==target:
return True
if a[mid]>target:
high-=1
else:
low+=1
return False
def search(self, nums: List[int], target: int) -> bool:
index = 0
length = len(nums)
if length==0:
return False
for i in range(length-1):
if nums[i]>nums[i+1]:
index = i
break
if self.binary_search(nums,0,index,target):
return True
return self.binary_search(nums,index+1,le
这道题目比较偷懒.....直接找的临界点
寻找峰值(162)
这又是一道很重要的模板题目
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
# mid + 1 一定存在
if nums[mid] > nums[mid+1]:
# 峰值在左边
right = mid
else:
left = mid + 1
return left
判断峰值在哪的结论,直接看代码吧
山脉数组的峰顶索引(852)
class Solution:
def peakIndexInMountainArray(self, A: List[int]) -> int:
left, right = 0, len(A) - 1
while left < right:
mid = left + (right - left) // 2
if A[mid+1] > A[mid]:
# 峰值在右边
left = mid + 1
else:
right = mid
return left
162 改的
x 的平方根(69)
- 解法一:牛顿迭代法
class Solution:
def mySqrt(self, a: int) -> int:
x = a
while x * x > a:
x = (x + a // x) // 2
return x
牛顿迭代:
这里是求: 的解
虽然看起来需要浮点数,但是整数部分也是可以的
- 解法二:二叉搜索
class Solution:
def mySqrt(self, x: int) -> int:
left, right = 1, x
while left <= right:
mid = left + (right - left) // 2
t = mid ** 2
if t == x: return mid
elif t < x: left = mid + 1
else: right = mid - 1
return right
网友评论