C++算法第九天

本篇文章我们继续学习c++算法

目录

第一题

题目链接

题目展示

代码原理

暴力解法

二分解法

代码编写

第二题

题目链接

题目展示

代码原理

代码编写

重点回顾

朴素二分

非朴素二分

重点一

重点二

重点三


第一题

题目链接

153. 寻找旋转排序数组中的最小值 - 力扣(LeetCode)

题目展示

代码原理

图1

从图1中我们将4567分为一组,012分为另一组,并且以2为参照点,从而有了图1中类似数学中的分段函数的图,从这个图中我们可以看到有明显的二段性,因此,我们就可以使用二分查找进行解题。那么在讲解二分算法之前,我们先来讲解一下这个暴力解法

暴力解法

依次遍历,最后取得最小值并返回即可

二分解法

代码编写

class Solution {

public:

    int findMin(vector<int>& nums) {

        int left = 0, right = nums.size() - 1;

        int x = nums[right];

        while(left < right)

        {

            int mid = left + (right - left) / 2;

            if(nums[mid] > x)

            left = mid + 1;

            else

            right = mid;

        }

        return nums[right];

    }

};

第二题

题目链接

LCR 173. 点名 - 力扣(LeetCode)

题目展示

代码原理

代码编写

class Solution {

public:

    int findMin(vector<int>& nums) {

        int left = 0, right = nums.size() - 1;

        int x = nums[right];

        while(left < right)

        {

            int mid = left + (right - left) / 2;

            if(nums[mid] > x)

            left = mid + 1;

            else

            right = mid;

        }

        return nums[right];

    }

};

总结

其实从这道题中,我们可以发现这题的二段性并不是和之前一样是大小关系了,而是等于下标和不等于下标的关系了,因此我们在学习的时候不能把一个知识点学死了,随机应变才是上策

那么二分查找的到这里就已经结束了,我们最后再来回顾一下二分查找的重点

重点回顾

朴素二分

先根据最初的left和right指针计算出mid指针,再将[mid]与目标值进行比较,然后缩小空间,继续查找

非朴素二分

重点一

循环条件必须是left < right,至于为什么只能是它,前面的文章已经讲解原因如果已经忘记的小伙伴可以返回前面的文章仔细阅读,如果是新来的小伙伴,那么先当作一个结论记下来,把题目大概理解后再回去看原因

重点二

求重点的操作,注意了这个必须得记住

重点三

当推理出左端点的条件后,右端点的条件取反即可

重点四

二分算法的使用前提是有二段性

那么本篇文章的内容就先到这里了,我们下期文章再见!!!

记得一键三联哦!!!

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

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

相关文章

HarmonyOS 实时监听与获取 Wi-Fi 信息

文章目录 摘要项目功能概述代码模块详细说明创建 Wi-Fi 状态保存对象Wi-Fi 状态监听模块获取当前 Wi-Fi 信息整合主模块 运行效果展示性能分析总结 摘要 本文展示了如何使用 HarmonyOS 框架开发一个 Demo&#xff0c;用于监听手机的 Wi-Fi 状态变化并实时获取连接的 Wi-Fi 信息…

gpu硬件架构

1.简介 NVIDIA在视觉计算和人工智能&#xff08;AI&#xff09;领域处于领先地位&#xff1b;其旗舰GPU已成为解决包括高性能计算和人工智能在内的各个领域复杂计算挑战所不可或缺的。虽然它们的规格经常被讨论&#xff0c;但很难掌握各种组件的清晰完整的图景。 这些GPU的高性…

【Qt】显示类控件:QLabel、QLCDNumber、QProgressBar、QCalendarWidget

目录 QLabel QFrame 例子&#xff1a; textFormat pixmap、scaledContents alignment wordWrap、indent、margin buddy QLCDNumber 例子&#xff1a; QTimer QProgressBar 例子&#xff1a; QCalendarWidget 例子&#xff1a; QLabel 标签控件&#xff0c;用来显示…

0001.基于springmvc简易酒店管理系统后台

一.系统架构 springmvcjsplayuimysql 二.功能特性 简单易学习&#xff0c;虽然版本比较老但是部署方便&#xff0c;tomcat环境即可启用&#xff1b;代码简洁&#xff0c;前后端代码提供可统一学习&#xff1b;祝愿您能成尽快为一位合格的程序员&#xff0c;愿世界没有BUG; …

Wallpaper壁纸制作学习记录12

角色表 创建人偶变形动画的更高级方法可以使用角色表来完成。角色表要求您使用角色的切割版本&#xff0c;将您的角色分成不同肢体/部分。这允许创建更复杂、更准确的动画&#xff0c;因为部分可以自由移动和重叠&#xff0c;而不会使图像失真。使用操控变形不一定能获得良好的…

【Python项目】基于Django的语音和背景音乐分离系统

【Python项目】基于Django的语音和背景音乐分离系统 技术简介&#xff1a;采用Python技术、Django框架、B/S结构&#xff0c;MYSQL数据库等实现。 系统简介&#xff1a;系统完成在线的音频上传&#xff0c;并且通过计算机的神经网络算法来对系统中的背景音乐和人声进行分离操作…

负载均衡oj项目:介绍

目录 项目介绍 项目演示 项目介绍 负载均衡oj是一个基于bs模式的项目。 用户使用浏览器向oj模块提交代码&#xff0c;oj模块会在所有在线的后端主机中选择一个负载情况最低的主机&#xff0c;将用户的代码提交给该主机&#xff0c;该主机进行编译运行&#xff0c;将结果返回…

