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

随想录二刷(数组二分法)leetcode 704 35 34 69 367

第一题 leetcode 704.二分查找

在这里插入图片描述

二分法的思路

二分法的思路很简单

  • 数组必须有序
  • 先查找中间元素进行比较
  • 得出大小再考虑向左比较还是向右比较

代码实现

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;int middle = 0;while(left<=right){middle = left + (right - left) /  2;if(nums[middle]==target){return middle;}else if(nums[middle] < target){left = middle + 1;}else{right = middle - 1;}}return -1;}
};

结果如下

在这里插入图片描述

第二题 leetcode 35.搜索插入位置

题目描述

在这里插入图片描述

题目分析

和704题的比较如下

  • 依旧需要返回可以搜到的下标
  • 704搜不到返回-1 本题返回可以插入的位置

代码示例

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;int middle = 0;while(left <= right){middle = left + (right - left) / 2;if(nums[middle]==target){return middle;}else if(nums[middle] < target){left = middle + 1;}else{right = middle - 1;}}// 为何返回left的原因有以下几点// 我们需要返回一个正确的有序位置 而且计算到最后返回-1 的时候 已有三个参数 left,middle, rightreturn left;}
};

明确eft的原因从以下几点来看

  • while的限制条件是left大于right的时候,那么一旦找不到righ会-1导致left大于right退出while循环
  • 此时left的位置就是要插入的位置

第三题 leetcode 34.

题目描述

在这里插入图片描述

分析

核心就是当边界结束的时候left代表的是什么

代码实现

