leetcode 二分查找 - easy

objc94 发布于2019-07-30 17:44 / 772人阅读

摘要：如果目标值不存在于数组中，返回它将会被按顺序插入的位置。也因为是排序的数组，所以可以考虑二分法。计算并返回的平方根，其中是非负整数。输入输出说明的平方根是由于返回类型是整数，小数部分将被舍去。是一个非负整数，并且在位有符号整型的范围内。

有时候会抽时间看看题目，锻炼一下
简单记录下二分查找吧，会持续更新的啊哈~~~
仅供参考，路过看下就行，欢迎交流~

第35题

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。例如：
输入: [1,3,5,6], 5 输出: 2
输入: [1,3,5,6], 2 输出: 1
输入: [1,3,5,6], 7 输出: 4
输入: [1,3,5,6], 0 输出: 0

想法：简单粗暴一点，因为是排序数组，所以直接for遍历就可以了。

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        # 如果target大于max(nums),则直接插入最后位置
        for i in range(0,len(nums)):
            if nums[i] >= target:
                return i
        return len(nums)

但是若目标值若是最大的，则得等循环len(nums)遍才能找到，时间复杂度高。也因为是排序的数组，所以可以考虑二分法。

class Solution(object):
    def searchInsert(self, nums, target):
        left = 0
        right = len(nums)-1
        while left <= right :
            # 中间的数
            middle = (right-left) / 2 + left
            if nums[middle] == target:
                return middle
            elif nums[middle] > target : # 即target在左边
                right = middle - 1 
            else :
                left = middle + 1
        return left

第69题：x的平方根

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
输入: 8
输出: 2
说明: 8 的平方根是 2.82842...,

 由于返回类型是整数，小数部分将被舍去。

class Solution(object):
    def mySqrt(self, x):
        l, r = 0, x
        while l <= r:
            mid = l + (r-l)//2
            if mid * mid <= x < (mid+1)*(mid+1):
                return mid
            elif x < mid * mid:
                r = mid
            else:
                l = mid + 1

第367题：有效的完全平方数

给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
说明：不要使用任何内置的库函数，如 sqrt。
输入：16 输出：True
输入：14 输出：False

class Solution:
    def isPerfectSquare(self, num):
        """
        :type num: int
        :rtype: bool
        """
        left = 0
        right = num
        #tag = None
        while left <= right :
            mid = (right-left)//2  + left   # 减少循环次数
            val = mid *mid 
            if val == num :
                #tag = True
                return True
            elif val > num :
                #tag = False
                right = mid - 1 
            else:
                #tag = False
                left = mid + 1
        #return tag  
        # 注释掉部分减少运行时间，其次通过val来减少中间运算
        return False

第441题：排列硬币

你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内。
n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整，所以返回2.

n = 8
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因为第四行不完整，所以返回3.

class Solution(object):
    def arrangeCoins(self, n):
        if n == 0:
            return 0
        left = 1
        right = n/2
        while left <= right:
            mid = (right-left)/2+left
            total = (mid * (mid+1)) / 2
            if total > n:
                right = mid - 1
            elif n - total < mid + 1:
                return mid
            elif n-total == mid + 1:
                return mid+1
            else:
                left = left + 1
        return left

GPU云服务器云服务器二分查找二分查找代码二分法查找二分查找c语言实例

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/42387.html

大厂算法面试之leetcode精讲9.位运算

摘要：空间复杂度方法是否为最大的幂的约数思路最大的的幂为，判断是否是的约数即可。复杂度时间复杂度，一个整数统计二进制的复杂度，最坏的情况下是。大厂算法面试之leetcode精讲9.位运算视频教程（高效学习）:点击学习目录：1.开篇介绍2.时间空间复杂度3.动态规划4.贪心5.二分查找6.深度优先&广度优先7.双指针...

番茄西红柿 2021-11-29 10:50 评论0 收藏2637
LeetCode 之 JavaScript 解答第69题 —— X 的平方根（Squrt(x)）

摘要：测试用例输入输入输入负数的输入平方根为正整数的输入平方根为小数的代码实现写二分查找代码需要注意的三点循环退出条件。使用二分查找之前，判断问题是否满足二分查找的要求。 Time：2019/4/17Title: sqrt(x)Difficulty: EasyAuthor: 小鹿题目：sqrt(x) Implement int sqrt(int x). Compute and retu...

sf_wangchong 2019-08-23 17:00 评论0 收藏0
70道前端LeetCode题目集合及视频讲解（持续更新中...）

前端LeetCode刷题下面是已刷的题目的目录。GitHub：https://github.com/cunzaizhuy...每日打卡更新中，欢迎关注。数组类 26 删除排序数组中的重复项 27 移除元素 35 搜索插入位置 66 加1 80 medium 删除排序数组中的重复项2 88 合并两个有序数组 167 两数之和II - 输入有序数组 118 杨辉三角 169 easy 求众数 1...

mayaohua 2019-08-26 10:46 评论0 收藏0
大厂算法面试之leetcode精讲7.双指针

摘要：空间复杂度双指针，循环数组，较小的那个先向内移动如果高的指针先移动，那肯定不如当前的面积大计算面积更新最大面积相交链表方法哈希表思路将链表存入中，第一个相同的节点就是重合的节点复杂度时间复杂度，分别是两个链表的长度。大厂算法面试之leetcode精讲7.双指针视频教程（高效学习）:点击学习目录：1.开篇介绍2...

不知名网友 2021-11-26 11:11 评论0 收藏0