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

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

链式法则中 复合函数的推导路径 多变量“信息传递路径”

非常好&#xff0c;我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题&#xff0c;统一使用 二重复合函数&#xff1a; z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y))​ 来全面说明。我们会展示其全微分形式&#xff08;偏导…...

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

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的有价值数据。如何高效地采集这些数据并将其应用于实际业务中,成为了许多企业和开发者关注的焦点。网络爬虫技术作为一种自动化的数据采集工具,可以帮助我们从网页中提取所需的信息。而 RESTful API …...

RushDB开源程序 是现代应用程序和 AI 的即时数据库。建立在 Neo4j 之上

一、软件介绍 文末提供程序和源码下载 RushDB 改变了您处理图形数据的方式 — 不需要 Schema&#xff0c;不需要复杂的查询&#xff0c;只需推送数据即可。 二、Key Features ✨ 主要特点 Instant Setup: Be productive in seconds, not days 即时设置 &#xff1a;在几秒钟…...

新版NANO下载烧录过程

一、序言 搭建 Jetson 系列产品烧录系统的环境需要在电脑主机上安装 Ubuntu 系统。此处使用 18.04 LTS。 二、环境搭建 1、安装库 $ sudo apt-get install qemu-user-static$ sudo apt-get install python 搭建环境的过程需要这个应用库来将某些 NVIDIA 软件组件安装到 Je…...