当前位置: 首页 > news >正文

算法刷题【二分法】

题目:

在这里插入图片描述
在这里插入图片描述

  • 注意题目中说明了数据时非递减的,那么这样就存在二分性,能够实现logn的复杂度。
  • 二分法每次只能取寻找特定的某一个值,所以我们要分别求左端点和有端点。

分析第一组用例得到结果如下:
在这里插入图片描述
成功找到左端点8


由此可知,用二分法去寻找左端端点的时候:

  • num[mid]<target,那么此时mid的左边包括自身的值都小于target,所以直接执行赋值操作left = mid + 1即可。

  • num[mid]= =target的时候,由于可能此时的mid已经是左端端点了。但是只是可能是左端点了,也有可能不是左端点,所以相等的情况就要和大于的情况合并起来操作,执行right = mid操作。

  • num[mid]>target的时候,mid的右边包括自身都比target的值要大,执行right = mid具有合理性,不能执行right = mid -1因为此时和等于合并起来了,判断条件变成是num[mid] <= target在等于的情况下,可能成为左端的端点。
    图示*😗
    在这里插入图片描述
    上述就是找最左边的端点的基本思路了,但是我们还有一些细节需要处理:

  • 对于每次mid位置的取发:
    1:mid = left + (right-left)/2
    2:mid = left + (right-left +1)/2
    有以上两种取法,前后者在奇数的情况下相同,但是在偶数的情况下就会有所不同。
    偶数的情况下,1会取到中间两个数的片左边的那一个,2会取到中间两个数的偏右边那一个。

对于取左边端点来说:

到最终可能会有这么一种的情况:
在这里插入图片描述
所以在用二分法寻找左侧端点的时候,应该要使用mid的第一种取法(mid = left + (right-left)/2 )。

相关文章:

算法刷题【二分法】

题目&#xff1a; 注意题目中说明了数据时非递减的&#xff0c;那么这样就存在二分性&#xff0c;能够实现logn的复杂度。二分法每次只能取寻找特定的某一个值&#xff0c;所以我们要分别求左端点和有端点。 分析第一组用例得到结果如下: 成功找到左端点8 由此可知&#xff0…...

.NET MAUI Sqlite程序应用-数据库配置(一)

项目名称:Ownership&#xff08;权籍信息采集&#xff09; 一、安装 NuGet 包 安装 sqlite-net-pcl 安装 SQLitePCLRawEx.bundle_green 二、创建多个表及相关字段 Models\OwnershipItem.cs using SQLite;namespace Ownership.Models {public class fa_rural_base//基础数据…...

基于WPF技术的换热站智能监控系统09--封装水泵对象

1、添加用户控件 2、编写水泵UI 控件中用到了Viewbox控件&#xff0c;Viewbox控件是WPF中一个简单的缩放工具&#xff0c;它可以帮助你放大或缩小单个元素&#xff0c;同时保持其宽高比。通过样式和属性设置&#xff0c;你可以创建出既美观又功能丰富的用户界面。在实际开发中…...

GLM+vLLM 部署调用

GLMvLLM 部署调用 vLLM 简介 vLLM 框架是一个高效的大型语言模型&#xff08;LLM&#xff09;推理和部署服务系统&#xff0c;具备以下特性&#xff1a; 高效的内存管理&#xff1a;通过 PagedAttention 算法&#xff0c;vLLM 实现了对 KV 缓存的高效管理&#xff0c;减少了…...

leetcode 122 买卖股票的最佳时机||(动态规划解法)

题目分析 题目描述的已经十分清楚了&#xff0c;不做过多阐述 算法原理 状态表示 我们假设第i天的最大利润是dp[i] 我们来画一下状态机 有两个状态&#xff0c;买入后和卖出后&#xff0c;我们就可以使用两个dp表来解决问题 f[i]表示当天买入后的最大利润 g[i]表示当天卖出…...

C++设计模式---组合模式

1、介绍 组合模式&#xff08;Composite&#xff09;是一种结构型设计模式&#xff0c;也被称为部分-整体模式。它将复杂对象视为由多个简单对象&#xff08;称为“组件”&#xff09;组成的树形结构&#xff0c;这些组件能够共享相同的行为。每个组件都可能包含一个或多个子组…...

