二分基础两道
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 抓交通肇事犯 一辆卡车违反交通规则,撞人后逃跑。现场有三人目击该事件,但都没有记住车号,只记下了车号的一些特征。甲说:牌照的前两位数字是相同的;乙说:牌照的后两位数字是相同的,但与前…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
Razor编程中@Html的方法使用大全
文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...
DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...
