【C++ leetcode】双指针问题

2024-03-23 00:04
文章标签 leetcode c++ 问题 指针

本文主要是介绍【C++ leetcode】双指针问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1.   611. 有效三角形的个数

题目

给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。

题目链接

. - 力扣(LeetCode)

画图 和 文字 分析

判断是否是三角形要得到三边,由于遍历三边要套三层循环,时间复杂度很大,所以这里我们需要借助双指针思想,可以降到 O(N * N),先将这个数组进行排序(升序),然后定义三个指针,一个开始固定在数组的最后一个元素的位置,另外两个指向第一个位置和最后一个元素的前一个位置

举例: 输入[4,2,3,4],输出 4

如图

因为是排好序的,判断的时候,只需要拿 left , right 所指向的元素与 n 所指向的元素进行对比

比较过程会遇到两种情况:

第一种是不能构成三角形,则让 left++ ,

第二种是能构成三角形,则让 count += left - right (如果能构成三角形,则 right 和 n 不变,left 与 right 之间的区间都能构成三角形 ) ,right-- ,

直到 left >= right(里层循环结束条件) , 再 n--, right = n - 1 , left = 0

外出循环结束条件:n < 2

 代码

class Solution {
public:bool IsTriangle(int x,int y,int z){return (x + y) > z;}int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int count = 0;for(int n = nums.size() - 1;n >=2 ;n--){int left = 0;int right = n - 1;while(left < right){if(IsTriangle(nums[left],nums[right],nums[n])){count += (right - left);right--;}else{left++;}}}return count;}
};

2.   LCR 179. 查找总价格为目标值的两个商品

题目

购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况,返回任一结果即可。

题目链接

. - 力扣(LeetCode)

画图 和 文字 分析

思路还是一样,排序 + 双指针

很容易就想到思路,两个指针指向数组的两端

会遇到三种情况:

第一种情况,当大于目标值时,right--

第二种情况,当小于目标值时,left++

第三种情况,等于目标值时,存完数值,break 即可

代码

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {vector<int> t;int right = price.size() - 1;int left = 0;while(left < right){if( price[left] +  price[right] == target ){t.push_back(price[left]);t.push_back(price[right]);break;}else if(price[left] +  price[right] > target){right--;}else{left++;}}return t;}
};

这篇关于【C++ leetcode】双指针问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/836521

相关文章

Spring的RedisTemplate的json反序列泛型丢失问题解决

《Spring的RedisTemplate的json反序列泛型丢失问题解决》本文主要介绍了SpringRedisTemplate中使用JSON序列化时泛型信息丢失的问题及其提出三种解决方案,可以根据性... 目录背景解决方案方案一方案二方案三总结背景在使用RedisTemplate操作redis时我们针对

Kotlin Map映射转换问题小结

《KotlinMap映射转换问题小结》文章介绍了Kotlin集合转换的多种方法,包括map(一对一转换)、mapIndexed(带索引)、mapNotNull(过滤null)、mapKeys/map... 目录Kotlin 集合转换:map、mapIndexed、mapNotNull、mapKeys、map

nginx中端口无权限的问题解决

《nginx中端口无权限的问题解决》当Nginx日志报错bind()to80failed(13:Permissiondenied)时,这通常是由于权限不足导致Nginx无法绑定到80端口,下面就来... 目录一、问题原因分析二、解决方案1. 以 root 权限运行 Nginx(不推荐)2. 为 Nginx

解决1093 - You can‘t specify target table报错问题及原因分析

《解决1093-Youcan‘tspecifytargettable报错问题及原因分析》MySQL1093错误因UPDATE/DELETE语句的FROM子句直接引用目标表或嵌套子查询导致,... 目录报js错原因分析具体原因解决办法方法一:使用临时表方法二:使用JOIN方法三:使用EXISTS示例总结报错原

Windows环境下解决Matplotlib中文字体显示问题的详细教程

《Windows环境下解决Matplotlib中文字体显示问题的详细教程》本文详细介绍了在Windows下解决Matplotlib中文显示问题的方法,包括安装字体、更新缓存、配置文件设置及编码調整,并... 目录引言问题分析解决方案详解1. 检查系统已安装字体2. 手动添加中文字体(以SimHei为例)步骤

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

SpringSecurity整合redission序列化问题小结(最新整理)

《SpringSecurity整合redission序列化问题小结(最新整理)》文章详解SpringSecurity整合Redisson时的序列化问题,指出需排除官方Jackson依赖,通过自定义反序... 目录1. 前言2. Redission配置2.1 RedissonProperties2.2 Red

nginx 负载均衡配置及如何解决重复登录问题

《nginx负载均衡配置及如何解决重复登录问题》文章详解Nginx源码安装与Docker部署,介绍四层/七层代理区别及负载均衡策略,通过ip_hash解决重复登录问题,对nginx负载均衡配置及如何... 目录一:源码安装:1.配置编译参数2.编译3.编译安装 二,四层代理和七层代理区别1.二者混合使用举例

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被