工厂方法模式(大话设计模式)C/C++版本

工厂方法模式 C 参考&#xff1a;https://www.cnblogs.com/Galesaur-wcy/p/15926711.html #include <iostream> #include <memory> using namespace std;// 运算类 class Operation { private:double _NumA;double _NumB;public:void SetNumA(){cout << &…...

[NCTF 2018]flask真香

打开题目后没有提示框&#xff0c;尝试扫描后也没有什么结果&#xff0c;猜想是ssti。所以尝试寻找ssti的注入点并判断模版。 模版判断方式&#xff1a; 在url地址中输入{7*7} 后发现不能识别执行。 尝试{{7*7}} ,执行成功&#xff0c;继续往下走注入{{7*7}}&#xff0c;如果执…...

性能测试3【搬代码】

1.Linux服务器性能分析命令及详解 2.GarafanainfluxDB监控jmeter数据 3.GarafanaPrometheus监控服务器和数据库性能 4.性能瓶颈分析以及性能调优方案详解 一、无界面压测时&#xff0c; top load average:平均负载 htop 二、Garafana监控平台 传统项目&#xff1a;centosphpm…...

<tesseract><opencv><Python>基于python和opencv,使用ocr识别图片中的文本并进行替换

前言 本文是在python中,利用opencv处理图片,利用tesseractOCR来识别图片中的文本并进行替换的一种实现方法。 环境配置 系统:windows 平台:visual studio code 语言:python 库:pyqt5、opencv、tesseractOCR 代码介绍 本文程序功能实现,主要依赖于tesseractOCR这个库,…...

海南云亿商务咨询有限公司解锁抖音电商新纪元

在当今数字化浪潮中&#xff0c;抖音电商以其独特的魅力和强大的用户基础&#xff0c;迅速成为企业营销的新宠。海南云亿商务咨询有限公司&#xff0c;作为专注于抖音电商服务的领先企业&#xff0c;凭借专业的团队和丰富的经验&#xff0c;为众多企业提供了高效、精准的电商服…...

arm64架构 统信UOS搭建PXE无盘启动Linux系统(麒麟桌面为例)

arm64架构 统信UOS搭建PXE无盘启动Linux系统&#xff08;麒麟桌面为例&#xff09; 搞了好久搞得头疼哎 1、准备服务器UOS服务器 准备服务IP 这里是192.168.1.100 1.1、安装程序 yum install -y dhcp tftp tftp-server xinetd nfs-utils rpcbind 2、修改配置 2.1、修改dhcpd.c…...

SpringBoot 实现 阿里云语音通知(SingleCallByTts)

目录 一、准备工作1.开通 阿里云语音服务2.申请企业资质3.创建语音通知模板&#xff0c;审核通过4.调用API接口---SingleCallByTts5.调试API接口---SingleCallByTts 二、代码实现1.导入依赖 com.aliyun:aliyun-java-sdk-dyvmsapi:3.0.22.创建工具类&#xff0c;用于发送语音通知…...

IDEA 连接GitHub仓库并上传项目(同时解决SSH问题)

目录 1 确认自己电脑上已经安装好Git 2 添加GitHub账号 2.1 Setting -> 搜索GitHub-> ‘’ -> Log In with Token 2.2 点击Generate 去GitHub生成Token 2.3 勾选SSH后其他不变直接生成token 2.4 然后复制token添加登录账号即可 3 点击导航栏中VCS -> Create…...

vue/react/js 常用的原生获取当前页面的url网址的相关方法

目录 第一章 场景 第二章 总结 第一章 场景 最近实现需求时遇到这么一种情况&#xff1a; 本地url —— 线上url —— 需求&#xff1a;需要将token清除掉 注意事项&#xff1a;token不是#/后面的参数&#xff0c;说明并不是我们前端返回的&#xff0c;vue路由的方法使用不…...

java-final 关键字

## Java中的final关键字 ### 1. final关键字的基本概念 final是Java中一个非常重要的关键字&#xff0c;用于声明常量、阻止继承和重写&#xff0c;确保类、方法和变量的不可变性。具体来说&#xff0c;final关键字可以用来修饰类、方法和变量&#xff08;包括成员变量和局部…...