【鸿睿创智开发板试用】移植OpenCV 4到OpenHarmony 4.1

目录 目录 引言 编译系统镜像 (1) 下载代码后解压SDK (2) 下载docker镜像   (3) 编译OH 编译OpenCV 下载OpenCV源代码 构建编译配置文件 执行编译命令 安装库和头文件 测试 结语 引言 最近有个需求是在基于RK3568的OpenHarmony 4.1系统中使用OpenCV&#xff0c…

【HarmonyOS之旅】HarmonyOS开发基础知识(一)

目录 1 -> 应用基础知识 1.1 -> 用户应用程序 1.2 -> 用户应用程序包结构 1.3 -> Ability 1.4 -> 库文件 1.5 -> 资源文件 1.6 -> 配置文件 1.7 -> pack.info 1.8 -> HAR 2 -> 配置文件简介 2.1 -> 配置文件的组成 3 -> 配置文…

【机器人】Graspness 端到端抓取点估计 | 环境搭建 | 模型推理测试

在复杂场景中实现抓取检测&#xff0c;Graspness是一种端到端的方法&#xff1b; 输入点云数据&#xff0c;输出抓取角度、抓取深度、夹具宽度等信息。 开源地址&#xff1a;https://github.com/rhett-chen/graspness_implementation?tabreadme-ov-file 论文地址&#xff1…

B站bilibili视频转文字字幕下载方法

本文将讲述介绍一种使用本地工具如何快速的下载B站的字幕为本地文本文件的方法。 通常获取B站字幕需要在浏览器中安装第三方插件&#xff0c;通过插件获取字幕。随着大模型&#xff0c;生成式AI&#xff0c;ChatGPT的应用&#xff0c;B站也提供了AI小助手对视频的内容进行总结…

CSS3 实现火焰-小火苗效果

创建 CSS3 火焰效果可以通过组合 CSS 动画、伪元素 和 渐变 来实现。以下是一个简单的实现步骤&#xff0c;展示如何制作动态火焰效果 1. HTML 结构 我们只需要一个简单的 div 容器&#xff1a; <div class"fire"></div>2. CSS 实现 基础样式 使用 …

新能源汽车充电需求攀升,智慧移动充电服务有哪些实际应用场景?

在新能源汽车行业迅猛发展的今天&#xff0c;智慧充电桩作为支持这一变革的关键基础设施&#xff0c;正在多个实际应用场景中发挥着重要作用。从公共停车场到高速公路服务区&#xff0c;从企业园区到住宅小区&#xff0c;智慧充电桩不仅提供了便捷的充电服务&#xff0c;还通过…

git remote -v(--verbose)显示你的 Git 仓库配置的远程仓库的详细信息

git remote -v 是一个 Git 命令&#xff0c;用于显示你的 Git 仓库配置的远程仓库的详细信息。 当你执行 git remote -v 命令时&#xff0c;你会看到类似以下的输出&#xff1a; origin https://github.com/your-username/your-repo.git (fetch) origin https://github.com…

Java Web项目部署教程简单实用

前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c; 忍不住分享一下给大家。点击跳转到网站 学习总结 1、掌握 JAVA入门到进阶知识(持续写作中……&#xff09; 2、学会Oracle数据库入门到入土用法(创作中……&#xff09; 3、手把…

【爬虫一】python爬虫基础合集一

【爬虫一】python爬虫基础合集一 1. 网络请求了解1.1. 请求的类型1.2. 网络请求协议1.3. 网络请求过程简单图解1.4. 网络请求Headers(其中的关键字释义)&#xff1a;请求头、响应头 2. 网络爬虫的基本工作节点2.1. 了解简单网络请求获取响应数据的过程所涉及要点 1. 网络请求了…

清理C盘小记

突然C盘就爆满了&#xff0c;想当初还是给他预留了120G的空间&#xff0c;感觉到现在也不够用了&#xff0c;担心出现死机的情况就赶紧进行了清理。有一说一&#xff0c;清理回收站是真的有用。 参考&#xff1a;C盘清理指南&#xff0c;清理出30G起&#xff0c;超详细总结&am…

Ansible playbook 详解与实战操作

一、概述 playbook 与 ad-hoc 相比,是一种完全不同的运用 ansible 的方式&#xff0c;类似与 saltstack 的 state 状态文件。ad-hoc 无法持久使用&#xff0c;playbook 可以持久使用。 playbook 是由一个或多个 play 组成的列表&#xff0c;play 的主要功能在于将事先归并为一…

seata-2阶段提交-笔记3

本文属于B站图灵课堂springcloud笔记系列。 前面整理过2篇:seata 2阶段提交实现代码-笔记1-CSDN博客 扫描GlobalTransactional注解 seata 2阶段提交实现代码-笔记2-CSDN博客 TC生成XID&#xff0c;并保存到global_table表。 本篇继续整理 执行业务逻辑&#xff0c;提交本地…

Docker如何运行一个Java的jar包程序

Docker如何运行一个Java的jar包程序 1、jar包程序 2、start.sh运行jar包脚本 #!/bin/bash #进入目录 cd /app #1.下载SDK并安装 java -jar SDKDown1.4.jar #2.加载环境变量 export LD_LIBRARY_PATH/opt/casb/CipherSuiteSdk_linux/lib echo $LD_LIBRARY_PATH #3.执行SDK java …