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

算法训练篇06--力扣611.有效三角形的个数

目录

1.题目链接:611.有效三角形的个数

2.题目描述:

3.解法一:(暴力解法)(会超时):

4.解法二(排序+双指针)


1.题目链接:611.有效三角形的个数

2.题目描述:
 

给定一个包含非负整数的数组 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

3.解法一:(暴力解法)(会超时):

算法思路:
三层for循环枚举出所有的三元组,并且判断是否能构成三角形。

虽然说是暴力求解,但是还是可以优化一下:

判断三角形的优化

  • 如果能构成三角形,需要满足任意两边之和大于第三边。但是实际上只需让较小的两条边之和大于第三边既可。
  • 因此我们可以先将原数组排序,然后从小到大枚举三元组,一方面省去枚举的数量,另一方面方便判断是否能构成三角形。
class Solution
{
public:int triangleNumber(vector<int>& nums){//1.排序sort(nums.begin(), nums.end());int n = nums.size(), ret = 0;//2.从小到大枚举所有的三元组for (int i = 0; i < n; i++){for (int j = i + 1; j < n; j++){for (int k = j + 1; k < n; k++){   //当最小的两个边之和大于第三个边的时候,统计答案if (nums[i] + nums[i] > nums[k])ret++;}}}return ret;}
};

4.解法二(排序+双指针)

算法思路:

先将数组排序。

根据解法一中的优化思想,我们可以固定一个最长边,然后在比这条边小的有序数组中找出一个二元组,使这个二元组之和大于这个最长边。由于数组使有序的,我们可以利用对撞指针来优化。

设最长边枚举到i位置,区间[left,right]是i位置左边的区间(也就是比他小的区间):

