当前位置: 首页 > news >正文

【算法挨揍日记】day03——双指针算法_有效三角形的个数、和为s的两个数字

  

611. 有效三角形的个数

611. 有效三角形的个数icon-default.png?t=N6B9https://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的两个数字icon-default.png?t=N6B9https://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/ 题目描述&#xff1a; 给定一个包含非负整数的数组 nums &#xff0c;返回其中可以组成三角形三条边的三元组个数。 解题思路&#xff1a; 本题是一个关于三角形是否能成立…...

通过 kk 创建 k8s 集群和 kubesphere

官方文档&#xff1a;多节点安装 确保从正确的区域下载 KubeKey export KKZONEcn下载 KubeKey curl -sfL https://get-kk.kubesphere.io | VERSIONv3.0.7 sh -为 kk 添加可执行权限&#xff1a; chmod x kk创建 config 文件 KubeSphere 版本&#xff1a;v3.3 支持的 Kuber…...

感觉和身边其他人有差距怎么办?

虽然清楚知识需要靠时间沉淀&#xff0c;但在看到自己做不出来的题别人会做&#xff0c;自己写不出的代码别人会写时还是会感到焦虑怎么办&#xff1f; 你是否也因为自身跟周围人的差距而产生过迷茫&#xff0c;这份迷茫如今是被你克服了还是仍旧让你感到困扰&#xff1f; 下…...

【C语言基础】宏定义的用法详解

&#x1f4e2;&#xff1a;如果你也对机器人、人工智能感兴趣&#xff0c;看来我们志同道合✨ &#x1f4e2;&#xff1a;不妨浏览一下我的博客主页【https://blog.csdn.net/weixin_51244852】 &#x1f4e2;&#xff1a;文章若有幸对你有帮助&#xff0c;可点赞 &#x1f44d;…...

微服务系列文章之 SpringBoot 最佳实践

Spring Boot 是一种广泛使用且非常流行的企业级高性能框架。 以下是一些最佳实践和一些技巧&#xff0c;我们可以使用它们来改进 Spring Boot 应用程序并使其更加高效。 Spring Boot 的四大核心 1、自动配置 针对很多Spring应用程序和常见的应用功能&#xff0c;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用于启动一个异步任务&#xff0c;并返回一个std::future对象&#xff1b;std::future对象里含有异步任务线程入口函数的结果&#xff1b; 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", …...

【数据结构】 单链表面试题讲解

文章目录 引言反转单链表题目描述示例&#xff1a;题解思路代码实现&#xff1a; 移除链表元素题目描述&#xff1a;示例思路解析&#xff1a; 链表的中间结点题目描述&#xff1a;示例&#xff1a;思路解析代码实现如下&#xff1a; 链表中倒数第k个结点题目描述示例思路解析&…...

C++ string类的模拟实现

模拟实现string类不是为了造一个更好的轮子&#xff0c;而是更加理解string类&#xff0c;从而来掌握string类的使用 string类的接口设计繁多&#xff0c;故而不会全部涵盖到&#xff0c;但是核心的会模拟实现 库中string类是封装在std的命名空间中的&#xff0c;所以在模拟…...

Qt实现简单的漫游器

文章目录 Qt的OpenGL窗口GLSL的实现摄像机类的实现简单的漫游器 Qt的OpenGL窗口 Qt主要是使用QOpenGLWidget来实现opengl的功能。  QOpenGLWidget 提供了三个便捷的虚函数&#xff0c;可以重载&#xff0c;用来重新实现典型的OpenGL任务&#xff1a; paintGL&#xff1a;渲染…...

【c语言】文件操作

朋友们&#xff0c;大家好&#xff0c;今天分享给大家的是文件操作的相关知识&#xff0c;跟着我一起学习吧&#xff01;&#xff01; &#x1f388;什么是文件 磁盘上的文件是文件。 但是在程序设计中&#xff0c;我们一般谈的文件有两种&#xff1a;程序文件、数据文件 程序文…...

【Unity】坐标转换经纬度方法(应用篇)

【Unity】坐标转换经纬度方法&#xff08;应用篇&#xff09; 解决地图中经纬度坐标转换与unity坐标互转的问题。使用线性变换的方法&#xff0c;理论上可以解决小范围内所以坐标转换的问题。 之前有写过[Unity]坐标转换经纬度方法&#xff08;原理篇),在实际使用中&#xff0c…...

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 年外包,已经废了

如果不是女朋友和我提分手&#xff0c;我估计现在还没醒悟 本科大专&#xff0c;17年通过校招进入某软件公司做测试&#xff0c;干了接近5年的功能。 今年年初&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落&#xff01;而我已经…...

day-23 代码随想录算法训练营(19)part09

669.修剪二叉搜索树 思路一&#xff1a;根据二叉搜索树的特性进行中间值与去区间值判断&#xff0c;有三种情况&#xff1a;1.在区间中&#xff0c;所以左右子树都可能在区间中&#xff1b; 2.在区间外面的左侧&#xff0c;必然只有右子树可能存在区间中&#xff1b;3.在区间外…...

JVM编译优化

即时编译器 HotSpot虚拟机中内置了两个即时编译器,分别称为Client Compiler和Server Compiler,或者简称为C1编译器和C2编译器。Java8默认开启Server模式。用户可以使用“-client”或“-server”参数去指定编译模式。 C1编译器启动速度快,关注局部简单可靠的优化,比如方法…...

vue浏览器插件安装-各种问题

方法1&#xff1a;vue.js devtolls插件下载 https://blog.csdn.net/qq_55640378/article/details/131553642 下载地址&#xff1a; Tags vuejs/devtools GitHub npm install 或是 cnpm install 遇到的报错 设置淘宝镜像源&#xff08;推荐使用nrm&#xff0c;这一步是为…...

maven工具-maven的使用-镜像仓库、本地仓、IDEA使用maven

Maven 一、为什么使用maven 添加第三方jar包jar包之间的依赖关系处理jar包之间的冲突获取第三方jar包将项目拆分成多个工程模块实现项目的分布式部署 二、maven简介 ​ Maven项目对象模型(POM)&#xff0c;可以通过一小段描述信息来管理项目的构建&#xff0c;报告和文档的…...

Mac鼠标增强工具Smooze Pro

Smooze Pro是一款Mac上的鼠标手势增强工具&#xff0c;可以让用户使用鼠标手势来控制应用程序和系统功能。 它支持多种手势操作&#xff0c;包括单指、双指、三指和四指手势&#xff0c;并且可以自定义每种手势的功能。例如&#xff0c;您可以使用单指向下滑动手势来启动Expos视…...

数据结构-单链表(C语言简单实现)

简介 以顺序结构进行数据存储时&#xff0c;它的特点就是可以用一组任意的存储单元存储数据元素&#xff0c;这组存储单元可以是连续的&#xff0c;也可以是不连续的&#xff0c;这些数据可以存在内存未被占用的任意位置。它也是有缺点的&#xff0c;就是在插入和删除时需要移…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

YSYX学习记录(八)

C语言&#xff0c;练习0&#xff1a; 先创建一个文件夹&#xff0c;我用的是物理机&#xff1a; 安装build-essential 练习1&#xff1a; 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件&#xff0c;随机修改或删除一部分&#xff0c;之后…...

基于数字孪生的水厂可视化平台建设:架构与实践

分享大纲&#xff1a; 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年&#xff0c;数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段&#xff0c;基于数字孪生的水厂可视化平台的…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...