2020-2-16 刷题记录

2020-02-16 本文已影响0人 madao756

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

牛顿迭代:

$x_{n+1} = x_{n} - \frac{f(x_n)}{f'(x_n)}$

这里是求: $x^2 - a = 0$ 的解

虽然看起来需要浮点数,但是整数部分也是可以的

解法二:二叉搜索

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