class Solution {
private:int board(vector<int>& nums, int target){int left = 0;int right = nums.size() - 1;int middle = 0;while(left<=right){middle = left + (right-left) / 2;if(nums[middle]<target){left = middle + 1;}else{right = middle - 1;}}return left;// 返回左边界 即可以查找到的第一个数的位置}
public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> res={-1, -1};int start = board(nums, target);// 排除三种情况if(nums.size()==0 || nums[nums.size()-1] < target || nums[start]!=target){return res;}int end = board(nums, target+1)-1;res.clear();res.push_back(start);res.push_back(end);return res;}
};

第四题 leetcode 69

题目描述

在这里插入图片描述

分析

说白了也是搜素 只是现在需要不保留小数的
那么搜素结束之后的right即是较小的那一个,另外将特殊情况排除一下

代码实现

class Solution {
public:int mySqrt(int x) {int left = 0;int right = x;int middle = 0;if(x==0){return 0;}if(x==1){return 1;}while(left<=right){middle = left + (right-left) / 2;if(x/middle > middle){left = middle + 1;}else if(x/middle == middle){return middle;}else{right = middle - 1;}}return right;}
};

第五题 leetcode 367.

题目描述

在这里插入图片描述

代码实现

class Solution {
public:bool isPerfectSquare(int num) {int left = 1;int right = num;int middle = 0;if(num==1){return true;}while(left<=right){middle = left + (right-left) / 2;if(num/middle > middle){left = middle + 1;}else if((num%middle==0) && (num/middle==middle)){	// 来进行判断是否是平方return true;}else{right = middle - 1;}}return false;}
};

相关文章:

随想录二刷(数组二分法)leetcode 704 35 34 69 367

第一题 leetcode 704.二分查找 二分法的思路 二分法的思路很简单 数组必须有序先查找中间元素进行比较得出大小再考虑向左比较还是向右比较 代码实现 class Solution { public:int search(vector<int>& nums, int target) {int left 0;int right nums.size() -…...

【微信小程序】--WXML WXSS JS 逻辑交互介绍(四)

&#x1f48c; 所属专栏&#xff1a;【微信小程序开发教程】 &#x1f600; 作  者&#xff1a;我是夜阑的狗&#x1f436; &#x1f680; 个人简介&#xff1a;一个正在努力学技术的CV工程师&#xff0c;专注基础和实战分享 &#xff0c;欢迎咨询&#xff01; &#…...

c/c++开发,无可避免的模板编程实践(篇八)

一、借用标准库模板构造自己的模板 通常&#xff0c;模板设计是遵循当对象的类型不影响类中函数的行为时就使用模板。这也就是为何标准库提供大部分的模板都是与容器、迭代器、适配器、通用算法等有关&#xff0c;因为这些主要是除了对象集合行为&#xff0c;如读写、增删、遍历…...

Leetcode13. 罗马数字转整数

一、题目描述&#xff1a; 罗马数字包含以下七种字符&#xff1a; I&#xff0c; V&#xff0c; X&#xff0c; L&#xff0c;C&#xff0c;D 和 M。 字符数字I1V5X10L50C100D500M1000 例如&#xff0c; 罗马数字 2 写做 II &#xff0c;即为两个并列的 1。12 写做 XII &…...

元宇宙对营销方式的影响

营销方式的变化通常伴随着技术的发展。我们已经看到营销方式从印刷媒体、电视、广播到互联网的转变。而现在&#xff0c;我们又处在下一个营销方式大跃进的风口浪尖上。关于元宇宙及其潜在的变革性影响&#xff0c;人们已经讨论了很多。虽然与元宇宙相关的大多数东西在很大程度…...

PERCCLI命令行程序说明

Dell EMC PowerEdge RAID控制器(PERC)命令行界面(CLI)实用程序用于管理RAID卡相关的配置和信息&#xff0c;命令的子命令和选项如下所示&#xff1a; help - lists all the commands with their usage. E.g. perccli help <command> help - gives details about a parti…...

系统架构——分布式架构负载均衡系统设计实战

摘要 关于“负载均衡”的解释&#xff0c;百度词条里&#xff1a;负载均衡&#xff0c;英文叫Load Balance&#xff0c;意思就是将请求或者数据分摊到多个操作单元上进行执行&#xff0c;共同完成工作任务。负载均衡&#xff08;Load Balance&#xff09;建立在现有网络结构之…...

机器学习算法: AdaBoost 详解

1. 集成学习概述 1.1. 定义 集成学习&#xff08;Ensemble learning&#xff09;就是将若干个弱分类器通过一定的策略组合之后产生一个强分类器。 弱分类器&#xff08;Weak Classifier&#xff09;指的就是那些分类准确率只比随机猜测略好一点的分类器&#xff0c;而强分类器&…...

6.824lab1总结

目录总体概要核心结构体coordinator思路&#xff1a;任务池管理RPC函数worker思路:实现细节总体概要 程序主要由mrcoordinator.go、mrworker.go为启动模块。 mrcoordinator.go: 启动rpc服务&#xff0c;循环等待m.Done()为true时退出。mrwoker.go:调用mr.worker(mapf, reduce…...

NIO蔚来 面试——IP地址你了解多少?

目录 前言 1、IP地址 1.1、什么是IP地址 1.2、IP地址的格式 1.2.1、32位二进制数表示IP地址&#xff0c;够用吗&#xff1f; 1.3、IP地址的组成 1.4、为什么会出现IPv6 1.4.1、为什么IPv6还没有大量普及呢&#xff1f; 1.5、子网掩码 1.6、特殊的IP地址 2、路由选择 …...

Gluten 首次开源技术沙龙成功举办,更多新能力值得期待

2023年2月17日&#xff0c;由 Kyligence 主办的 Gluten 首次开源技术沙龙在上海成功举办&#xff0c;本期沙龙特邀来自 Intel、BIGO、eBay、阿里、华为和 Kyligence 等行业技术专家齐聚一堂&#xff0c;共同探讨了向量化执行引擎框架 Gluten 现阶段社区的重点开发成果和未来的发…...

springboot+redis+lua实现限流

Redis 除了做缓存&#xff0c;还能干很多很多事情&#xff1a;分布式锁、限流、处理请求接口幂等性。。。太多太多了&#xff5e;今天想和小伙伴们聊聊用 Redis 处理接口限流。1. 准备工作首先我们创建一个 Spring Boot 工程&#xff0c;引入 Web 和 Redis 依赖&#xff0c;同时…...

线段树总结

文章目录参考文档题目线段树实现单点修改&#xff0c;区间求值模板题目308. 二维区域和检索 - 可变区间修改&#xff0c;区间求值1. 掉落的方块&#xff08;区间开点&#xff09;2. 维护序列3. 一个简单的问题24. 天际线问题动态开点1. 区间和个数(单点修改开点)问题以及注意事…...

龙芯GS232(MIPS 32)架构cache管理笔记

1 mips32架构 MIPS架构是一种基于精简指令集&#xff08;Reduced Instruction Set Computer&#xff0c;RISC&#xff09;的计算机处理器架构。MIPS架构由MIPS Technologies公司在1981年开发&#xff0c;并在1984年发布了第一款MIPS处理器。 MIPS架构的特点包括&#xff1a; …...

js去重

<script>let arr [{ id: 0, name: "张三" },{ id: 1, name: "李四" },{ id: 2, name: "王五" },{ id: 3, name: "赵六" },{ id: 1, name: "孙七" },{ id: 2, name: "周八" },{ id: 2, name: "吴九&qu…...

小白都能看懂的C语言入门教程

文章目录C语言入门教程1. 第一个C语言程序HelloWorld2. C语言的数据类型3. 常量变量的使用4. 自定义标识符#define5. 枚举的使用6. 字符串和转义字符7. 判断和循环8. 函数9. 数组的使用10. 操作符的使用11. 结构体12. 指针的简单使用C语言入门教程 1. 第一个C语言程序HelloWor…...

leetcode 21~30 学习经历

leetcode 21~30 学习经历21. 合并两个有序链表22. 括号生成23. 合并K个升序链表24. 两两交换链表中的节点25. K 个一组翻转链表26. 删除有序数组中的重复项27. 移除元素28. 找出字符串中第一个匹配项的下标29. 两数相除30. 串联所有单词的子串小结21. 合并两个有序链表 将两个升…...

让ArcMap变得更加强大,用python执行地理处理以及编写自定义脚本工具箱

文章目录一、用python执行地理处理工具1.1 例&#xff1a;乘以0.00011.2 例&#xff1a;裁剪栅格1.3 哪里查看调用某工具的代码&#xff1f;二、用python批量执行地理处理工具2.1 必需的python语法知识for循环语句缩进的使用注释的使用2.2 一个批处理栅格的代码模板三、创建自定…...

SAP 项目实施阶段全过程

在sap实施项目的周期和步骤上&#xff0c;根据各公司对业务的理解不同&#xff0c;也被划分为各个阶段&#xff0c;但其中由普华永道提出的分七步走&#xff0c;个人觉得对刚进入这一行业的人很有帮助&#xff0c;接下来一起分享和讨论下&#xff1a; sap实施项目生命周期&…...

idea中的Maven导包失败问题解决总结

idea中的Maven导包失败问题解决总结 先确定idea和Maven 的配置文件settings 没有问题 找到我们本地的maven仓库&#xff0c;默认的maven仓库路径是在\C:\Users\用户名.m2下 有两个文件夹&#xff0c;repositotry是放具体jar包的&#xff0c;根据报错包的名&#xff0c;找对应文…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

Oracle查询表空间大小

1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

【C++】纯虚函数类外可以写实现吗?

1. 答案 先说答案&#xff0c;可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...