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

【每日一题Day311】LC1761一个图中连通三元组的最小度数 | 枚举

一个图中连通三元组的最小度数【LC1761】

给你一个无向图,整数 n 表示图中节点的数目,edges 数组表示图中的边,其中 edges[i] = [ui, vi] ,表示 uivi 之间有一条无向边。

一个 连通三元组 指的是 三个 节点组成的集合且这三个点之间 两两 有边。

连通三元组的度数 是所有满足此条件的边的数目:一个顶点在这个三元组内,而另一个顶点不在这个三元组内。

请你返回所有连通三元组中度数的 最小值 ,如果图中没有连通三元组,那么返回 -1

来晚咯

  • 思路

    • 使用数组记录每个节点的度数,即相连的边数;
    • 并记录每条边至哈希表中,每条边假定小指向大
    • 暴力枚举每个三元组,判断是否两两相连,如果是那么该三元组为连通三元组,其度数为[每个点度数之和-6],判断能否更新结果
    • 枚举过程中,可以进行剪枝优化
      • 每个点的度数一定大于2
      • res为0时,可以直接返回结果
  • 实现

    class Solution {public int minTrioDegree(int n, int[][] edges) {Set<Integer> set = new HashSet<>();int[] deg = new int[n];for (int[] edge : edges){int u = edge[0] - 1, v = edge[1] - 1;if (u > v){int tmp = u;u = v;v = tmp;}set.add(u * n + v);deg[u]++;deg[v]++;}int res = Integer.MAX_VALUE;for (int i = 0; i < n; i++){if (deg[i] < 2) continue;for (int j = i + 1; j < n; j++){if (!set.contains(i * n + j) || deg[j] < 2) continue;for (int k = j + 1; k < n; k++){if (deg[k] < 2) continue;                  if (set.contains(i * n + k) && set.contains(j * n + k)){res = Math.min(res, deg[i] + deg[j] + deg[k] - 6);if (res == 0) return 0;}}}}return res == Integer.MAX_VALUE ? -1 : res;}
    }
    
    • 复杂度

      • 时间复杂度: O ( n 3 ) \mathcal{O}(n^3) O(n3),n为点的个数

      • 空间复杂度: O ( m ) \mathcal{O}(m) O(m),m为edges的长度

相关文章:

【每日一题Day311】LC1761一个图中连通三元组的最小度数 | 枚举

一个图中连通三元组的最小度数【LC1761】 给你一个无向图&#xff0c;整数 n 表示图中节点的数目&#xff0c;edges 数组表示图中的边&#xff0c;其中 edges[i] [ui, vi] &#xff0c;表示 ui 和 vi 之间有一条无向边。 一个 连通三元组 指的是 三个 节点组成的集合且这三个点…...

前端日期减一天的笑话

vue日期减一天 给大家讲一个真实的笑话。最近做的一个项目&#xff0c;要统计不同年月日期的关联交易数量&#xff0c;由于和银行内数据对接取得数据都是T-1的&#xff0c;所以在首页根据日期统计一些交易数据量时默认是统计昨日的数据量。所以当时和前端约定好的让前端的妹子做…...

高效能,一键批量剪辑,AI智剪让创作更轻松

在今天的数字化时代&#xff0c;视频制作已经成为各种行业和领域的必备技能。然而&#xff0c;视频剪辑过程往往繁琐且耗时&#xff0c;大大降低了我们的工作效率。幸运的是&#xff0c;随着人工智能技术的发展&#xff0c;我们有了新的解决方案——AI智剪软件。 AI智剪软件&am…...

手写Mybatis:第15章-返回Insert操作自增索引值

文章目录 一、目标&#xff1a;Insert自增索引值二、设计&#xff1a;Insert自增索引值三、实现&#xff1a;Insert自增索引值3.1 工程结构3.2 Insert自增索引值类图3.3 修改执行器3.3.1 修改执行器接口3.3.2 抽象执行器基类 3.4 键值生成器3.4.1 键值生成器接口3.4.2 不用键值…...

【数据结构】动态数组(vector)的基本操作,包括插入、删除、扩容、输出、释放内存等。以下是代码的解释和注释:

这段C代码实现了一个动态数组&#xff08;vector&#xff09;的基本操作&#xff0c;包括插入、删除、扩容、输出、释放内存等。以下是代码的解释和注释&#xff1a; // 引入标准输入输出库和标准库函数&#xff0c;用于后续的内存分配和打印输出等操作 #include <stdio.…...

[unity]三角形顶点顺序

序 详见官方文档&#xff1a;Unity - Manual: Mesh data (unity3d.com) Topology&#xff1a;拓扑结构 翻译&#xff1a; 拓扑描述网格具有的面类型。 网格的拓扑定义了索引缓冲区的结构&#xff0c;索引缓冲区又描述了顶点位置如何组合成面。每种类型的拓扑都使用索引数组中…...

【python爬虫】14.Scrapy框架讲解

文章目录 前言Scrapy是什么Scrapy的结构Scrapy的工作原理 Scrapy的用法明确目标与分析过程代码实现——创建项目代码实现——编辑爬虫代码实现——定义数据代码实操——设置代码实操——运行 复习 前言 前两关&#xff0c;我们学习了能提升爬虫速度的进阶知识——协程&#xf…...

