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

611.有效的三角形个数

1.题目解析

给定一个包含非负整数的数组 nums ,返回其中可以组成三角形三条边的三元组个数。

补充:

1.三角形的判断:假设有三条边按大小排序:

 2.题目示例

示例 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

 分析题目可知是要算上重复的

3.算法分析:

①暴力枚举:

时间复杂度较高O(3*n^3)

三层for循环确定三条边,再定义一个计数器计算有小三角形的个数

//暴力枚举public int triangleNumber(int[] nums) {Arrays.sort(nums);int count=0;int len=nums.length;for(int i=0;i<len;i++){for(int j=i+1;j<len;j++){for(int k=j+1;k<len;k++){if(nums[i]+nums[j]>nums[k]){count++;}}}}return count;}

集美们,不用跑了,我帮你们试过了,过不了

解法二:

利用单调性和双指针的方法:

举个例子:

2,2,3,4,5,6,7,8,9,10

1.设置一个最大值

2.在最大数的左区间内,使用双指针和单调性的方法计算出有效三角形的个数

本宝宝建议你自己画一画,真正理解这个算法。

 会出现两种情况:

①left+right>max           count+=right-left right--

②left+right=<max         lrft++

 代码实现:

 public int triangleNumber(int[] nums) {int len=nums.length;int count=0;for(int i=len-1;i>=0;i--){int max=nums[i];int left=0;int right=i-1;while (left<right){if(nums[left]+nums[right]>max){count+=right-left;right--;}else{left++;}}}return  count;}

当然这个代码你是跑不过的,为什么呢?

因为你无法确定最大值,我举的栗子正好是我排过序的,若是没有排过序,不仅找不到最大值,还无用大学生的方法判断是否是有效三角形,所以一定要先排序(这都是姐走过的弯路)

 public int triangleNumber(int[] nums) {Arrays.sort(nums);int len=nums.length;int count=0;for(int i=len-1;i>=0;i--){int max=nums[i];int left=0;int right=i-1;while (left<right){if(nums[left]+nums[right]>max){count+=right-left;right--;}else{left++;}}}return  count;}

 本题完,欢迎指正

相关文章:

611.有效的三角形个数

1.题目解析 给定一个包含非负整数的数组 nums &#xff0c;返回其中可以组成三角形三条边的三元组个数。 补充&#xff1a; 1.三角形的判断&#xff1a;假设有三条边按大小排序&#xff1a; 2.题目示例 示例 1: 输入: nums [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用…...

超详细,使用JavaScript获取短信验证码

一、引言 短信验证码的重要性已经不言而喻,那么如何使用avaScript获取短信验证码呢?今天小编就整理了超详细的攻略,请各位看好~ 二、准备工作 1.注册短信服务提供商 注册并登录你的短信平台,然后获取AppID和AppKey,注册地址在代码里 2.创建验证码模版 三、实现步骤 …...

利用 Python 进行数据分析实验(七)

一、实验目的 使用Python解决问题 二、实验要求 自主编写并运行代码&#xff0c;按照模板要求撰写实验报告 三、实验步骤 操作书上第九章内容请画出如图2.png所示的图形通过编码获得fcity.jpg的手绘图像&#xff08;如beijing.jpg所示&#xff09; 四、实验结果 T2 &qu…...

前端小技巧: 写一个异步程序示例, 使用任务队列替代promise和async/await等语法糖

异步程序设定场景 1 &#xff09;场景设定 可以使用懒人每做几件事&#xff0c;就要休息一会儿&#xff0c;并且不会影响做事的顺序这种场景来模拟定义单例名称为: lazyMan支持 sleep 和 eat 两个方法支持链式调用 2 ) 调用示例 const lm new LazyMan(www) lm.eat(苹果).…...

【Windows下】Eclipse 尝试 Mapreduce 编程

文章目录 配置环境环境准备连接 Hadoop查看 hadoop 文件 导入 Hadoop 包创建 MapReduce 项目测试 Mapreduce 编程代码注意事项常见报错 配置环境 环境准备 本次实验使用的 Hadoop 为 2.7.7 版本&#xff0c;实验可能会用到的文件 百度网盘链接&#xff1a;https://pan.baidu…...

Python---time库

目录 时间获取 时间格式化 程序计时 time库包含三类函数&#xff1a; 时间获取&#xff1a;time() ctime() gmtime() 时间格式化&#xff1a;strtime() strptime() 程序计时&#xff1a;sleep() perf_counter() 下面逐一介绍&#…...

unity 自由框选截图(两种方法,亲测有效)

提示&#xff1a;文章有错误的地方&#xff0c;还望诸位大神不吝指教&#xff01; 文章目录 前言一、第一种方法&#xff08;1&#xff09;简介GL&#xff08;2&#xff09; GL 用法&#xff1a;&#xff08;3&#xff09;具体代码 二、第二种方法第一步&#xff1a;第二步第三…...

项目代码规范

editorconfig EditorConfig 是一种用于统一不同编辑器和 IDE 的代码风格的文件格式和插件&#xff0c;帮助开发人员在不同的编辑器和 IDE 中保持一致的代码风格&#xff0c;从而提高代码的可读性和可维护性 # EditorConfig is awesome: https://EditorConfig.org root true[…...

