【数据结构与算法】二分查找题解(二)

news/2024/4/21 13:34:38/文章来源:https://blog.csdn.net/YZL40514131/article/details/136556259

在这里插入图片描述


这里写目录标题

  • 一、81. 搜索旋转排序数组 II
  • 二、167. 两数之和 II - 输入有序数组
  • 三、441. 排列硬币
  • 四、374. 猜数字大小
  • 五、367. 有效的完全平方数
  • 六、69. x 的平方根

一、81. 搜索旋转排序数组 II

中等
已知存在一个按非降序排列的整数数组 nums ,数组中的值不必互不相同。
在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转 ,使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ,请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ,则返回 true ,否则返回 false 。
你必须尽可能减少整个操作步骤。

示例 1:
输入:nums = [2,5,6,0,0,1,2], target = 0
输出:true

示例 2:
输入:nums = [2,5,6,0,0,1,2], target = 3
输出:false

class S81:def func(self, nums, target):left = 0right = len(nums) - 1while left <= right:mid = (left + right) // 2if nums[mid] == target:return Trueelif nums[mid] > nums[right]:if nums[mid] > target and target >= nums[left]:right = mid - 1else:left = mid + 1elif nums[mid] <= nums[right]:if nums[mid] < target and target <= nums[right]:left = mid + 1else:right = mid - 1return Falser = S81()
nums = [2, 5, 6, 0, 0, 1, 2]
target = 3
print(r.func(nums, target))

二、167. 两数之和 II - 输入有序数组

中等
给你一个下标从 1 开始的整数数组 numbers ,该数组已按 非递减顺序排列 ,请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ,则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ,而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。

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

示例 2:
输入:numbers = [2,3,4], target = 6
输出:[1,3]
解释:2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3:
输入:numbers = [-1,0], target = -1
输出:[1,2]
解释:-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

def func1(nums, target):left = 0right = len(nums) - 1while left < right:if nums[left] + nums[right] == target:return [left + 1, right + 1]elif nums[left] + nums[right] > target:right -= 1else:left += 1return [-1, -1]nums = [-1, 0]
target = -1
print(func1(nums=nums, target=target))

三、441. 排列硬币

简单
你总共有 n 枚硬币,并计划将它们按阶梯状排列。对于一个由 k 行组成的阶梯,其第 i 行必须正好有 i 枚硬币。阶梯的最后一行 可能 是不完整的。

给你一个数字 n ,计算并返回可形成 完整阶梯行 的总行数。
在这里插入图片描述
在这里插入图片描述
解题思路
1.二分查找,设立左右边界分别为1和n,每次取中间值mid为行数,将mid行总数和n对比
3.在不断的判定后如果硬币不能刚好分完,那么left会等于能分的最多行数+1,right会等于总量超出n的最小行数-1,即为能分的最多行数,

class S441:def func(self,n):left=1right=nwhile left<=right:mid=(left+right)//2if (1+mid)*mid//2<=n:left=mid+1else:right=mid-1return rightr=S441()
n=5
print(r.func(n))

四、374. 猜数字大小

简单
猜数字游戏的规则如下:
每轮游戏,我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了,我会告诉你,你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果,返回值一共有 3 种可能的情况(-1,1 或 0):

-1:我选出的数字比你猜的数字小 pick < num
1:我选出的数字比你猜的数字大 pick > num
0:我选出的数字和你猜的数字一样。恭喜!你猜对了!pick == num
返回我选出的数字。

示例 1:
输入:n = 10, pick = 6
输出:6

示例 2:
输入:n = 1, pick = 1
输出:1

示例 3:
输入:n = 2, pick = 1
输出:1

示例 4:
输入:n = 2, pick = 2
输出:2

调用预定义的接口guess来得到高了还是低了的信息,数字 范围是[1,n][1,n][1,n],直到猜中题目pick的数字。
运用二分查找,从范围[1,n][1,n][1,n]开始,不断的折半,调用guessguessguess,如果midmidmid高了,就往左半折,如果低了就往右半折,直到找到了

class S374:def func(self,n):start=1end=nwhile start<=end:mid=(start+end)//2ret=guess(mid)if ret==0:return midelif ret==1:start=mid+1else:end=mid-1r=S374()
n=10
print(r.func(n))

五、367. 有效的完全平方数

简单
给你一个正整数 num 。如果 num 是一个完全平方数,则返回 true ,否则返回 false 。
完全平方数 是一个可以写成某个整数的平方的整数。换句话说,它可以写成某个整数和自身的乘积。
不能使用任何内置的库函数,如 sqrt 。

