【编程题】有效三角形的个数
文章目录
- 一、题目
- 二、算法讲解
- 三、题目链接
- 四、补充
一、题目
给定一个包含非负整数的数组 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 反向代理介绍 在计算机网络中,反向代理一般指代理服务器,其首先代替内网的服务器接收客户端请求 并从一个或多个服务器检索资源,然后将这些资源返回给客户端。在客户端看来,这些资 源就好像来自代理服务…...
3步搞定ERPNext自动化部署:让企业管理系统安装变得简单
3步搞定ERPNext自动化部署:让企业管理系统安装变得简单 【免费下载链接】erpnext_quick_install Unattended install script for ERPNext Versions, 13, 14 and 15 项目地址: https://gitcode.com/gh_mirrors/er/erpnext_quick_install 还在为复杂的ERPNext安…...
springboot框架-美妆化妆品商城进货系统
目录系统架构设计技术选型与依赖数据库设计核心功能实现库存预警机制前端交互建议测试与部署扩展性考虑项目技术支持源码获取详细视频演示 :文章底部获取博主联系方式!同行可合作系统架构设计 采用SpringBoot MyBatis-Plus MySQL构建后端,…...
Teensy41嵌入式FTP服务器库:轻量协议栈与多网络适配
1. 项目概述FTP_Server_Teensy41 是一款专为 Teensy 4.x 系列微控制器(特别是 Teensy 4.0 和 Teensy 4.1)深度定制的嵌入式 FTP 服务器库。它并非从零构建,而是基于 Jean-Michel Gallego 开发的成熟开源项目 Arduino-Ftp-Server 进行了系统性…...
效率革命:设计师必备的Sketch批量命名神器RenameIt完全指南
效率革命:设计师必备的Sketch批量命名神器RenameIt完全指南 【免费下载链接】RenameIt Keep your Sketch files organized, batch rename layers and artboards. 项目地址: https://gitcode.com/gh_mirrors/re/RenameIt 在现代UI/UX设计流程中,保…...
终极指南:用EdgeRemover快速彻底卸载微软Edge浏览器
终极指南:用EdgeRemover快速彻底卸载微软Edge浏览器 【免费下载链接】EdgeRemover PowerShell script to remove Microsoft Edge in a non-forceful manner. 项目地址: https://gitcode.com/gh_mirrors/ed/EdgeRemover 还在为Windows系统中无法彻底移除Micro…...
强强联合!望石智慧携手华为、华鲲振宇发布AI药物研发联合解决方案,共筑中国智慧医药创新生态
近日,以“因聚而升 融智有为”为主题的华为中国合作伙伴大会2026在深圳圆满落幕。望石智慧作为其国内AI驱动医药创新领域的核心技术伙伴受邀参会,并在智能制造医药行业论坛发表演讲。会议期间,望石智慧、华为、华鲲振宇三方达成战略级生态合作…...
告别Transformer!用PyTorch从零实现MLP-Mixer图像分类(附完整代码与调参技巧)
告别Transformer!用PyTorch从零实现MLP-Mixer图像分类(附完整代码与调参技巧) 在计算机视觉领域,Transformer架构近年来风头无两,但你是否想过——仅用多层感知机(MLP)也能构建高性能视觉模型&a…...
告别手动Dockerfile!io.fabric8插件如何用Maven配置自动生成镜像(附Spring Boot实战)
告别手动Dockerfile!io.fabric8插件如何用Maven配置自动生成镜像(附Spring Boot实战) 在Java生态中,容器化部署已成为现代应用交付的标准方式。传统做法要求开发者同时维护Dockerfile和构建脚本,这种割裂的配置方式不仅…...
DeepSeek-R1-Distill-Qwen-7B功能体验:Ollama部署后,实测推理速度提升3倍
DeepSeek-R1-Distill-Qwen-7B功能体验:Ollama部署后,实测推理速度提升3倍 1. 模型背景与核心优势 1.1 模型技术背景 DeepSeek-R1-Distill-Qwen-7B是华为昇腾与阿里达摩院技术协作的产物,通过知识蒸馏技术将DeepSeek-R1(660B参数…...
Cadence导出Gerber文件保姆级教程:从Database Check到嘉立创预览,一步不落
Cadence导出Gerber文件全流程实战:从设计验证到生产准备的深度指南 第一次在Cadence Allegro中导出Gerber文件时,那种面对几十个参数选项的手足无措感我至今记忆犹新。作为电子设计自动化(EDA)领域的工业标准工具,Cadence的强大功能背后是复杂…...
