当前位置: 首页 > 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;就是在插入和删除时需要移…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...