二分基础两道
Leetcode704:
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
示例 1:
输入:nums= [-1,0,3,5,9,12],target= 9 输出: 4 解释: 9 出现在nums中并且下标为 4
代码:
class Solution {
public:int search(vector<int>& nums, int target) {sort(nums.begin(), nums.end());int l, r, mid;l = 0, r = nums.size();//左闭右开,与结束循环条件l<r相对应while (l < r) {mid = (l + r) / 2;if (nums[mid] >= target) {//由于这种二分方法是利用l+1避免无限循环,因此r=mid的判定条件是合法即可(即加上等于号)//因为r不会+1,会一直将搜索结果保留在区间内r = mid;} else {l = mid + 1;}}if (l >= 0 && l < nums.size() && nums[l] == target)return l;elsereturn -1;}
};
Leetcode 209
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的
子数组
[numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
典型的二分搜索答案类型题。以最终答案长度作为二分搜索的目标进行搜索。
class Solution {
public:bool check(int mid, int target, vector<int>& nums){int sum = 0;for(int i = 0;i<mid;i++){sum += nums[i];}if(target<=sum)return true;for(int i = mid;i<nums.size();i++){sum+=nums[i];sum-=nums[i-mid];if(target<=sum)return true;}return false;}int minSubArrayLen(int target, vector<int>& nums) {int sum = 0;for(int i = 0;i<nums.size();i++){sum += nums[i];}if(target>sum)return 0;int l,r,mid;l = 1,r = nums.size();while(l<r){mid=(l+r)/2;if(check(mid,target,nums)){r = mid;}else l = mid + 1;}return l;}
};
这道题还可以使用双指针,代码如下:
class Solution {
public:int minSubArrayLen(int s, vector<int>& nums) {int l,r;l=r=0;int sum = 0;int ans = INT_MAX;while(r<nums.size()){sum += nums[r];if(sum>=s){while(sum>=s){sum-=nums[l];l++;}ans = min(ans,r-l+2);}r++;}if(ans==INT_MAX)return 0;else return ans;}
};
相关文章:
二分基础两道
Leetcode704: 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。 示例 1: 输入: nums [-1,0,3,5,9,12], target 9 输出:…...
Skyeye 云 VUE 版本 v3.15.7 发布
Skyeye 云智能制造,采用 Springboot winUI 的低代码平台、移动端采用 UNI-APP。包含 30 多个应用模块、50 多种电子流程,CRM、PM、ERP、MES、ADM、EHR、笔记、知识库、项目、门店、商城、财务、多班次考勤、薪资、招聘、云售后、论坛、公告、问卷、报表…...
位运算和操作符属性
位运算和操作符属性 除了课件中提到的那几种应用,其他时候一般先不考虑用这个原反补码 printf("%d\n,017")打印出来则是15 printf("%d\n,0017")打印出来也是15 printf("%d\n,0x017")打印出来是23eg:2进制转换为32进制则每5个2进制位…...
php的使用及 phpstorm环境部署
php语法 环境搭建:在小皮中新建网站,注意先填写域名再点击选择根目录。 成功创建网站后,打开发现forbidden,因为新建的网站里是空的,需要新建index.php文件----> 在Phpstorm中左上角打开文件,打开那个文…...
高阶开发基础——快速入门C++并发编程6——大作业:实现一个超级迷你的线程池
目录 实现一个无返回的线程池 完全代码实现 Reference 实现一个无返回的线程池 实现一个简单的线程池非常简单,我们首先聊一聊线程池的定义: 线程池(Thread Pool) 是一种并发编程的设计模式,用于管理和复用多个线程…...
Jupyterlab和notebook修改文件的默认存放路径的方法
文章目录 1.缘由2.操作流程2.1找到默认的路径2.2创建配置文件2.3修改配置文件内容2.4注意事项 1.缘由 我自己使用jupyterlab的时候,打开是在这个浏览器上面打开的,但是这个打开的文件路径显示的是C盘上面路径,所以这个就很麻烦,因…...
吴恩达深度学习——有效运作神经网络
内容来自https://www.bilibili.com/video/BV1FT4y1E74V,仅为本人学习所用。 文章目录 训练集、验证集、测试集偏差、方差正则化正则化参数为什么正则化可以减少过拟合Dropout正则化Inverted Dropout其他的正则化方法数据增广Early stopping 归一化梯度消失与梯度爆…...
享元模式——C++实现
目录 1. 享元模式简介 2. 代码示例 1. 享元模式简介 享元模式是一种结构型模式。 享元模式用于缓存共享对象,降低内存消耗。共享对象相同的部分,避免创建大量相同的对象,减少内存占用。 享元模式需要将对象分成内部状态和外部状态两个部分…...
【Go语言圣经】第五节:函数
第五章:函数 5.1 函数声明 和其它语言类似,Golang 的函数声明包括函数名、形参列表、返回值列表(可省略)以及函数体: func name(parameter-list) (result-list) {/* ... Body ... */ }需要注意的是,函数…...
win32汇编环境,窗口程序中使用进度条控件
;运行效果 ;win32汇编环境,窗口程序中使用进度条控件 ;进度条控件主要涉及的是长度单位,每步步长,推进的时间。 ;比如你的长度是1000,步长是100,每秒走1次,则10秒走完全程 ;比如你的长度是1000,步长是10&am…...
Vscode的AI插件 —— Cline
简介 vscode的一款AI辅助吃插件,主要用来辅助创建和编辑文件,探索大型项目,使用浏览器并执行终端命令(需要多个tokens),可以使用模型上下文协议(MCP)来创建新工具并扩展自己(比较慢…...
Flink (十三) :Table API 与 DataStream API 的转换 (一)
Table API 和 DataStream API 在定义数据处理管道时同样重要。DataStream API 提供了流处理的基本操作(即时间、状态和数据流管理),并且是一个相对低级的命令式编程 API。而 Table API 抽象了许多内部实现,提供了一个结构化和声明…...
Android --- handler详解
handler 理解 handler 是一套Android 消息传递机制,主要用于线程间通信。 tips: binder/socket 用于进程间通信。 参考: Android 进程间通信-CSDN博客 handler 就是主线程在起了一个子线程,子线程运行并生成message ,l…...
[EAI-023] FAST,机器人动作专用的Tokenizer,提高VLA模型的能力和训练效率
Paper Card 论文标题:FAST: Efficient Action Tokenization for Vision-Language-Action Models 论文作者:Karl Pertsch, Kyle Stachowicz, Brian Ichter, Danny Driess, Suraj Nair, Quan Vuong, Oier Mees, Chelsea Finn, Sergey Levine 论文链接&…...
关于贪心学习的文笔记录
贪心,顾名思义就是越贪越好,越多越有易,他给我的感觉是,通常是求最大或最小问题,相比于动态规划贪心让人更加琢磨不透,不易看出方法,为此在这记录我所见过的题型和思维方法,以便回头…...
SLAM技术栈 ——《视觉SLAM十四讲》学习笔记(一)
《视觉SLAM十四讲》学习笔记(一) 第2讲 初识SLAM习题部分 第3讲 三维空间刚体运动3.1 左手系与右手系3.2 齐次坐标3.3 旋转矩阵与变换矩阵3.4 正交群与欧式群3.5 旋转向量与欧拉角3.6 实践Eigen线性代数库3.6.1 QR分解(QR decomposition) 3.7 四元数到其…...
【ChatGPT:开启人工智能新纪元】
一、ChatGPT 是什么 最近,ChatGPT 可是火得一塌糊涂,不管是在科技圈、媒体界,还是咱们普通人的日常聊天里,都能听到它的大名。好多人都在讨论,这 ChatGPT 到底是个啥 “神器”,能让大家这么着迷?今天咱就好好唠唠。 ChatGPT,全称是 Chat Generative Pre-trained Trans…...
1. 【.NET 8 实战--孢子记账--从单体到微服务--转向微服务】--前言
在我们的专栏《单体开发》中,我们实现了一个简单的记账软件的服务端,并且成功上线。随着用户数量的不断增长,问题逐渐开始显现。访问量逐渐增加,服务端的压力也随之加大。随着访问量的攀升,服务端的响应时间变得越来越…...
量子力学初步:微观领域的科学之旅
飞书📚链接:量子力学篇 长尾 - 什么是量子力学 (未完成… 等有时间再看,前面的内容可以参考下,比如了解自旋、以及斯特恩-盖拉赫实验) 【量子力学篇-01期】经典物理学的终结,量子力学的开端 量…...
趣味Python100例初学者练习01
1. 1 抓交通肇事犯 一辆卡车违反交通规则,撞人后逃跑。现场有三人目击该事件,但都没有记住车号,只记下了车号的一些特征。甲说:牌照的前两位数字是相同的;乙说:牌照的后两位数字是相同的,但与前…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
WEB3全栈开发——面试专业技能点P7前端与链上集成
一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染(SSR)与静态网站生成(SSG) 框架,由 Vercel 开发。它简化了构建生产级 React 应用的过程,并内置了很多特性: ✅ 文件系…...
macOS 终端智能代理检测
🧠 终端智能代理检测:自动判断是否需要设置代理访问 GitHub 在开发中,使用 GitHub 是非常常见的需求。但有时候我们会发现某些命令失败、插件无法更新,例如: fatal: unable to access https://github.com/ohmyzsh/oh…...
