二分基础两道
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 抓交通肇事犯 一辆卡车违反交通规则,撞人后逃跑。现场有三人目击该事件,但都没有记住车号,只记下了车号的一些特征。甲说:牌照的前两位数字是相同的;乙说:牌照的后两位数字是相同的,但与前…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
数据结构:递归的种类(Types of Recursion)
目录 尾递归(Tail Recursion) 什么是 Loop(循环)? 复杂度分析 头递归(Head Recursion) 树形递归(Tree Recursion) 线性递归(Linear Recursion)…...
