二分基础两道
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 抓交通肇事犯 一辆卡车违反交通规则,撞人后逃跑。现场有三人目击该事件,但都没有记住车号,只记下了车号的一些特征。甲说:牌照的前两位数字是相同的;乙说:牌照的后两位数字是相同的,但与前…...
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 …...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南
1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发,使用DevEco Studio作为开发工具,采用Java语言实现,包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
