双指针的问题解法以及常见的leetcode例题。
目录
介绍:
问题1:双指针 剑指offer57 和为S的两个数字。
问题2:剑指Offer 21. 调整数组顺序使奇数位于偶数前面
问题3:连续奇数子串(笔试遇到的真题)
问题4:滑动窗口的最大值
介绍:
双指针的问题通常需要理解问题的核心,然后选择合适的双指针策略来解决问题。以下是一种通用的解决方法:
- 首先,对数组进行排序,这样相同的元素会在一起,并且可以更好地控制数组的遍历。
- 定义两个指针,一个快指针和一个慢指针。通常,快指针是慢指针的两倍速度。
- 从数组的两侧开始遍历,比较两个指针指向的元素之和与目标值的大小。
- 根据和的大小调整指针的位置,例如,如果和等于目标值,则将两个指针都向后移动一位。如果和小于目标值,则慢指针向后移动一位,快指针向前移动两位。如果和大于目标值,则慢指针向前移动一位,快指针向后移动两位。
- 当快指针和慢指针相遇时,就找到了解。
这种解决方案适用于很多问题,但是具体实现需要根据问题的具体要求进行调整。
问题1:双指针 剑指offer57 和为S的两个数字。
https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/?envType=study-plan-v2&envId=coding-interviews
tag:easy.
// 输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。
示例 1:因为已经排序完成了,定义了两个指针.从两侧进行即可。
输入:nums = [2,7,11,15], target = 9
输出:[2,7] 或者 [7,2]
示例 2:
输入:nums = [10,26,30,31,47,60], target = 40
输出:[10,30] 或者 [30,10]
class Solution10
{
public:vector<int> twoSum(vector<int> &nums, int target){vector<int> ans;int left = 0, right = nums.size() - 1;while (left <= right){if (nums[left] + nums[right] == target){ans.push_back(nums[left]);ans.push_back(nums[right]);break;}else if (nums[left] + nums[right] > target){right--;}else{left++;}}return ans;}
};
问题2:剑指Offer 21. 调整数组顺序使奇数位于偶数前面
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。
https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/?envType=study-plan-v2&envId=coding-interviews。
输入:nums = [1,2,3,4]
输出:[1,3,2,4]
注:[3,1,2,4] 也是正确的答案之一
class Solution11 {
public:vector<int> exchange(vector<int>& nums) {int left=0;int right=0;while(right<nums.size()){if(nums[right]%2!=0){swap(nums[left++],nums[right++]);}else{right++;}}return nums;}};
问题3:连续奇数子串(笔试遇到的真题)
若有一组最小值大于0,数目大于1的连续的奇数的和等于指定正整5数
字,那么此连续的奇数序列称为此正整数数字的一个奇序列。如数字12,总共能找出一个奇序列 (5,7),数字16 能找出两个奇序列 (1,3,5,7)和(7,9)
数字17 找不出,那么12的奇序列数为1,16的奇序列数为2,17的奇序列数为0。
输入 17
输入 0
输入 16
输出 2
输入 12
输出 1
函数用于计算奇序列数 从1 开始 加到 n/2,计算累计和超过n进入while 循环. 如果等于就是+2, 否则就停止。
1 3 5 7 9 11
3 5 7 9
5 7 9 。。。小于n就可以了。
int main()
{int n;cin >> n;int start = 0;int count = 0;int sum = 0;int i = 0;for (start = 1; start < n / 2; start += 2){i = start;sum = 0;while (sum < n){sum += i;i += 2;}if (sum == n){count++;}}cout << count << endl;system("pause");return 0;
}
问题4:滑动窗口的最大值
剑指 Offer 59 - I. 滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k,请找出所有滑动窗口里的最大值。
示例:
输入: nums =[1,3,-1,-3,5,3,6,7], 和 k = 3 输出:[3,3,5,5,6,7] 解释:滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 31 [3 -1 -3] 5 3 6 7 31 3 [-1 -3 5] 3 6 7 51 3 -1 [-3 5 3] 6 7 51 3 -1 -3 [5 3 6] 7 61 3 -1 -3 5 [3 6 7] 7
class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {int n=nums.size();priority_queue<pair<int,int>> q;for(int i=0;i<k;i++){q.emplace(nums[i],i);}vector<int> ans={q.top().first};for(int i=k;i<n;i++){q.emplace(nums[i],i);//离开了滑动窗口里面了,永久移除了while(q.top().second<=i-k){q.pop();}ans.push_back(q.top().first);}return ans;}};
======================待补充===========================
相关文章:
双指针的问题解法以及常见的leetcode例题。
目录 介绍: 问题1:双指针 剑指offer57 和为S的两个数字。 问题2:剑指Offer 21. 调整数组顺序使奇数位于偶数前面 问题3:连续奇数子串(笔试遇到的真题) 问题4:滑动窗口的最大值 介绍&#…...
python容器模块Collections
Python附带一个模块,它包含许多容器数据类型,名字叫作collections defaultdict defaultdict与dict类型不同,你不需要检查key是否存在,所以我们能这样做: from collections import defaultdict colours ((Yasoob, Y…...
排序算法学习记录-快速排序
快速排序 快速排序关键在于确定一个中间值,使得小于这个中间值的数在左边,大于这个中间值的数在右边。那么中间值该如何确定呢?有以下几种做法 首元素,也就是arr[l]尾元素,也就是arr[r]中间元素,也就是ar…...
安装windows版本的ros2 humble的时候,最后报错
"[rti_connext_dds_cmake_module][warning] RTI Connext DDS environment script not found (\resource\scripts\rtisetenv_x64Win64VS2017.bat). RTI Connext DDS will not be available at runtime, unless you already configured PATH manually." 意思是没找到。…...
Nginx 学习(十)高可用中间件的配置与实现
一 Keepalived热备 1 概述 调度器出现单点故障,如何解决?Keepalived实现了高可用集群Keepalived最初是为LVS设计的,专门监控各服务器节点的状态Keepalived后来加入了VRRP功能,防止单点故障 2 运行原理 Keepalived检测每个服务器节点状…...
[刷题记录]牛客面试笔刷TOP101
牛客笔试算法必刷TOP101系列,每日更新中~ 1.合并有序链表2023.9.3 合并两个排序的链表_牛客题霸_牛客网 (nowcoder.com) 题意大致为: 将两个链表中的元素按照从小到大的顺序合并成为一个链表. 所给予的条件: 给出的所要合并的链表都是从小到大顺序排列的. 思路: 创建一…...
降水预报之双重惩罚
在降水预报中,通常会出现 "双重惩罚问题 "的指标或度量包括那些常用于预报验证的指标或度量。当假阴性(漏报降水事件)和假阳性(误报)受到同等惩罚或加权时,就会出现双重惩罚问题,这在…...
一条SQL语句的执行过程(附一次两段式提交)
一条SQL语句的完整执行过程是怎样的呢?我们用select和update语句来举例。 注意在mysql8后,进入服务层后,取消了去查询缓存(属于Server服务层)这个步骤,缓存中key是SQL语句,value是值,这样其实并不会提升性…...
Python基础知识详解:数据类型、对象结构、运算符完整分析
文章目录 python基础知识数据类型类型检查对象(object)对象的结构变量和对象类型转换运算符(操作符)1. 算术运算符2. 赋值运算符3. 比较运算符(关系运算符)4. 逻辑运算符5. 条件运算符(三元运算符) 总结 py…...
基于Streamlit的应用如何通过streamlit-authenticator组件实现用户验证与隔离
Streamlit框架中默认是没有提供用户验证组件的,大家在基于streamlit快速实现web应用服务过程中,不可避免的需要配置该应用的访问范围和权限,即用户群体,一般的做法有两种,一种是通过用户密码验证机制,要求只…...
[虚幻引擎插件介绍] DTGlobalEvent 蓝图全局事件, Actor, UMG 相互回调,自由回调通知事件函数,支持自定义参数。
本插件可以在虚幻的蓝图 Actor, Obiect,UMG 里面指定绑定和执行消息,可带自定义参数。 参数支持 Bool,Byte,Int,Int64,Float,Name,String,Text,Ve…...
2023数学建模国赛选题建议及BC题思路
大家好呀,全国大学生数学建模竞赛今天下午开赛啦,在这里先带来初步的选题建议及思路。 目前团队正在写B题和C题完整论文,后续还会持续更新哈,以下只是比较简略的图文版讲解,团队目前正在写B、C题完整论文,…...
vue3:4、组合式API-setup选项
setup每次都要return,好麻烦。怎么解决? 使用 <script setup> 语法糖(底层帮你return了) 写法如下...
【C刷题训练营】第三讲(c语言入门训练)
前言: 大家好,我决定日后逐渐更新c刷题训练营的内容,或许能帮到入门c语言的初学者,如果文章有错误,非常欢迎你的指正! 💥🎈个人主页:Dream_Chaser~ 🎈&…...
简述视频智能分析EasyCVR视频汇聚平台如何通过“AI+视频融合”技术规避八大特殊作业风险
视频智能分析EasyCVR视频汇聚平台可以根据不同的场景需求,让平台在内网、专网、VPN、广域网、互联网等各种环境下进行音视频的采集、接入与多端分发。在视频能力上,视频云存储平台EasyCVR可实现视频实时直播、云端录像、视频云存储、视频存储磁盘阵列、录…...
2023年9月NPDP产品经理国际认证报名,找弘博创新
产品经理国际资格认证NPDP是新产品开发方面的认证,集理论、方法与实践为一体的全方位的知识体系,为公司组织层级进行规划、决策、执行提供良好的方法体系支撑。 【认证机构】 产品开发与管理协会(PDMA)成立于1979年,是…...
【MySQL】MySQL的安装,登录,配置和相关命令
文章目录 前言一. 卸载不需要的环境二. 获取MySQL的yum源三. 安装MySQL和启动四. 尝试登录MySQL方法1:获取临时root密码方法2:没有密码方法3:配置文件 五. 简单配置结束语 前言 本篇文章是基于云服务器;Linux:Centos7…...
攻防世界-WEB-php_rce
打开靶机链接 搜村ThinkPhP V5存在远程命令执行的漏洞 构建payload /index.php?sindex/think\app/invokefunction&functioncall_user_func_array&vars[0]system&vars[1][]ls 查询当前目录文件,没有发现flag。调整payload 得到flag文件,修…...
WRFDA资料同化实践技术
数值预报已经成为提升预报质量的重要手段,而模式初值质量是决定数值预报质量的重要环节。资料同化作为提高模式初值质量的有效方法,成为当前气象、海洋和大气环境和水文等诸多领域科研、业务预报中的关键科学方法。资料同化新方法的快速发展,…...
C++11新特性② | 左值、左值引用、右值与右值引用
目录 1、引言 2、值类别及相关概念 3、左值、右值 4、左值引用、右值引用 5、移动语义 5.1、为什么需要移动语义 5.2、移动语义定义 5.3、转移构造函数 5.4、转移赋值函数 6、标准库函数 std::move 7、完美转发 std::forward VC常用功能开发汇总(专栏文章…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
css实现圆环展示百分比,根据值动态展示所占比例
代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...
C++.OpenGL (10/64)基础光照(Basic Lighting)
基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...
es6+和css3新增的特性有哪些
一:ECMAScript 新特性(ES6) ES6 (2015) - 革命性更新 1,记住的方法,从一个方法里面用到了哪些技术 1,let /const块级作用域声明2,**默认参数**:函数参数可以设置默认值。3&#x…...
Java中栈的多种实现类详解
Java中栈的多种实现类详解:Stack、LinkedList与ArrayDeque全方位对比 前言一、Stack类——Java最早的栈实现1.1 Stack类简介1.2 常用方法1.3 优缺点分析 二、LinkedList类——灵活的双端链表2.1 LinkedList类简介2.2 常用方法2.3 优缺点分析 三、ArrayDeque类——高…...
CVE-2023-25194源码分析与漏洞复现(Kafka JNDI注入)
漏洞概述 漏洞名称:Apache Kafka Connect JNDI注入导致的远程代码执行漏洞 CVE编号:CVE-2023-25194 CVSS评分:8.8 影响版本:Apache Kafka 2.3.0 - 3.3.2 修复版本:≥ 3.4.0 漏洞类型:反序列化导致的远程代…...
Copilot for Xcode (iOS的 AI辅助编程)
Copilot for Xcode 简介Copilot下载与安装 体验环境要求下载最新的安装包安装登录系统权限设置 AI辅助编程生成注释代码补全简单需求代码生成辅助编程行间代码生成注释联想 代码生成 总结 简介 尝试使用了Copilot,它能根据上下文补全代码,快速生成常用…...
