【编程题】有效三角形的个数
文章目录
- 一、题目
- 二、算法讲解
- 三、题目链接
- 四、补充
一、题目
给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。
示例1:
输入: nums = [2,2,3,4]
输出: 3
**解释:**有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
示例2:
输入: nums = [4,2,3,4]
输出: 4
二、算法讲解
构成三角形的条件:任意两条边之和大于第三边,其实也就是较小的两条边之和大于最大的边,只要满足这个那么就一定是三角形。
思路1: 暴力枚举,三层循环,得到一个三角形的三条边,然后判断是否为三角形,但是时间复杂度为O(n3),可能会超时。
思路2: 可以通过双指针来模拟三层循环的过程,通过一些条件来规避三层循环。
- 首先对数据进行升序排序
- 将最后也就是最大的数设置为第三条边。
- 两个指针left和right分别指向数据开头和最大数的前一个位置
- 进行判断:
如果left和right的和大于最大的数,那么固定right,left++,两数之和都大于最大的数,因为该组数据是升序,这时候就相当于把right这个位置的数的每种可能都遍历了一遍,只要right-left计算一下三角形个数加到一起就行了,之后right–;
如果left和right的和小于最大的数,那么固定left,right–,每种情况都是小于最大的数的,这时候就相当于把left这个位置的数的每种可能都遍历了一遍,由于这种情况是不满足三角形的,只需要left++就行了。 - 最大的数位置-1,回到步骤3再次进行判断,直到最大数的位置到2(因为从0开始,0、1位置肯定不可能作为三角形最大的边)。
代码:
class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(),nums.end());int ret = 0;int n = nums.size();for(int i = n-1; i>=2; --i){int left=0,right=i-1;while(left<right){if((nums[left]+nums[right])>nums[i]){ret+=(right-left);right--;}else{left++;}}}return ret;}
};
三、题目链接
611. 有效三角形的个数
四、补充
类似的题目还有
11. 盛最多水的容器
相关文章:
【编程题】有效三角形的个数
文章目录 一、题目二、算法讲解三、题目链接四、补充 一、题目 给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。 示例1: 输入: nums [2,2,3,4] 输出: 3 **解释:**有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 …...
【mysql是怎样运行的】-EXPLAIN详解
文章目录 1.基本语法2. EXPLAIN各列作用1. table2. id3. select_type4. partitions5. type 1.基本语法 EXPLAIN SELECT select_options #或者 DESCRIBE SELECT select_optionsEXPLAIN 语句输出的各个列的作用如下: 列名描述id在一个大的查询语句中每个SELECT关键…...
数据结构例题代码及其讲解-链表
链表 单链表的结构体定义及其初始化。 typedef struct LNode {int data;struct LNode* next; }LNode, *LinkList;①强调结点 LNode *p; ②强调链表 LinkList p; //初始化 LNode* initList() {//定义头结点LNode* L (LNode*)malloc(sizeof(LNode));L->next NULL;return …...
[Open-source tool] 可搭配PHP和SQL的表單開源工具_Form tools(1):簡介和建置
Form tools是一套可搭配PHP和SQL的表單開源工具,可讓開發者靈活運用,同時其有數個表單模板和應用模組供挑選,方便且彈性。Form tools已開發超過20年,為不同領域的需求者或開發者提供一個自由和開放的平台,使他們可建構…...
移动数据业务价值链的整合
3G 时代移动数据业务开发体系的建立和发展,要求运营商从封闭、统一的业 务形态、单一提供业务,向开放的、个性化多元化的业务体系以及多方合作参与提 供业务的方向发展,不可避免的使通信价值链不断延长和升级,内容提供商、服务 …...
合并两个链表
题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 比如以下例子: 题目接口: /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListN…...
测试框架pytest教程(9)跳过测试skip和xfail
skip无条件跳过 使用装饰器 pytest.mark.skip(reason"no way of currently testing this") def test_example(faker):print("nihao")print(faker.words()) 方法内部调用 满足条件时跳过 def test_example():a1if a>0:pytest.skip("unsupported …...
HTML <textarea> 标签
实例 <textarea rows="3" cols="20"> 收拾收拾 </textarea>定义和用法 <textarea> 标签定义多行的文本输入控件。 文本区中可容纳无限数量的文本,其中的文本的默认字体是等宽字体(通常是 Courier)。 可以通过 cols 和 rows 属性来…...
探索图结构:从基础到算法应用
文章目录 理解图的基本概念学习图的遍历算法学习最短路径算法案例分析:使用 Dijkstra 算法找出最短路径结论 🎉欢迎来到数据结构学习专栏~探索图结构:从基础到算法应用 ☆* o(≧▽≦)o *☆嗨~我是IT陈寒🍹✨博客主页:I…...
Redis之GEO类型解读
目录 基本介绍 基本命令 geoadd 命令 geopos 命令 geodist 命令 georadius 命令 georadiusbymember 命令 geohash 命令 基本介绍 GEO 主要用于存储地理位置信息(纬度、经度、名称)添加到指定的key中。该功能在 Redis 3.2 版本新增。 GEO&…...
uniapp 微信小程序 路由跳转
保留当前页面,跳转到应用内的某个页面,使用uni.navigateBack可以返回到原页面 //在起始页面跳转到test.vue页面并传递参数 uni.navigateTo({url: test?id1&name"lisa" }); uni.redirectTo(OBJECT) 关闭当前页面,跳转到应用…...
【android12-linux-5.1】【ST芯片】HAL移植后没调起来
ST传感器芯片HAL按官方文档移植后,测试一直掉不起来,加的日志没出来。经过分析,是系统自带了一个HAL,影响的。 按照官方文档,移植HAL后,在/device/<vendor\>/<board\>/device.mk*路径增加PROD…...
Redis Lua脚本执行原理和语法示例
Redis Lua脚本语法示例 文章目录 Redis Lua脚本语法示例0. 前言参考资料 1. Redis 执行Lua脚本原理1.1. 对Redis源码中嵌入Lua解释器的简要解析:1.2. Redis Lua 脚本缓存机制 2. Redis Lua脚本示例1.1. 场景示例1. 请求限流2. 原子性地从一个list移动元素到另一个li…...
百望云华为云共建零售数字化新生态 聚焦数智新消费升级
零售业是一个充满活力和创新的行业,但也是当前面临很大新挑战和新机遇的行业。数智新消费时代,数字化转型已经成为零售企业必须面对的重要课题。 8 月 20 日-21日,以“云上创新 韧性增长”为主题的华为云数智新消费创新峰会2023在成都隆重召…...
JMETER基本原理
Jmeter基本原理是建立一个线程池,多线程运行取样器产生大量负载,在运行过程中通过断言来验证结果的正确性,可以通过监听来记录测试结果; JMETER是运行在JVM虚拟机上的,每个进程的开销比loadrunner的进程开销大&#x…...
elementUI自定义上传文件 前端后端超详细过程
下面是使用Element UI自定义上传文件的前后端详细过程: 前端过程: 引入Element UI组件库:在前端项目中引入Element UI库,可以通过CDN引入或者通过npm安装并导入。 创建上传组件:在前端代码中创建一个上传组件&#x…...
快速排序笔记
一、quick_sort方法中如果 il,jr 会死循环的分析 1、示例代码 void quick_sort(int a[],int l,int r){if(l>r) return;int il,jr; //此处设置会导致死循环int x num[(lr)>>1];while(i<j){while(a[i] <x); //死循环的地方while(a[--j] >x);if(i<j) swap(a…...
JAVA:(JSON反序列化Long变成了Integer)java.lang.Integer cannot be cast to java.lang.Long
困扰了好几个小时。。。 场景:mybatisplus从数据库取数据,只是用了最基础的 LambdaQueryWrapper 来查询,实体类如下。 TableField(typeHandler JacksonTypeHandler.class) private Set<Long> ids; 得到的Set数据却是Set<Integer…...
ui设计师简历自我评价(合集)
UI设计最新面试题及答案 1、说说你是怎么理解UI的? UI是最直观的把产品展示展现在用户面前的东西,是一个产品的脸面。人开始往往是先会先喜欢上美好的事物后,在去深究内在的东西的。 那么也就意味着一个产品的UI首先要做的好看,无论风格是…...
Nginx 反向代理
一. Nginx 反向代理 1.1 反向代理介绍 在计算机网络中,反向代理一般指代理服务器,其首先代替内网的服务器接收客户端请求 并从一个或多个服务器检索资源,然后将这些资源返回给客户端。在客户端看来,这些资 源就好像来自代理服务…...
Label Studio实战:如何为NLP项目自定义标注模板(含模板代码分享)
Label Studio实战:如何为NLP项目自定义标注模板(含模板代码分享) 在自然语言处理项目中,数据标注的质量往往直接决定模型性能的上限。Label Studio作为当前最主流的开源标注工具之一,其灵活的自定义模板功能让NLP工程师…...
AnythingtoRealCharacters2511应用案例:为小说角色生成真人参考形象
AnythingtoRealCharacters2511应用案例:为小说角色生成真人参考形象 1. 引言:从动漫到真人的魔法转换 想象一下,当你阅读一本精彩的小说时,脑海中浮现的角色形象突然变得栩栩如生。这正是AnythingtoRealCharacters2511能够实现的…...
革新性PDF打印解决方案:PDFtoPrinter全场景应用指南
革新性PDF打印解决方案:PDFtoPrinter全场景应用指南 【免费下载链接】PDFtoPrinter .Net Wrapper over PDFtoPrinter util allows to print PDF files. 项目地址: https://gitcode.com/gh_mirrors/pd/PDFtoPrinter 价值定位:重新定义PDF打印体验…...
OpenClaw日志分析进阶:百川2-13B-4bits量化模型自动错误诊断
OpenClaw日志分析进阶:百川2-13B-4bits量化模型自动错误诊断 1. 为什么需要自动化日志分析 深夜两点,我的手机突然震动起来——服务器又报警了。强撑着睡意打开终端,面对满屏的报错日志,那种无力感相信每个运维人都深有体会。传…...
RWKV7-1.5B-g1a参数详解教程:temperature/top_p/max_new_tokens调优指南
RWKV7-1.5B-g1a参数详解教程:temperature/top_p/max_new_tokens调优指南 1. 模型简介 rwkv7-1.5B-g1a 是基于 RWKV-7 架构的多语言文本生成模型,特别适合以下场景: 基础问答文案续写简短总结轻量中文对话 这个模型在单卡 24GB 显存的设备上…...
Mojo项目无法import本地.py模块?工程师连夜修复的6种路径/环境变量/Loader级配置错误
第一章:Mojo项目无法import本地.py模块的根本原因剖析Mojo 语言虽兼容 Python 语法,但其运行时环境与 CPython 截然不同——它基于 LLVM 编译为原生机器码,并通过 Mojo Runtime 执行,**不依赖 Python 解释器进程**。因此ÿ…...
【亲测】OpenClaw怎么部署?2026年OpenClaw华为云8分钟搭建喂奶级教程
【亲测】OpenClaw怎么部署?2026年OpenClaw华为云8分钟搭建喂奶级教程。OpenClaw能做什么?OpenClaw怎么部署?本文面向零基础用户,完整说明在轻量服务器与本地Windows11、macOS、Linux系统中部署OpenClaw(Clawdbot&#…...
OpenClaw日志分析:QwQ-32B任务执行效率监控
OpenClaw日志分析:QwQ-32B任务执行效率监控 1. 为什么需要监控OpenClaw任务执行效率 去年冬天,我部署了一个自动整理会议纪要的OpenClaw工作流。起初运行得很顺利,直到某天早上发现它漏掉了三场重要会议的记录。检查日志才发现,…...
互联网大厂 Java 面试实战:一次“高并发系统追问”下的真实对话
在大多数 Java 面试中,真正拉开差距的从来不是“你会多少知识点”,而是当系统出现问题时,你是否知道该怎么扛。很多候选人熟悉各种八股文,但一旦进入场景题就会卡住。下面通过一场更贴近真实大厂风格的面试,对话式还原…...
LeagueAkari终极指南:智能游戏辅助工具快速上手与深度配置
LeagueAkari终极指南:智能游戏辅助工具快速上手与深度配置 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit 你是否曾在…...