ARM32开发--IIC软实现

知不足而奋进 望远山而前行 目录 文章目录 前言 开发流程 GD32F4软件I2C初始化 GD32F4软件I2C引脚功能 写操作 读操作 总结 前言 在嵌入式系统开发中&#xff0c;软件实现的I2C通信协议扮演着至关重要的角色。本文将深入探讨如何在GD32F4系列微控制器上实现软件I2C功能…...

在有向无环图(DAG)中实现拓扑排序与最短路径和最长路径算法

有向无环图&#xff08;DAG&#xff09;是一类非常重要的图结构&#xff0c;广泛应用于任务调度、数据依赖分析等领域。本文将介绍如何在DAG中实现拓扑排序、单源最短路径和单源最长路径算法&#xff0c;并提供完整的Java代码示例。 图结构定义 首先&#xff0c;我们定义一个…...

SQLServer按照年龄段进行分组查询数据

1.按照年龄段对数据进行分组&#xff0c; 将人群分为&#xff1a;青年&#xff0c;中年&#xff0c;老年三种类型&#xff0c;人群类型加上其他分组字段如&#xff1a;性别&#xff0c;进行多条件分组,统计各个年龄段多少人 Select case sex when 1 then ‘男’ when 2 then …...

开放式耳机哪个品牌质量比较好?2024高性价比机型推荐!

随着音乐技术的不断发展&#xff0c;开放式耳机已成为音乐发烧友们的另外一种选择。从最初的简单音质&#xff0c;到如今的高清解析&#xff0c;开放式耳机不断进化升级。音质纯净&#xff0c;佩戴舒适&#xff0c;无论是街头漫步还是家中放松时候&#xff0c;都能带给你身临其…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

【 java 虚拟机知识 第一篇 】

目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...

STM32标准库-ADC数模转换器

文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”&#xff1a;输入模块&#xff08;GPIO、温度、V_REFINT&#xff09;1.4.2 信号 “调度站”&#xff1a;多路开关1.4.3 信号 “加工厂”&#xff1a;ADC 转换器&#xff08;规则组 注入…...

Qt 按钮类控件(Push Button 与 Radio Button)(1)

文章目录 Push Button前提概要API接口给按钮添加图标给按钮添加快捷键 Radio ButtonAPI接口性别选择 Push Button&#xff08;鼠标点击不放连续移动快捷键&#xff09; Radio Button Push Button 前提概要 1. 之前文章中所提到的各种跟QWidget有关的各种属性/函数/方法&#…...

设计模式-3 行为型模式

一、观察者模式 1、定义 定义对象之间的一对多的依赖关系&#xff0c;这样当一个对象改变状态时&#xff0c;它的所有依赖项都会自动得到通知和更新。 描述复杂的流程控制 描述多个类或者对象之间怎样互相协作共同完成单个对象都无法单独度完成的任务 它涉及算法与对象间职责…...

LeetCode 2894.分类求和并作差

目录 题目&#xff1a; 题目描述&#xff1a; 题目链接&#xff1a; 思路&#xff1a; 思路一详解&#xff08;遍历 判断&#xff09;&#xff1a; 思路二详解&#xff08;数学规律/公式&#xff09;&#xff1a; 代码&#xff1a; Java思路一&#xff08;遍历 判断&a…...

Java求职者面试:微服务技术与源码原理深度解析

Java求职者面试&#xff1a;微服务技术与源码原理深度解析 第一轮&#xff1a;基础概念问题 1. 请解释什么是微服务架构&#xff0c;并说明其优势和挑战。 微服务架构是一种将单体应用拆分为多个小型、独立的服务的软件开发方法。每个服务都运行在自己的进程中&#xff0c;并…...

使用高斯朴素贝叶斯算法对鸢尾花数据集进行分类

高斯朴素贝叶斯算法通常用于特征变量是连续变量&#xff0c;符合高素分布的情况。 使用高斯朴素贝叶斯算法对鸢尾花数据集进行分类 """ 使用高斯贝叶斯堆鸢尾花进行分类 """ #导入需要的库 from sklearn.datasets import load_iris from skle…...