Leecode 101刷题笔记之第四章:和你一起你轻松刷题(Python)

简介: 这篇博客是关于LeetCode上使用Python语言解决二分查找问题的刷题笔记,涵盖了从基础到进阶难度的多个题目及其解法。

69. Sqrt(x) (Easy)

题目描述
给定一个非负整数,求它的开方,向下取整。
输入输出样例
输入一个整数,输出一个整数。

Input: 8
Output: 2

8 的开方结果是2.82842…,向下取整即是2。
题解
我们可以把这道题想象成,给定一个非负整数a,求f (x) = x2 − a = 0 的解。因为我们只考虑x ≥ 0,所以f (x) 在定义域上是单调递增的。考虑到f (0) = −a ≤ 0,f (a) = a2 − a ≥ 0,我们可以对[0, a] 区间使用二分法找到f (x) = 0 的解。
注意,在以下的代码里,为了防止除以0,我们把a = 0 的情况单独考虑,然后对区间[1, a]进行二分查找。我们使用了左闭右闭的写法。
另外,这道题还有一种更快的算法——牛顿迭代法,其公式为xn+1 = xn − f (xn)/ f ′(xn)。给定f (x) = x2 − a = 0,这里的迭代公式为xn+1 = (xn + a/xn)/2
具体代码

# leetcode submit region begin(Prohibit modification and deletion)
"""
执行用时:20 ms, 在所有 Python 提交中击败了93.53%的用户
内存消耗:12.9 MB, 在所有 Python 提交中击败了83.08%的用户
"""
def mySqrt(x):
    """
    :type x: int
    :rtype: int
    """
    if x==1:
        return x
    r=x
    while r>x/r:
        # 基本不等式(a+b)/2 >=√ab 推导自 (a-b)^2 >= 0,注意 a>0 且 b>0
        r=(r+x/r)//2
    return r
# leetcode submit region end(Prohibit modification and deletion)

34. Find First and Last Position of Element in Sorted Array (Medium)

题目描述
给定一个增序的整数数组和一个值,查找该值第一次和最后一次出现的位置。
输入输出样例
输入是一个数组和一个值,输出为该值第一次出现的位置和最后一次出现的位置(从0 开始);如果不存在该值,则两个返回值都设为-1。

Input: nums = [5,7,7,8,8,10], target = 8 
Output: [3,4]

数字8 在第3 位第一次出现,在第4 位最后一次出现。
’题解
这道题可以看作是自己实现C++ 里的 lower_bound 和 upper_bound 函数。这里我们尝试使用左闭右开的写法,当然左闭右闭也可以。
具体代码