STM32的BKP与RTC简介

芯片的供电引脚 引脚表橙色的是芯片的供电引脚&#xff0c;其中VSS/VDD是芯片内部数字部分的供电&#xff0c;VSSA/VDDA是芯片内部模拟部分的供电&#xff0c;这4组以VDD开头的供电都是系统的主电源&#xff0c;正常使用时&#xff0c;全部都要接3.3V的电源上&#xff0c;VBAT是…...

11.Java安卓程序设计-基于SSM框架的Android平台健康管理系统的设计与实现

摘要 随着人们生活水平的提高和健康意识的增强&#xff0c;健康管理系统在日常生活中扮演着越来越重要的角色。本研究旨在设计并实现一款基于SSM框架的Android平台健康管理系统&#xff0c;为用户提供全面的健康监测和管理服务。 在需求分析阶段&#xff0c;我们明确了系统的…...

jetbrains卡顿(Pycharm等全家桶)终极解决方案,肯定解决!非常肯定!

话越短&#xff0c;越有用&#xff0c;一共四种方案&#xff0c;肯定能解决&#xff01;&#xff01;&#xff01;非常肯定&#xff01;&#xff01; 下面四种解决方案&#xff0c;笔者按照实际体验后的结果&#xff0c;按照优先级从高到低排序。你只要按顺序试试就知道了。 m…...

c++的排序算法

一&#xff1a;merge 是 C STL 中的一个算法函数&#xff0c;用于将两个已排序的序列合并成一个有序序列。 template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare> OutputIterator merge(InputIterator1 first1, InputIterator1 …...

YOLOv5独家原创改进:SPPF自研创新 | SPPF与感知大内核卷积UniRepLK结合,大kernel+非膨胀卷积提升感受野

💡💡💡本文自研创新改进:SPPF与感知大内核卷积UniRepLK结合,大kernel+非膨胀卷积,使SPPF增加大kernel,提升感受野,最终提升检测精度 收录 YOLOv5原创自研 https://blog.csdn.net/m0_63774211/category_12511931.html 💡💡💡全网独家首发创新(原创),…...

【C/PTA —— 15.结构体2(课外实践)】

C/PTA —— 15.结构体2&#xff08;课外实践&#xff09; 7-1 一帮一7-2 考试座位号7-3 新键表输出7-4 可怕的素质7-5 找出同龄者7-6 排队7-7 军训 7-1 一帮一 #include<stdio.h> #include<string.h>struct student {int a;char name[20]; };struct student1 {int …...

艾泊宇产品战略:适应新消费时代,产品战略指南以应对市场挑战和提升盈利

赚钱越来越难&#xff0c;这是许多企业和个人都感到困惑的问题。 然而&#xff0c;艾泊宇产品战略告诉大家&#xff0c;我们不能把这个问题简单地归咎于经济环境或市场竞争&#xff0c;而是需要从更深层次去思考和解决。 本文将从多个角度去剖析这个问题&#xff0c;并探讨在…...

使用autodl服务器,两个3090显卡上运行, Yi-34B-Chat-int4模型,并使用vllm优化加速,显存占用42G,速度23 words/s

1&#xff0c;演示视频地址 https://www.bilibili.com/video/BV1Hu4y1L7BH/ 使用autodl服务器&#xff0c;两个3090显卡上运行&#xff0c; Yi-34B-Chat-int4模型&#xff0c;用vllm优化&#xff0c;增加 --num-gpu 2&#xff0c;速度23 words/s 2&#xff0c;使用3090显卡 和…...

ORACLE数据库实验总集 实验六 SQL 语句应用

一、 实验目的 &#xff08;1&#xff09; 掌握数据的插入&#xff08;INSERT&#xff09;、 修改&#xff08;UPDATE&#xff09; 和删除&#xff08;DELETE&#xff09; 操作。 &#xff08;2&#xff09; 掌握不同类型的数据查询&#xff08;SELECT&#xff09; 操作。 二、…...

[FPGA 学习记录] 快速开发的法宝——IP核

快速开发的法宝——IP核 文章目录 1 IP 核是什么2 为什么要使用 IP 核3 IP 核的存在形式4 IP 核的缺点5 Quartus II 软件下 IP 核的调用6 Altera IP 核的分类 在本小节当中&#xff0c;我们来学习一下 IP 核的相关知识。 IP 核在 FPGA 开发当中应用十分广泛&#xff0c;它被称为…...

每日一题:LeetCode-11.盛水最多的容器

每日一题系列&#xff08;day 13&#xff09; 前言&#xff1a; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f308; &#x1f50e…...

查看电脑cuda版本

1.找到NVODIA控制面板 输入NVIDIA搜索即可 出现NVIDIA控制面板 点击系统信息 2.WINR 输入nvidia-smi 检查了一下&#xff0c;电脑没用过GPU&#xff0c;连驱动都没有 所以&#xff0c;装驱动…… 选版本&#xff0c;下载 下载后双击打开安装 重新输入nvidia-smi 显示如下…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

PAN/FPN

import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...