LeetCode in python简单题–二分查找-叭楼楼市分享网

楼市新闻、行业动态
叭楼，新房带看，二手房代办过户，望京二手房精选房源，您置业的小管家。

二分查找的简单题整理了7个。

提纲

35. 搜索插入位置

69. x 的平方根

167. 两数之和 II – 输入有序数组

349. 两个数组的交集

350. 两个数组的交集 II

367. 有效的完全平方数

441. 排列硬币

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2

示例 2:

输入: [1,3,5,6], 2
输出: 1

代码 1：

使用for循环遍历数组，首先考虑target不在数组中，且比数组中最大的数大的情况下，直接返回len(nums)；找到第一个大于target的位置，时间复杂度O(n)。

class Solution(object):
    def searchInsert(self, nums, target):
        if target > nums[len(nums)-1]:
            return len(nums)
        for i in range(len(nums)):
            if nums[i] >= target:
                return i

代码2：

二分查找的时间复杂度是O(logn)，注意临界值。

class Solution(object):
    def searchInsert(self, nums, target):
        if target <= nums[0]:
            return 0
        if target > nums[len(nums)-1]:
            return len(nums)
        low,high = 0, len(nums)-1
        while low <= high:
            mid = (low + high) // 2
            if target < nums[mid]:
                high = mid - 1
            elif target > nums[mid]:
                low = mid +1
            else:
                return mid
        if target < nums[mid]:
            return mid
        if target > nums[mid]:
            return mid + 1

69. x 的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

代码

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 2:
            return x
        left, right = 1, x//2
        while left <= right:
            mid = (left + right)//2
            if mid*mid > x:
                right = mid - 1
            else:
                left = mid + 1
        return left - 1

167. 两数之和 II – 输入有序数组

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例:

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

思路

左右两个指针移动，sum等于左右两个元素的和，sum和target比较，当sum小于target时，start往右走，当sum大于target的时候,end往左走。

代码

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        start = 0
        end = len(numbers) - 1
        sum = 0
        while start < end:
            sum = numbers[start] + numbers[end]
            if sum < target:
                start += 1
            elif sum > target:
                end -= 1
            else:
                return [start+1, end+1]

349. 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]

示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]

说明:

输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。

思路

349和350题思路一样，代码写的很清楚。

代码

class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1.sort()
        nums2.sort()
        res = set()
        i = j = 0
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                res.add(nums1[i])
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        return list(res)

350. 两个数组的交集 II

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]

示例 2:

输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]

说明：

输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。

代码

class Solution(object):
    def intersect(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        nums1.sort()
        nums2.sort()
        res = []
        i = j = 0
        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                res.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1
        return list(res)

367. 有效的完全平方数

给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。

说明：不要使用任何内置的库函数，如 sqrt。

示例 1：

输入：16
输出：True

示例 2：

输入：14
输出：False

思路

二分查找，看能否找到num开平方后的数。

代码

class Solution(object):
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        l = 1
        r = num
        while l <= r:
            mid = (l+r)//2
            t = mid ** 2
            if t > num:
                r = mid - 1
            elif t < num:
                l = mid +1
            else:
                return True
        return False

374. 猜数字大小

你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。

给定一个数字 n，找出可形成完整阶梯行的总行数。

n 是一个非负整数，并且在32位有符号整型的范围内。

示例 :

n = 5
硬币可排列成以下几行:

 
 
因为第三行不完整，所以返回2.

方法一：

一行行堆积，每一行比上一行多一个，但该方法超时。

class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n==0 or n == 1:
            return n
        temp = 0
        t = 0
        for i in range(1,n):
            temp += i
            if temp <= n:
                t += 1
        return t

方法二：

二分查找，利用公式1+2+…+n = n*(n+1)/2求出所在层一共花掉多少个数。

class Solution(object):
    def arrangeCoins(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 1:
            return n
        l = 0
        r = n
        while l <= r:
            mid = (l + r)//2
            if mid*(mid+1)/2 <= n:
                l = mid+1
            else:
                r = mid-1
        return l - 1

声明：本站内容来源于网络或叭楼会员发布，叭楼只作为信息发布平台，版权归原作者所有，本站不承担任何图片、内容、观点等内容版权问题，如对内容有歧义，可第一时间联系本站管理员发送邮件8309272@qq.com或者扫码微信沟通，经核实后我们会第一时间删除。
北京二手房、楼市分析
二分查找的简单题整理了7个。提纲35. 搜索插入位置69. x 的平方根167. 两数之和 II – 输入有序数组349. 两个数组的交集350. 两个数组的交集 II367. 有效的完全平方数441. 排列硬币35. 搜索插入位置给定一个排序数组和一个目标值，在数组中找到目标值，并返…