IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 二分查找核心思路解析与Leetcode相关题解(python,二分数值型) -> 正文阅读

[数据结构与算法]二分查找核心思路解析与Leetcode相关题解(python,二分数值型)

二分查找的讲解请见上一篇文章。本文主要记录对数值进行二分的题目解法与思路。

374. 猜数字大小

class Solution:
    def guessNumber(self, n: int) -> int:
        left = 1
        right = n
        while left < right:
            mid = left + (right - left) // 2
            if guess(mid) == 1: # mid < pick
                left = mid + 1
            else:
                right = mid
        return left

正常二分思路。

702. 搜索长度未知的有序数组

class Solution:
    def search(self, reader, target):
        """
        :type reader: ArrayReader
        :type target: int
        :rtype: int
        """
        left, right = 0, 10000 # 英文官方有范围
        while left < right:
            mid = left + (right - left) // 2
            if reader.get(mid) < target:
                left = mid + 1
            else:
                right = mid
        
        return left if reader.get(left) == target else -1

基本思路一致,长度未知的情况下 right 设为最大值10000(英文官方的条件),然后二分查找,最后找到目标值则返回下标,没有则返回 -1。

287. 寻找重复数

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        left = 1
        right = len(nums) - 1
        while left < right:
            mid = left + (right - left) // 2 
            cnt = 0 # 记录小于等于mid的元素个数
            for num in nums:
                if num <= mid:
                    cnt += 1
            if cnt > mid:
                right = mid
            else:
                left = mid + 1
        return left

这题给定一个包含 n + 1 个整数的数组,其数字都在 1 到 n 之间,只有一个数字是重复的。因此,对于某个数字 x 来说,正常来说小于等于 x 的数字应该有 x 个,例如有1、2、3、4共4个数字小于等于4,如果大于4了,则说明1、2、3、4其中有一个数字重复了,所以右边界左移,反之左边界右移。

69. x 的平方根

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        if x == 1:
            return 1

        left, right = 1, x // 2
        while left < right:
            mid = left + (right - left + 1) // 2
            if mid > x / mid: # mid的平方大于x就肯定不是平方根,等于一定是,小于可能是
                right = mid - 1
            else:
                left = mid
                
        return left

这题只能用分法二,因为题目要求直接舍弃小数部分,所以若平方根为分数,其两边的整数,我们应该取较小的一个,只有分法二符合条件,剩余两个元素时,需要 mid 指向 right,然后最后取值为 left。

367. 有效的完全平方数

class Solution:
    def isPerfectSquare(self, num: int) -> bool:
        if num == 1:
            return True

        left, right = 0, num // 2
        while left < right:
            mid = left + (right - left) // 2
            if mid < num / mid:
                left = mid + 1
            else:
                right = mid

        return True if left * left == num else False

比上一题简单一点,用分法一即可,不停寻找平方大于等于 num 的区间,得到第一个平方大于等于 num 的数字,若该数字平方正好是 num 则为平方根,否则不是。

1300. 转变数组后最接近目标值的数组和

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr.sort()
        s, n = 0, len(arr)
        for i in range(len(arr)):
            avg = (target - s) / (n - i)
            if avg < arr[i]: # 均值小于当前值arr[i](以及后面的值),即value为均值可以让arr[i]到arr[n]的值变为均值
                return int(avg + 0.49)   #五舍六入,若为int(avg)会向下取整,直接截断
            s += arr[i]
        return arr[-1]

首先对数组进行排序,由小到大,然后我们思考,对于如[1, 2, 3, 4, 5]这样的数组,如果取value = 1,则数组为[1, 1, 1, 1, 1],如果取value = 2,数组为[1, 2, 2, 2, 2],即 value 的取值越大,数组和越大。因此,我们要让value从小到大,直到找到一个 value 使得数组和与 target 最为接近。

遍历数组,对于第i个元素,其之前的元素和为 s,剩下的元素如果能使得绝对值为0,一定等于(target - s) / (n - i) = avg,但是这个 avg 不一定出现在位置 i ,除非有 avg < arr[i]。

当位置i及其后面的元素可以变成avg时,如果出现 3.5 这种恰好在中间的数,无论取整为3或者4对于绝对值来说都是一样的,但是题目要求数尽量小,所以 3.5 应取整为3,而 3.51 就要取为4了,因此是五舍六入。int(avg)是直接截断,向下取整;int(avg + 0.5)是四舍五入;int(avg + 0.49)就是五舍六入。

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-07-26 12:18:24  更:2021-07-26 12:19:40 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/27 9:46:24-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计