【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字
611. 有效三角形的个数
611. 有效三角形的个数
https://leetcode.cn/problems/valid-triangle-number/
题目描述:
给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。

解题思路:
本题是一个关于三角形是否能成立的题目,首先我们假设三角形的三边(a,b,c),我们要保证两边之和大于第三边
题目给我们nums是乱序的,如果我们一个个abc去实验就是会超时(时间复杂度O^3)
当我们将sort排序一下,这样的话假设a<b<c的情况下,我们就只要去判断a+b>c是否成立!
这里我们遍历每个c(从后往前),这样时间复杂度就变成了N^2+NlogN也就是N^2
解题代码:
class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());//假设a<b<cint num=0;int n=nums.size();for(int i=n-1;i>=2;i--){int left=0;int right=i-1;while(left<right){if(nums[left]+nums[right]>nums[i]){num+=(right-left);right--;}else{left++;}}}return num;}
};
剑指 Offer 57. 和为s的两个数字
剑指 Offer 57. 和为s的两个数字
https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/
题目描述:
输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

解题思路:
首先本题是升序数组,这里如果我们用暴力的话会超时
这里我们使用双指针,我们让一个指向头left一个指向尾right,这里left、right和target会有三种关系
我们假设sub=right-left
第一种情况很显然直接返回就好了我们来研究一下第二种和第三种情况:
解题代码:
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n=nums.size();int left=0;int right=n-1;while(nums[right]>target){right--;}while(left<right){int sub=target-nums[right];if(sub==nums[left]){return {nums[left],nums[right]};}else if(sub>nums[left]){left++;}else//sub<nums[left]{right--;}}return {-1,-1};}
};
相关文章:
【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字
611. 有效三角形的个数 611. 有效三角形的个数https://leetcode.cn/problems/valid-triangle-number/ 题目描述: 给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。 解题思路: 本题是一个关于三角形是否能成立…...
通过 kk 创建 k8s 集群和 kubesphere
官方文档:多节点安装 确保从正确的区域下载 KubeKey export KKZONEcn下载 KubeKey curl -sfL https://get-kk.kubesphere.io | VERSIONv3.0.7 sh -为 kk 添加可执行权限: chmod x kk创建 config 文件 KubeSphere 版本:v3.3 支持的 Kuber…...
感觉和身边其他人有差距怎么办?
虽然清楚知识需要靠时间沉淀,但在看到自己做不出来的题别人会做,自己写不出的代码别人会写时还是会感到焦虑怎么办? 你是否也因为自身跟周围人的差距而产生过迷茫,这份迷茫如今是被你克服了还是仍旧让你感到困扰? 下…...
【C语言基础】宏定义的用法详解
📢:如果你也对机器人、人工智能感兴趣,看来我们志同道合✨ 📢:不妨浏览一下我的博客主页【https://blog.csdn.net/weixin_51244852】 📢:文章若有幸对你有帮助,可点赞 👍…...
微服务系列文章之 SpringBoot 最佳实践
Spring Boot 是一种广泛使用且非常流行的企业级高性能框架。 以下是一些最佳实践和一些技巧,我们可以使用它们来改进 Spring Boot 应用程序并使其更加高效。 Spring Boot 的四大核心 1、自动配置 针对很多Spring应用程序和常见的应用功能,Spring Boo…...
C++并发多线程--std::async、std::packaged_task和std::promise的使用
目录 1--std::async的使用 2--std::packaged_task的使用 3--std::promise的使用 1--std::async的使用 std::async用于启动一个异步任务,并返回一个std::future对象;std::future对象里含有异步任务线程入口函数的结果; std::launch::deferr…...
opencv-目标追踪
import argparse import time import cv2 import numpy as np# 配置参数 ap argparse.ArgumentParser() ap.add_argument("-v", "--video", typestr,help"path to input video file") ap.add_argument("-t", "--tracker", …...
【数据结构】 单链表面试题讲解
文章目录 引言反转单链表题目描述示例:题解思路代码实现: 移除链表元素题目描述:示例思路解析: 链表的中间结点题目描述:示例:思路解析代码实现如下: 链表中倒数第k个结点题目描述示例思路解析&…...
C++ string类的模拟实现
模拟实现string类不是为了造一个更好的轮子,而是更加理解string类,从而来掌握string类的使用 string类的接口设计繁多,故而不会全部涵盖到,但是核心的会模拟实现 库中string类是封装在std的命名空间中的,所以在模拟…...
Qt实现简单的漫游器
文章目录 Qt的OpenGL窗口GLSL的实现摄像机类的实现简单的漫游器 Qt的OpenGL窗口 Qt主要是使用QOpenGLWidget来实现opengl的功能。 QOpenGLWidget 提供了三个便捷的虚函数,可以重载,用来重新实现典型的OpenGL任务: paintGL:渲染…...
【c语言】文件操作
朋友们,大家好,今天分享给大家的是文件操作的相关知识,跟着我一起学习吧!! 🎈什么是文件 磁盘上的文件是文件。 但是在程序设计中,我们一般谈的文件有两种:程序文件、数据文件 程序文…...
【Unity】坐标转换经纬度方法(应用篇)
【Unity】坐标转换经纬度方法(应用篇) 解决地图中经纬度坐标转换与unity坐标互转的问题。使用线性变换的方法,理论上可以解决小范围内所以坐标转换的问题。 之前有写过[Unity]坐标转换经纬度方法(原理篇),在实际使用中,…...
element时间选择器el-date-picter使用disabledDate指定禁用的日期
需要的效果 <el-date-pickerclass"selectstyle"v-model"year"value-format"yyyy"type"year":picker-options"disabledCli"placeholder"选择年"> </el-date-picker>data() {return {disabledCli: {/…...
出学校干了 5 年外包,已经废了
如果不是女朋友和我提分手,我估计现在还没醒悟 本科大专,17年通过校招进入某软件公司做测试,干了接近5年的功能。 今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落!而我已经…...
day-23 代码随想录算法训练营(19)part09
669.修剪二叉搜索树 思路一:根据二叉搜索树的特性进行中间值与去区间值判断,有三种情况:1.在区间中,所以左右子树都可能在区间中; 2.在区间外面的左侧,必然只有右子树可能存在区间中;3.在区间外…...
JVM编译优化
即时编译器 HotSpot虚拟机中内置了两个即时编译器,分别称为Client Compiler和Server Compiler,或者简称为C1编译器和C2编译器。Java8默认开启Server模式。用户可以使用“-client”或“-server”参数去指定编译模式。 C1编译器启动速度快,关注局部简单可靠的优化,比如方法…...
vue浏览器插件安装-各种问题
方法1:vue.js devtolls插件下载 https://blog.csdn.net/qq_55640378/article/details/131553642 下载地址: Tags vuejs/devtools GitHub npm install 或是 cnpm install 遇到的报错 设置淘宝镜像源(推荐使用nrm,这一步是为…...
maven工具-maven的使用-镜像仓库、本地仓、IDEA使用maven
Maven 一、为什么使用maven 添加第三方jar包jar包之间的依赖关系处理jar包之间的冲突获取第三方jar包将项目拆分成多个工程模块实现项目的分布式部署 二、maven简介 Maven项目对象模型(POM),可以通过一小段描述信息来管理项目的构建,报告和文档的…...
Mac鼠标增强工具Smooze Pro
Smooze Pro是一款Mac上的鼠标手势增强工具,可以让用户使用鼠标手势来控制应用程序和系统功能。 它支持多种手势操作,包括单指、双指、三指和四指手势,并且可以自定义每种手势的功能。例如,您可以使用单指向下滑动手势来启动Expos视…...
数据结构-单链表(C语言简单实现)
简介 以顺序结构进行数据存储时,它的特点就是可以用一组任意的存储单元存储数据元素,这组存储单元可以是连续的,也可以是不连续的,这些数据可以存在内存未被占用的任意位置。它也是有缺点的,就是在插入和删除时需要移…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...