  • 如果nums[left] + nums[right] > nums[i]:
    说明[left,right-1]区间上的所有元素均可以与nums[right]构成比nums[i]大的二元组            满足条件的有right - left种                                                                                                  此时right位置的元素的所有情况相当于全部考虑完毕,right--,进入下一轮判断
  • 如果nums[left] + nums[right] <= nums[i]:
    说明left位置的元素是不可能与[left+1,right]位置上的元素构成满足条件的二元组               left位置的元素可以舍去,left++进入下轮循环
class Solution {
public:int triangleNumber(vector<int>& nums) {int sum = 0,n = nums.size();sort(nums.begin(),nums.end());for(int i = n - 1;i>=2;i--){int left = 0,right = i-1;while(left<right){if(nums[left] + nums[right] > nums[i]){sum += (right - left);right--;}else{left++;}}}return sum;}
};

相关文章:

算法训练篇06--力扣611.有效三角形的个数

目录 1.题目链接&#xff1a;611.有效三角形的个数 2.题目描述&#xff1a; 3.解法一&#xff1a;(暴力解法)(会超时)&#xff1a; 4.解法二(排序双指针) 1.题目链接&#xff1a;611.有效三角形的个数 2.题目描述&#xff1a; 给定一个包含非负整数的数组 nums &#xf…...

Gin框架学习

一.介绍 Gin是一个用Go语言编写的web框架。它是一个类似于martini但拥有更好性能的API框架, 由于使用了httprouter&#xff0c;速度提高了近40倍。 如果你是性能和高效的追求者, 你会爱上Gin。 下载 go get -u github.com/gin-gonic/gin 二.Gin示例 学习的时候&#xff0c;写在…...

青少年编程与数学 02-011 MySQL数据库应用 07课题、表的操作

青少年编程与数学 02-011 MySQL数据库应用 07课题、表的操作 一、数据库表&#xff08;Table&#xff09;二、创建表语法格式示例注意事项 三、字段的命名规则基本规则命名规范建议示例 四、字段数据类型数值类型字符串类型日期和时间类型其他类型 五、选择合适的数据类型1. **…...

【详细解决】pycharm 终端出现报错:“Failed : 无法将“Failed”项识别为 cmdlet、函数、脚本文件或可运行程序的名称。

昨天在终端一顿操作后突然打开pycharm时就开始报错&#xff1a; 无法将“Failed”项识别为 cmdlet、函数、脚本文件或可运行程序的名称。请检查名称的拼写&#xff0c;如果包括路径&#xff0c;请确保路径正确&#xff0c;然后再试一次。 所在位置 行:1 字符: 1 Failed to act…...

AcWing 839:模拟堆 ← multiset + unordered_map

【题目来源】 https://www.acwing.com/problem/content/841/ 【题目描述】 维护一个集合&#xff0c;初始时集合为空&#xff0c;支持如下几种操作&#xff1a; 1. I x&#xff0c;插入一个数 x&#xff1b; 2. PM&#xff0c;输出当前集合中的最小值&#xff1b; 3. DM&#…...

cmake教程

CMake 是一个跨平台的自动化构建系统&#xff0c;广泛用于管理软件构建过程。它使用 CMakeLists.txt 文件来配置项目的构建过程&#xff0c;并生成适用于不同编译器和操作系统的构建文件&#xff08;如 Makefile、Visual Studio 项目文件等&#xff09;。以下是一个简单的 CMak…...

小蓝的括号串1(栈,蓝桥云课)

问题描述 小蓝有一个长度为 nn 的括号串&#xff0c;括号串仅由字符 ( 、 ) 构成&#xff0c;请你帮他判断一下该括号串是否合法&#xff0c;合法请输出 Yes &#xff0c;反之输出 No 。 合法括号序列&#xff1a; 空串是合法括号序列。 若 ss 是合法括号序列&#xff0c;则 (…...

软考系统架构设计师考试学习和考试的知识点大纲,覆盖所有考试考点

以下是软考系统架构设计师考试的知识点大纲&#xff0c;覆盖所有官方考点&#xff0c;分为基础知识、核心技术、系统设计、案例分析、论文写作五大模块&#xff0c;帮助系统性学习和备考&#xff1a; 一、基础知识模块 计算机组成与体系结构 计算机硬件组成&#xff08;CPU、内…...

车载以太网网络测试-18【传输层-DOIP协议-1】

目录 1 摘要2 DOIP协议的概述2.1 DOIP协议背景2.2 ISO 13400概述 3 DOIP报文的帧结构以及实例3.1 DOIP报文帧结构3.2 实例示例 总结 1 摘要 在汽车网络通信中&#xff0c;诊断扮演了非常重要的角色&#xff0c;无论是故障诊断、整车下线配置&#xff0c;还是ECU的软件更新、远…...

密码学(Public-Key Cryptography and Discrete Logarithms)

Public-Key Cryptography and Discrete Logarithms Discrete Logarithm 核心概念&#xff1a;离散对数是密码学中一个重要的数学问题&#xff0c;特别是在有限域和循环群中。它基于指数运算在某些群中是单向函数这一特性。也就是说&#xff0c;给定一个群 G G G和一个生成元 …...

自然语言处理|深入解析 PEGASUS:从原理到实践

一、引言 在信息爆炸的时代&#xff0c;互联网上的文本数据以极快的速度增长。无论是新闻资讯、学术论文、社交媒体动态&#xff0c;还是各类报告文档&#xff0c;我们每天接触到的文字信息量巨大。如何快速、准确地提取关键内容成为一项重要任务。文本摘要技术通过将长篇文本…...

矩阵指数的定义和基本性质

1. 矩阵指数的定义 矩阵指数 e A t e^{\boldsymbol{A}t} eAt 定义为幂级数的形式&#xff1a; e A t ∑ k 0 ∞ ( A t ) k k ! e^{\boldsymbol{A}t} \sum_{k0}^\infty \frac{(\boldsymbol{A}t)^k}{k!} eAtk0∑∞​k!(At)k​ 当 A \boldsymbol{A} A 为 n n n \times n …...

react 技术栈请问该如何优化 DOM 大小

针对 React 应用中 DOM 大小过大 的问题&#xff0c;以下是详细的优化方案和具体操作步骤&#xff0c;帮助你提升 Lighthouse 性能评分和用户体验&#xff1a; 一、问题根源分析 DOM 大小过大&#xff08;如超过 1500 个节点或深度超过 32 层&#xff09;会导致&#xff1a; …...

redis,tar.gz安装后,接入systemctl报错解决

1. WARNING Memory overcommit must be enabled! 这种报错&#xff0c;有两种解决方法 1.1 修改系统参数 编辑 /etc/sysctl.conf 文件&#xff0c;设置 overcommit_memory 为 1 vm.overcommit_memory 11.2 修改redis的最大使用内存 修改配置文件 redis.conf maxmemory 1g…...

YOLOv5部署全场景问题解决方案手册(2025版)

YOLOv5部署全场景问题解决方案手册&#xff08;2025版&#xff09; 文章目录 YOLOv5部署全场景问题解决方案手册&#xff08;2025版&#xff09;[TOC]一、环境配置问题1.1 CUDA与PyTorch版本冲突1.2 依赖库缺失问题 二、模型转换问题2.1 ONNX导出失败2.2 TensorRT转换问题 三、…...

Canal 解析与 Spring Boot 整合实战

一、Canal 简介 1.1 Canal 是什么&#xff1f; Canal 是阿里巴巴开源的一款基于 MySQL 数据库增量日志解析&#xff08;Binlog&#xff09;中间件&#xff0c;它模拟 MySQL 的从机&#xff08;Slave&#xff09;行为&#xff0c;监听 MySQL 主机的二进制日志&#xff08;Binl…...

AI第一天 自我理解笔记--微调大模型

目录 1. 确定目标&#xff1a;明确任务和数据 2. 选择预训练模型 3. 数据预处理 (1) 数据清洗与格式化 (2) 划分数据集 (4) 数据加载与批处理 4. 构建微调模型架构 (1) 加载预训练模型 (2) 修改模型尾部&#xff08;适配任务&#xff09; (3) 冻结部分层&#xff08;…...

SpringBoot日志

目录 一、日志的用途 二、日志的使用 1.打印日志 2.在程序中得到日志对象 3.使用日志对象打印日志 4.日志格式说明 5.日志框架的了解 门面模式&#xff08;外观模式&#xff09; 6.日志级别 7.日志配置 配置日志级别 日志持久化 配置日志文件分割 配置日志格式 三、…...

Redis数据结构详解--列表

Redis 列表是简单的字符串列表&#xff0c;按照插入顺序排序&#xff0c;常用命令&#xff1a; LPUSH key value1 [value2...] 在列表头部插入一个或多个值RPUSH key value1 [value2...] 在列表尾部插入一个或多个值LPOP key 移除并获取列表头部第一个元素RPOP key 移除并获取…...

[项目]基于FreeRTOS的STM32四轴飞行器: 六.2.4g通信

基于FreeRTOS的STM32四轴飞行器: 六.2.4g通信 一.Si24Ri原理图二.Si24R1芯片手册解读三.驱动函数讲解五.移植2.4g通讯&#xff08;飞控部分&#xff09;六.移植2.4g通讯&#xff08;遥控部分&#xff09;七.通讯模块的完成&#xff08;遥控部分&#xff09;七.通讯模块的完成&a…...

ElasticSearch 7.x 集群 + Kibana 部署完全指南(5节点)

ElasticSearch 7.x 集群 Kibana 部署完全指南&#xff08;5节点&#xff09; 一、基础环境准备 1. 系统要求 CentOS 7/Ubuntu 18.04JDK 11&#xff08;Elasticsearch 7自带JDK&#xff09;内存&#xff1a;建议每个节点≥8GB磁盘&#xff1a;≥50GB&#xff08;根据数据量调…...

前端项目中应该如何选择正确的图片格式

在前端项目中选择正确的图片格式是优化页面性能、提升用户体验的关键步骤之一。以下是常见图片格式的特点、适用场景及选择建议&#xff0c;帮助你在不同场景下做出最优决策&#xff1a; 一、常见图片格式对比 格式特点适用场景不适用场景JPEG- 有损压缩&#xff0c;文件小- 不…...

Python实现WYY音乐下载

一、需求背景 WYY音乐作为国内主流音乐平台,其歌曲资源丰富但下载接口存在多重加密保护。本文将通过Python结合JS逆向技术,解析其核心加密逻辑,实现免费歌曲的下载功能。 二、技术难点分析 1. 接口加密机制 通过抓包分析可知,网易云核心接口使用两次加密: 第一次:获取…...

药房链路轨道“空间拓扑优化+动态算法决策+多级容错控制”三重链式编程技术解析与应用

总论 随着智能医疗技术的快速发展&#xff0c;药房自动化系统已成为现代医院运营的核心基础设施。本文以“空间拓扑优化动态算法决策多级容错控制”三重链式编程技术为核心研究对象&#xff0c;探讨其如何通过跨学科技术融合实现药房链路轨道系统的精准化、高效化与可靠化运行…...

笔记本运行边缘计算

笔记本电脑可以用来运行PCDN&#xff08;Peer-to-Peer Content Delivery Network&#xff09;服务。实际上&#xff0c;如果你有闲置的笔记本电脑&#xff0c;并且它具备一定的硬件条件和网络环境&#xff0c;那么它可以成为一个不错的PCDN节点。 运行PCDN的基本要求 硬件需求…...

IMX8MP Android 10系统编译SDK

概述&#xff1a; 本文描述了在Ubuntu 20.04操作系统上搭建IMX8MP Android10系统编译环境。 ubuntu主机端设置 1. ubuntu 20.04 1. 450G Free Disk space 2. 16GB RAM以上 3. 安装 sudo apt-get install uuid uuid-dev zlib1g-dev liblz-dev liblzo2-2 liblzo2-dev lzop …...

项目实战:基于瑞萨RA6M5构建多节点OTA升级-创建系统最小框架<三>

MCUBoot项目创建完成后,接下来我们需要搭建多节点OTA系统最小框架,再将系统分模块搭建逐层完善,直到实现最终完整系统。开始动手干吧! 目录 一、创建项目 ​二、配置FSP ​2.1 配置RS485属性 ​2.2 配置定时器0 2.3 创建初始化进程并配置属性 ​2.4 创建RS485进程并…...

汇能感知高品质的多光谱相机VSC02UA

VSC02UA概要 VSC02UA是一款高品质的200万像素的光谱相机&#xff0c;适用于工业检测、农业、医疗等领域。VSC02UA 包含 1600 行1200 列有源像素阵列、片上 10 位 ADC 和图像信号处理器。它带有 USB2.0 接口&#xff0c;配合专门的电脑上位机软件使用&#xff0c;可进行图像采集…...

Fisher 信息矩阵公式原理:使用似然估计,二阶导数等知识点

Fisher 信息矩阵公式原理:使用似然估计,二阶导数等知识点 目录 Fisher 信息矩阵公式原理:使用似然估计,二阶导数等知识点Fisher 通过似然估计求解真实数据和权重参数之间的差异**1. Fisher 信息矩阵的定义****2. 计算对数似然函数的二阶导数****3. 代入 Fisher 信息矩阵定义…...

Xilinx系列FPGA视频采集转HDMI2.0输出,基于HDMI 1.4/2.0 Transmitter Subsystem方案,提供6套工程源码和技术支持

目录 1、前言工程概述免责声明 2、相关方案推荐我已有的所有工程源码总目录----方便你快速找到自己喜欢的项目我已有的 GT 高速接口解决方案我已有的FPGA图像处理方案 3、详细设计方案设计框图硬件设计架构FPGA开发板输入Sensor之-->OV5640摄像头动态彩条Video In To AXI4-S…...

dify重磅升级:从0.15.3安全升级1.1.0新手避坑指南

Docker Compose 部署 备份自定义的 docker-compose YAML 文件(可选) cd docker cp docker-compose.yaml docker-compose.yaml.-$(date +%Y-%m-%d-%H-%M).bak从 main 分支获取最新代码 git checkout main git pull origin main停止服务,命令,请在 docker 目录下执行...

工业相机选型

工业相机选型 一、工业相机分类二、相机的主要参数2.1 分辨率2.2 速度2.3 光学接口 / 接口类型2.4 相机靶面尺寸2.5 像元尺寸2.6 精度 三、镜头介绍及选型方法3.1 工作距离&#xff08;WD&#xff09;3.2 视场角(FOV)3.3 &#xff08;镜头&#xff09;靶面尺寸3.4 帧率3.5 光圈…...

Vue3:构建高效用户界面的利器

一、Vue.js 简介​ Vue.js&#xff08;读音 /vjuː/, 类似于 view&#xff09;是一套构建用户界面的渐进式框架。它只关注视图层&#xff0c;采用自底向上增量开发的设计。Vue 的目标是通过尽可能简单的 API 实现响应的数据绑定和组合的视图组件 &#xff0c;学习起来非常简单…...

mysql与redis的日志策略

MySQL 和 Redis 在日志记录方面采用了不同的策略&#xff0c;分别对应写前日志&#xff08;Write-Ahead Logging, WAL&#xff09;和写后日志&#xff08;Write-After Logging&#xff09;。以下是它们的详细说明&#xff1a; 1. MySQL&#xff1a;写前日志&#xff08;Write-A…...

在 Spring Boot 中调用 AnythingLLM 的发消息接口

整体逻辑: 自建系统的web UI界面调用接口: 1.SpringBoot接口&#xff1a;/anything/chatMessageAnything 2.调用anythingLLM - 调用知识库deepseek r1 . Windows Installation ~ AnythingLLMhttps://docs.anythingllm.com/installation-desktop/windows http://localhost:3…...

Kotlin 基础语法

1. &#x1f31f; Kotlin&#xff1a;Java 的“超级进化体”? Kotlin 是一门由 JetBrains 开发的 现代静态类型编程语言&#xff0c;支持 JVM、Android、JavaScript、Native 等多平台&#xff1a; Kotlin 与 Java 深度兼容&#xff0c;Kotlin 会编译为 JVM 字节码&#xff0c…...

设计模式使用Java案例

代码设计要有可维护性&#xff0c;可复用性&#xff0c;可扩展性&#xff0c;灵活性&#xff0c;所有要使用设计模式进行灵活设计代码 创建型 简单工厂模式&#xff08;Simple Factory&#xff09; 简单工厂模式&#xff08;Simple Factory Pattern&#xff09;是一种创建型…...

LORA的AB矩阵是针对Transformer的多头还是MLP

LORA的AB矩阵是针对Transformer的多头还是MLP Transformer中的矩阵是一个整体还是分开的每个小矩阵 在LORA(Low-Rank Adaptation)中,AB矩阵的应用位置和Transformer中的矩阵拆分方式如下: 1. LORA的AB矩阵作用对象 LORA的AB矩阵主要作用于Transformer的多头注意力模块和…...

【Gitee】删除仓库的详细步骤

文章目录 1、点击个人主页2、点击仓库3、点击想要删除的仓库4、点击管理5、点击侧边栏的删除仓库 1、点击个人主页 进入gitee官网&#xff0c;登录后点击个人主页 2、点击仓库 点击仓库跳转&#xff0c;如下图所示&#xff1a; 3、点击想要删除的仓库 这个页面会展示你所…...

DNS缓存使用中有什么问题?DNS缓存有哪些作用?

此前已经给大家介绍过刷新dns缓存的方法和流程以及dns缓存中毒和清楚dns缓存的知识介绍。那么你知道dns缓存使用中有什么问题吗?dns缓存有哪些作用? 以下是有关dns缓存的一些知识介绍。 一、DNS缓存使用中有什么问题? 1、缓存刷新不受控 当企业的域名发生变更时&#xf…...

Ollama + Open WebUI 本地部署DeepSeek

文章目录 前言一、环境准备最低系统要求必要软件 二、安装 Ollama通过 Docker 部署验证安装 三、部署 Open WebUI快速启动配置说明 四、加载 DeepSeek 模型通过 Ollama 拉取模型支持模型列表 五、使用 Web 界面交互首次使用功能特性 六、高级配置GPU 加速&#xff08;NVIDIA&am…...

STM32-汇编

学习arm汇编的主要目的是为了编写arm启动代码&#xff0c;启动代码启动以后&#xff0c;引导程序到c语言环境下运行。换句话说启动代码的目的是为了在处理器复位以后搭建c语言最基本的需求。因此启动代码的主要任务有&#xff1a; 初始化异常向量表&#xff1b; 初始化各工作模…...

word中老是有一个空白页删不掉

1、首先第一种&#xff1a;最后一页空白页删除方法 如果空白页是出现在最后一页的话&#xff0c;一般的删除方法是可行的&#xff0c;我们可以直接按Backspace或者Delete直接删除 2、缩小行距 如果空白页只有一行&#xff0c;而且还删不掉&#xff0c;我们可以在这一行点击鼠…...

docker需要sudo才能使用

一种方法是添加当前用户到docker组里去&#xff0c;当时添加的时候貌似是没问题的&#xff0c;但是现在又不可以了 产生的报错 ❯ docker images Cannot connect to the Docker daemon at unix:///home/ying/.docker/desktop/docker.sock. Is the docker daemon running?解决…...

Unity导出WebGL,无法显示中文

问题&#xff1a;中文无法显示 默认字体无法显示中文 在编辑器中设置了中文和英文的按钮&#xff0c;中文按钮无法显示 导出后无法显示中文 解决办法&#xff1a; 自己添加字体&#xff0c;导入项目&#xff0c;并引用 示例 下载一个字体文件&#xff0c;这里使用的阿里…...

理解大模型的function call ,思维链COT和MCP 协议

在大模型中&#xff0c;function call 是指模型调用外部功能或工具以完成特定任务的过程。这种机制使得模型不仅能生成文本&#xff0c;还能执行特定的操作&#xff0c;如生成图像、获取数据或进行计算。 关键特点 功能扩展&#xff1a;通过调用外部函数&#xff0c;模型可以实…...

K8S学习之基础三十三:K8S之监控Prometheus部署程序版

部署 Prometheus 通常包括以下步骤&#xff1a; 1. 下载 Prometheus 首先&#xff0c;从 Prometheus 官方网站 下载适用于你操作系统的最新版本。 bash 复制 wget https://github.com/prometheus/prometheus/releases/download/v2.30.0/prometheus-2.30.0.linux-amd64.tar…...

c语言笔记 结构体指针运用

目录 1.结构体指针与结构体变量 2.结构体指针与结构体数组 c语言其实有时候基本知识还是一样只是说换了一个名称但是所表示的含义是一样的。 结构体指针是指针的一种类型&#xff0c;可以指向结构体变量或者结构体数组&#xff0c;下面我们来探究一下结构体指针跟结构体变量的…...

科普类——双目立体视觉与 RGBD 相机的简单对比

双目立体视觉与 RGBD 相机生成的深度图在原理、性能和应用场景上有显著差异。以下是两者的详细对比和分析&#xff1a; 1. 原理差异 (1) 双目立体视觉 (Stereo Vision) 原理&#xff1a; 通过两个摄像头模拟人眼视差&#xff0c;计算匹配像素点的水平位移&#xff08;视差&…...

为什么要用linux?

使用 Linux 有许多独特的优势&#xff0c;尤其适合技术爱好者、开发者和企业用户。以下是 选择 Linux 的主要理由&#xff0c;涵盖不同场景的需求&#xff1a; --- 1. 开源与自由 &#x1f193; - 完全免费&#xff1a;无需支付系统或软件授权费用&#xff0c;节省成本。 - 开放…...