# leetcode submit region begin(Prohibit modification and deletion)
"""
执行用时:12 ms, 在所有 Python 提交中击败了96.96%的用户
内存消耗:13.2 MB, 在所有 Python 提交中击败了80.41%的用户
"""
class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """ 
        res=[-1,-1]
        if nums==[]:return res
        n=len(nums)
        l,r=0,n-1

        while l<=r:
            if l==r and nums[l]!=target and nums[r]!=target:
                return res
            mid = l+(r-l)//2
            if nums[mid]==target:
                res=[mid,mid]
                l=mid-1
                r=mid+1
                while l>=0 and nums[l]==target:
                    res[0]=l
                    l-=1
                while r<=n-1 and nums[r]==target:
                    res[1]=r
                    r+=1
                return res
            elif nums[mid]>target:
                r=mid
            else:
                l=mid+1
        return res

81. Search in Rotated Sorted Array II (Medium)

题目描述
一个原本增序的数组被首尾相连后按某个位置断开(如[1,2,2,3,4,5] → [2,3,4,5,1,2],在第一位和第二位断开),我们称其为旋转数组。给定一个值,判断这个值是否存在于这个为旋转数组中。
输入输出样例
输入是一个数组和一个值,输出是一个布尔值,表示数组中是否存在该值。

Input: nums = [2,5,6,0,0,1,2], target = 0 
Output: true

’题解
即使数组被旋转过,我们仍然可以利用这个数组的递增性,使用二分查找。对于当前的中点,如果它指向的值小于等于右端,那么说明右区间是排好序的;反之,那么说明左区间是排好序的。如果目标值位于排好序的区间内,我们可以对这个区间继续二分查找;反之,我们对于另一半区间继续二分查找。
注意,因为数组存在重复数字,如果中点和左端的数字相同,我们并不能确定是左区间全部相同,还是右区间完全相同。在这种情况下,我们可以简单地将左端点右移一位,然后继续进行二分查找。
具体代码

"""
执行用时:16 ms, 在所有 Python 提交中击败了85.37%的用户
内存消耗:13.1 MB, 在所有 Python 提交中击败了94.24%的用户
"""
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        n=len(nums)
        l,r=0,n-1
        while l<=r:
            mid=l+(r-l)//2
            if nums[mid]==target:
                return True
            elif nums[mid]==nums[l]:
                l+=1
            elif nums[mid]==nums[r]:
                r-=1
            elif nums[mid]<nums[r]: # 此时右边有序
                if nums[mid]<target<=nums[r]:
                    l=mid+1
                else:
                    r=mid-1
            elif nums[mid]>nums[l]: # 此时左边有序
                if nums[mid]>target>=nums[l]:
                    r=mid-1
                else:
                    l=mid+1
        return False

练习-基础难度

154. Find Minimum in Rotated Sorted Array II (Medium)

旋转数组的变形题之一。
题目描述
已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到:
若旋转 4 次,则可以得到 [4,5,6,7,0,1,4]
若旋转 7 次,则可以得到 [0,1,4,4,5,6,7]
注意,数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须尽可能减少整个过程的操作步骤。
输入输出样例

输入:nums = [1,3,5]
输出:1

’题解

  • 旋转数组中求最小值,为什么要用 mid 和 right 相比?
  • 假设用 mid 和 left 比较, 如果 mid 大于 left ,能说明什么? 说明最小值在 [left, mid ] 区间吗? 或说明最小值在 [mid, right] 区间吗? 都说明不了。因为 mid 大于 left 的时候,左边有序,但是最小值不一定是在坐标。
  • 但是 用 mid 和 right 比较,mid 小于 right ,说明右边是有序的,最小值在 [left, mid] 之间,mid 不能被排除,是一个潜在的答案。如果 mid 大于 right, 说明右边无序,最小值在 [mid, right] 的区间里。
  • 如果面试的时候是求旋转数组中的最大值,就可以用 mid 和 left 来比较了。

具体代码

"""
执行用时:20 ms, 在所有 Python 提交中击败了55.03%的用户
内存消耗:13.1 MB, 在所有 Python 提交中击败了92.74%的用户
"""
class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l,r=0,len(nums)-1
        while l<r:
            mid=l+(r-l)//2
            if nums[mid]>nums[r]: # 说明右边无序,答案在右边
                l=mid+1
            elif nums[mid]<nums[r]: # 说明右边有序,答案在左边
                r=mid
            else:
                r-=1
        return nums[r]

def findmax(nums):
    l, r = 0, len(nums) - 1
    while l < r:
        mid = l + (r - l) // 2
        if nums[l] > nums[mid]:  # 说明左边无序 则答案在左边
            r = mid + 1
        elif nums[l] < nums[mid]:  # 说明左边有序 则答案在右边
            l = mid
        else:
            # 如果mid和right相等,那么说明需要进一步减少r来判断
            l += 1
    return nums[l]

540. Single Element in a Sorted Array (Medium)

在出现独立数之前和之后,奇偶位数的值发生了什么变化?
题目描述
给你一个仅由整数组成的有序数组,其中每个元素都会出现两次,唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
输入输出样例

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

’题解
根据中间点左右的值来判断,奇和偶数的位置。

具体代码

"""
执行用时:28 ms, 在所有 Python 提交中击败了36.11%的用户
内存消耗:16.7 MB, 在所有 Python 提交中击败了94.09%的用户
通过测试用例:
15 / 15
"""
class Solution(object):
    def singleNonDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 0:
            return 0
        elif n == 1:
            return nums[0]
        else:
            l, r = 0, n - 1
            while True:
                if l==r:
                    return nums[l]
                mid = l + (r - l) // 2
                if nums[mid] == nums[mid - 1]:
                    # 说明和左边凑成一对
                    if (mid + 1) % 2 != 0:
                        # 说明单身狗在nums[:mid+1]中
                        r = mid + 1
                    else:
                        # 说明单身狗在nums[mid+1:]中 直接忽略相等的这两个
                        l = mid + 1
                elif nums[mid] == nums[mid + 1]:
                    # 说明和右边凑成一对
                    if (mid + 2) % 2 == 0:
                        l = mid + 2
                    else:
                        r = mid
                else:
                    return nums[mid]

"""
执行用时:16 ms, 在所有 Python 提交中击败了94.09%的用户
内存消耗:16.8 MB, 在所有 Python 提交中击败了89.06%的用户
"""
class Solution(object):
    def singleNonDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        l,r=0,len(nums)-1
        while l<r:
            mid=l+(r-l)//2
            if mid%2!=0:
                mid=mid-1
            if nums[mid]==nums[mid+1]:
                l=mid+2
            elif nums[mid]==nums[mid-1]:
                r=mid
            else:
                return nums[mid]
        return nums[r]

练习-进阶难度

4. Median of Two Sorted Arrays (Hard)

需要对两个数组同时进行二分搜索。
题目描述
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。
输入输出样例

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2

题解
引入寻找第k小的数的函数来避免一些冗余。在getKth()函数中,所有操作在第一个数组长度小于等于第二个的逻辑上产生。若第一个数组为空,则直接输出第二个数组的第k位。若k为1,则输出两个数组第一位中较小的数。k大于1时,对两个数组的k/2位开始比较,若A[k/2]较小,则比A[k/2]小的数最多有k-2个,所以A[k/2]前的数可以被放弃,操作的数组变为(A[k/2:], B, pb),A[k/2]较大时想法类似,抛弃B数组后半部份的数。
具体代码

"""
执行用时:40 ms, 在所有 Python 提交中击败了62.20%的用户
内存消耗:13.1 MB, 在所有 Python 提交中击败了77.44%的用户
"""
def findMedianSortedArrays(nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: float
    """
    def findtheresult(nums1,n,nums2,m,k):
        # 若第一个数组为空,则直接输出第二个数组的第k位。若k为1,则输出两个数组第一位中较小的数
        if n>m:return findtheresult(nums2,m,nums1,n,k) # 始终让nums1的长度小于nums2
        if n==0:return nums2[k-1] # 为了防止[]和[1,2,3]
        if k==1:return min(nums1[0],nums2[0]) # 为了防止[]和[2]
        # k大于1时,对两个数组的k/2位开始比较
        posi_a = min(k//2, n)
        posi_b = k - posi_a
        if nums1[posi_a - 1] <= nums2[posi_b - 1]:
            return findtheresult(nums1[posi_a:],len(nums1[posi_a:]),nums2,m,posi_b)
        else:
            return findtheresult(nums1,n,nums2[posi_b:],len(nums2[posi_b:]),posi_a)

    n1,n2=len(nums1),len(nums2)
    if (n1+n2)%2==1:
        # 说明为奇数
        return findtheresult(nums1,n1,nums2,n2,(n1+n2)//2+1)
    else:
        # 说明为偶数
        return (findtheresult(nums1,n1,nums2,n2,(n1+n2)//2)+findtheresult(nums1,n1,nums2,n2,(n1+n2)//2+1))*0.5
目录
相关文章
|
2月前
|
搜索推荐 Python
Leecode 101刷题笔记之第五章:和你一起你轻松刷题(Python)
这篇文章是关于LeetCode第101章的刷题笔记,涵盖了多种排序算法的Python实现和两个中等难度的编程练习题的解法。
23 3
|
2月前
|
算法 C++ Python
Leecode 101刷题笔记之第三章:和你一起你轻松刷题(Python)
本文是关于LeetCode算法题的刷题笔记,主要介绍了使用双指针技术解决的一系列算法问题,包括Two Sum II、Merge Sorted Array、Linked List Cycle II等,并提供了详细的题解和Python代码实现。
15 0
|
2月前
|
算法 C++ 索引
Leecode 101刷题笔记之第二章:和你一起你轻松刷题(Python)
本文是关于LeetCode 101刷题笔记的第二章,主要介绍了使用Python解决贪心算法题目的方法和实例。
11 0
|
存储 监控 API
Python笔记2(函数参数、面向对象、装饰器、高级函数、捕获异常、dir)
Python笔记2(函数参数、面向对象、装饰器、高级函数、捕获异常、dir)
70 0
|
7月前
|
Python
Python基础 笔记(九) 函数及进阶
Python基础 笔记(九) 函数及进阶
50 6
|
4月前
|
存储 Python
Python笔记8 函数
本文是作者的Python复习笔记第八篇,全面介绍了Python中的函数定义与使用,包括函数的参数传递(位置参数、关键字参数、默认参数、列表参数、任意数量参数和关键字参数)、函数的返回值以及如何创建和调用函数库(模块),并提供了丰富的示例代码。
30 0
|
4月前
|
Python
【python笔记】使用zip函数迭代多个可迭代对象
【python笔记】使用zip函数迭代多个可迭代对象
|
7月前
|
Python
Python基础 笔记(三) 标识符、输入输出函数
Python基础 笔记(三) 标识符、输入输出函数
63 7
|
算法 数据处理 索引
【Python 小白到精通 | 课程笔记】第三章:数据处理就像侦探游戏(函数和包)
【Python 小白到精通 | 课程笔记】第三章:数据处理就像侦探游戏(函数和包)
255 0
【Python 小白到精通 | 课程笔记】第三章:数据处理就像侦探游戏(函数和包)