示例 1:
输入:num = 16
输出:true
解释:返回 true ,因为 4 * 4 = 16 且 4 是一个整数。

示例 2:
输入:num = 14
输出:false
解释:返回 false ,因为 3.742 * 3.742 = 14 但 3.742 不是一个整数。

class S367:def func(self,num):l=1r=numwhile l<=r:mid=(l+r)//2if mid*mid==num:return Trueelif mid*mid>num:r=mid-1else:l=mid+1return False
r=S367()
num=14
print(r.func(num))

六、69. x 的平方根

简单
给你一个非负整数 x ,计算并返回 x 的 算术平方根 。
由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。
注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1:
输入:x = 4
输出:2

示例 2
输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842…, 由于返回类型是整数,小数部分将被舍去。

思路:二分查找

class S69:def func(self,x):left=0right=x     #任何数的平方根都小于本身ans=1while left<=right:mid=(left+right)//2if mid*mid==x:return midelif mid*mid<x:ans=midleft=mid+1else:right=mid-1return ansr=S69()
x=12
print(r.func(x))

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_997971.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

c++ 二分查找(迭代与递归)

二分搜索被定义为一种在排序数组中使用的搜索算法&#xff0c;通过重复将搜索间隔一分为二。二分查找的思想是利用数组已排序的信息&#xff0c;将时间复杂度降低到O(log N)。 二分查找算法示例 何时在数据结构中应用二分查找的条件&#xff1a; 应用二分查找算法&#xff1a;…

(C语言)sizeof和strlen的对比(详解)

sizeof和strlen的对⽐&#xff08;详解&#xff09; 1. sizeof sizeof是用来计算变量所占内存空间大小的&#xff0c; 单位是字节&#xff0c;如果操作数是类型的话&#xff0c;计算的是用类型创建的变量所占空间的大小。 sizeof 只关注占用内存空间的大小 &#xff0c;不在乎内…

Rust结构体讲解学习,以及impl结构体方法和结构体关联函数

Rust 中的结构体&#xff08;Struct&#xff09;与元组&#xff08;Tuple&#xff09;都可以将若干个类型不一定相同的数据捆绑在一起形成整体&#xff0c;但结构体的每个成员和其本身都有一个名字&#xff0c;这样访问它成员的时候就不用记住下标了。元组常用于非定义的多值传…

表单提交 滚动到必填校验位置