功率放大器主要作用是什么呢

功率放大器是一种电子设备&#xff0c;主要作用是将输入信号的功率增加到更高的水平&#xff0c;以便能够驱动高功率负载。在许多应用中&#xff0c;信号源产生的信号往往具有较低的功率&#xff0c;无法直接满足一些要求较高的设备或系统的需求。而功率放大器则可以增强信号的…...

SpringBoot ApplicationEvent详解

ApplicationStartingEvent 阶段 LoggingApplicationListener#onApplicationStartingEvent 初始化日志工厂,LoggingSystemFactory接口&#xff0c;可以通过spring.factories进行定制 可以通过System.setProperty("org.springframework.boot.logging.LoggingSystem",&q…...

WebSocket 报java.io.IOException: 远程主机强迫关闭了一个现有的连接。

在客户端强制关闭时&#xff0c;或者窗口强制关闭时&#xff0c;后端session没有关闭。 有时还会报&#xff1a;java.io.EOFException: 这个异常 前端心跳没有收到信息&#xff0c;还在心跳。 CloseReason close new CloseReason(CloseReason.CloseCodes.NORMAL_CLOSURE, &…...

关于git约定式提交IDEA

背景 因为git提交的消息不规范导致被乱喷&#xff0c;所以领导统一规定了约定式提交 官话 约定式提交官网地址 约定式提交规范是一种基于提交信息的轻量级约定。 它提供了一组简单规则来创建清晰的提交历史&#xff1b; 这更有利于编写自动化工具。 通过在提交信息中描述功能…...

【计算机网络】http协议

目录 前言 认识URL URLEncode和URLDecode http协议格式 http方法 GET POST GET与POST的区别 http状态码 http常见header 简易的http服务器 前言 我们在序列化和反序列化这一章中&#xff0c;实现了一个网络版的计算器。这个里面设计到了对协议的分析与处…...

仓库太大,clone 后,git pull 老分支成功,最新分支失败

由于 git 仓库太大&#xff0c;新加入的小伙伴在拉取时&#xff0c;无法切换到最新的分支&#xff0c;报错如下&#xff1a; fetch-pack: unexpected disconnect while reading sideband packet fatal: early EOF fatal: fetch-pack: invalid index-pack output在此记录解决步…...

javafx Dialog无法关闭

// 生成二维码图片String qrCodeText "https://example.com";DialogPane grid new DialogPane();grid.setPadding(new Insets(5));VBox vBox new VBox();vBox.setAlignment(Pos.CENTER);Image qrCodeImage generateQRCodeImage(qrCodeText);ImageView customImag…...

vue3中TCplayer应用

环境win10:vitevue3elementUI 1 安装 npm install tcplayer.js2 使用 <template><div><video id"player-container-id" width"414" height"270" preload"auto" playsinline webkit-playsinline></video>&l…...

算法通关村14关 | 数据流中位数问题

1. 数据流中位数问题 题目 LeetCode295: 中位数是有序列表中间的数&#xff0c;如果列表长度是偶数&#xff0c;中位数是中间两个数的平均值&#xff0c; 例如:[2,3,4]的中位数是3&#xff0c; [2,3]中位数是&#xff08;23&#xff09;/ 2 2.5 设计一个数据结构&#xff1a; …...

工厂模式 与 抽象工厂模式 的区别

工厂模式&#xff1a; // 抽象产品接口 interface Product {void showInfo(); }// 具体产品A class ConcreteProductA implements Product {Overridepublic void showInfo() {System.out.println("This is Product A");} }// 具体产品B class ConcreteProductB impl…...

安装虚拟机+安装/删除镜像

安装虚拟机 注意&#xff0c;官网可能无法登录&#xff0c;导致无法从官网下载&#xff0c;就自己去网上搜靠谱的下载&#xff0c;我用的16.2.3 删除镜像 Vm虚拟机怎么删除已经创建的系统&#xff1f;Vm虚拟机创建好之后iso删除方法 - 系统之家 (xitongzhijia.net) 安装镜像…...

MySQL的内置函数复合查询内外连接

文章目录 内置函数时间函数字符串函数数学函数其他函数 复合查询多表笛卡尔积自连接在where中使用子查询多列子查询在from中使用子查询 内连接外连接左外连接右外连接 内置函数 时间函数 函数描述current_date()当前日期current_time()当前时间current_timestamp()当前时间戳…...

操作系统(OS)与系统进程

操作系统&#xff08;OS&#xff09;与系统进程 冯诺依曼体系结构操作系统(Operator System)进程基本概念进程的描述&#xff08;PCB&#xff09;查看进程通过系统调用获取进程标示符&#xff08;PID&#xff09;通过系统调用创建进程&#xff08;fork&#xff09;进程状态&…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面

代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口&#xff08;适配服务端返回 Token&#xff09; export const login async (code, avatar) > {const res await http…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

JDK 17 新特性

#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持&#xff0c;不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的&#xff…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

MySQL 8.0 事务全面讲解

以下是一个结合两次回答的 MySQL 8.0 事务全面讲解&#xff0c;涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容&#xff0c;并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念&#xff08;ACID&#xff09; 事务是…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...