handleCommit(flag) {this.$refs["form"].validate((valid, object) > {if (valid) {this.form.checkState flag;this.form.checkLevel 1;this.form.type 1; //规划this.form.filingsId this.form.id;checkFilings(this.form).then((response) > {this.$mo…

list链表的创建,排序,插入, test ok

1. 链表的建立&#xff0c;打印 #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <stack> #include <iostream> #include <string.h> #include <string>using namespace std;struct node {int data;s…

后量子时代,未来密码该何去何从?

古有飞鸽&#xff0c;现有网络&#xff0c;在知识经济为基础的信息化社会中&#xff0c;保障网络信息安全无疑成为成为国与国之间无形的较量。小到个人通讯&#xff0c;大到机要信息传输&#xff0c;信息安全对于国家安全和经济活动正常运转至关重要。密码学作为保障网络与信息…

Windows®、Linux® 和 UNIX® 系统都适用的远程桌面工具 OpenText ETX

Windows、Linux 和 UNIX 系统都适用的远程桌面工具 OpenText ETX 为 Windows、Linux 和 UNIX 实施精益、经济高效的虚拟化&#xff1b;提供完整的远程 Windows 可用性&#xff1b;以类似本地的性能远程工作&#xff1b;安全地保护系统和知识产权&#xff08;IP&#xff09;&am…

什么是TikTok账号权重?打破TikTok0播放的方法

许多TikTok账号运营者都会遇到一个难题&#xff0c;那就是视频要么播放量很低&#xff0c;要么0播放&#xff01;不管内容做的多好&#xff0c;最好都是竹篮打水一场空&#xff01;其实你可能忽略了一个问题&#xff0c;那就是账号权重。下面好好跟大家讲讲这个东西&#xff01…

【kubernetes】关于k8s集群的配置资源(configmap和secret)

目录 一、Secret 类型一&#xff1a;kubernetes.io/service-account-token 类型二&#xff1a;普通类型secret&#xff0c; ●Opaque&#xff0c;base64 编码格式的 Secret&#xff0c;用来存储用户自定义的密码、密钥等&#xff0c;默认的 Secret 类型; 类型三&#xff1a;…

【数据结构】二、线性表:6.顺序表和链表的对比不同(从数据结构三要素讨论:逻辑结构、物理结构(存储结构)、数据运算(基本操作))

文章目录 6.对比&#xff1a;顺序表&链表6.1逻辑结构6.2物理结构&#xff08;存储结构&#xff09;6.2.1顺序表6.2.2链表 6.3数据运算&#xff08;基本操作&#xff09;6.3.1初始化6.3.2销毁表6.3.3插入、删除6.3.4查找 6.对比&#xff1a;顺序表&链表 6.1逻辑结构 顺…

管理技巧 | 提升团队效能:如何与下属进行有效沟通

本文节选霍格沃兹测试开发学社沟通管理公开课- 某外企PMO Angelia老师的分享 在日常的管理工作中&#xff0c;沟通作为一项基础而关键的技能&#xff0c;往往决定了团队的协作效率和目标达成率。作为一个曾经从基层员工一路成长为管理者的Angelia老师&#xff0c;深知沟通的艺术…

jmap-各种option参数说明

基本情况 jmap&#xff08;JVM Memory Map&#xff09;&#xff1a;作用一方面是获取dump文件&#xff08;堆转储快照文件&#xff0c;二进制文件&#xff09;&#xff0c;它还可以获取目标Java进程的内存相关信息&#xff0c;包括Java堆各区域的使用情况、堆中对象的统计信息…

国家妇女节放假是法定的假日

在这个充满活力和希望的春天&#xff0c;我们迎来了一个特殊的节日——国家妇女节。这是一个属于所有女性的节日&#xff0c;是一个庆祝女性成就、关爱女性权益的时刻。在这个特殊的日子里&#xff0c;我们不禁要问&#xff1a;国家妇女节放假是法定假日吗&#xff1f;让我们一…

ChatGPT数据分析应用——漏斗分析

ChatGPT数据分析应用——漏斗分析 ​ 漏斗分析在数据分析中也比较常用&#xff0c;主要是用于发现各个转化流程中哪个环节有问题。接下来我们让ChatGPT解释这个方法的概念并提供相应的案例。发送如下内容给ChatGPT。 ​ ChatGPT收到上述内容后&#xff0c;返回如下结果。 漏斗…

MutationObserver详解

1.基于之前Chrome游览器插件开发的过程中&#xff0c;会遇到在插件控制台打印被安游览器页面的元素&#xff0c;一直未解决。后来找到了解决了办法可以使用MutationObserver&#xff1b;使用MutationObserver这个可以在被安游览器页面直接打印页面元素等等&#xff0c;可能你会…

【电路笔记】-RC网络-时间常数

时间常数 文章目录 时间常数1、概述2、RC 电路的时间常数3、示例14、示例25、RC瞬态放电曲线6、示例37、总结Tau τ \tau τ 是 RC 电路在阶跃变化输入条件下从一种稳态条件变为另一种稳态条件所需的时间常数。 1、概述 Tau,符号 τ \tau τ,是电气和电子计算中使用的希腊字…

【翻译】零信任架构准则(五)Don‘t trust any network

将监控重点放在用户&#xff0c;设备和服务上 全面监控必不可少&#xff0c;因为设备和服务更容易受到网络攻击。在零信任架构中&#xff0c;随着设备&#xff0c;服务和用户行为的持续评估&#xff0c;我们的监控策略很可能发生改变。我们应该持续进行监控&#xff0c;并将用…

基于uniapp cli项目开发的老项目,运行报错path.replace is not a function

项目&#xff1a;基于uniapp cli的微信小程序老项目 问题&#xff1a;git拉取代码&#xff0c;npm安装包时就报错&#xff1b; cnpm能安装成功包&#xff0c;运行报错 三种方法尝试解决&#xff1a; 更改代码&#xff0c;typeof pathstring的话&#xff0c;才走path.replace…

wpf prism左侧抽屉式菜单

1.首先引入包MaterialDesignColors和MaterialDesignThemes 2.主页面布局 左侧菜单显示在窗体外&#xff0c;点击左上角菜单图标通过简单的动画呈现出来 3.左侧窗体外菜单 <Grid x:Name"GridMenu" Width"150" HorizontalAlignment"Left" Ma…

1.2_2 OSI参考模型

文章目录 1.2_2 OSI参考模型一、概述&#xff08;一&#xff09;ISO/OSI参考模型是怎么来的&#xff1f;&#xff08;二&#xff09;ISO/OSI参考模型&#xff08;三&#xff09;ISO/OSI参考模型解释通信过程 二、各层功能及协议&#xff08;一&#xff09;应用层&#xff08;第…