【每日一题Day311】LC1761一个图中连通三元组的最小度数 | 枚举
一个图中连通三元组的最小度数【LC1761】
给你一个无向图,整数
n表示图中节点的数目,edges数组表示图中的边,其中edges[i] = [ui, vi],表示ui和vi之间有一条无向边。一个 连通三元组 指的是 三个 节点组成的集合且这三个点之间 两两 有边。
连通三元组的度数 是所有满足此条件的边的数目:一个顶点在这个三元组内,而另一个顶点不在这个三元组内。
请你返回所有连通三元组中度数的 最小值 ,如果图中没有连通三元组,那么返回
-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】 给你一个无向图,整数 n 表示图中节点的数目,edges 数组表示图中的边,其中 edges[i] [ui, vi] ,表示 ui 和 vi 之间有一条无向边。 一个 连通三元组 指的是 三个 节点组成的集合且这三个点…...
前端日期减一天的笑话
vue日期减一天 给大家讲一个真实的笑话。最近做的一个项目,要统计不同年月日期的关联交易数量,由于和银行内数据对接取得数据都是T-1的,所以在首页根据日期统计一些交易数据量时默认是统计昨日的数据量。所以当时和前端约定好的让前端的妹子做…...
高效能,一键批量剪辑,AI智剪让创作更轻松
在今天的数字化时代,视频制作已经成为各种行业和领域的必备技能。然而,视频剪辑过程往往繁琐且耗时,大大降低了我们的工作效率。幸运的是,随着人工智能技术的发展,我们有了新的解决方案——AI智剪软件。 AI智剪软件&am…...
手写Mybatis:第15章-返回Insert操作自增索引值
文章目录 一、目标:Insert自增索引值二、设计:Insert自增索引值三、实现:Insert自增索引值3.1 工程结构3.2 Insert自增索引值类图3.3 修改执行器3.3.1 修改执行器接口3.3.2 抽象执行器基类 3.4 键值生成器3.4.1 键值生成器接口3.4.2 不用键值…...
【数据结构】动态数组(vector)的基本操作,包括插入、删除、扩容、输出、释放内存等。以下是代码的解释和注释:
这段C代码实现了一个动态数组(vector)的基本操作,包括插入、删除、扩容、输出、释放内存等。以下是代码的解释和注释: // 引入标准输入输出库和标准库函数,用于后续的内存分配和打印输出等操作 #include <stdio.…...
[unity]三角形顶点顺序
序 详见官方文档:Unity - Manual: Mesh data (unity3d.com) Topology:拓扑结构 翻译: 拓扑描述网格具有的面类型。 网格的拓扑定义了索引缓冲区的结构,索引缓冲区又描述了顶点位置如何组合成面。每种类型的拓扑都使用索引数组中…...
【python爬虫】14.Scrapy框架讲解
文章目录 前言Scrapy是什么Scrapy的结构Scrapy的工作原理 Scrapy的用法明确目标与分析过程代码实现——创建项目代码实现——编辑爬虫代码实现——定义数据代码实操——设置代码实操——运行 复习 前言 前两关,我们学习了能提升爬虫速度的进阶知识——协程…...
功率放大器主要作用是什么呢
功率放大器是一种电子设备,主要作用是将输入信号的功率增加到更高的水平,以便能够驱动高功率负载。在许多应用中,信号源产生的信号往往具有较低的功率,无法直接满足一些要求较高的设备或系统的需求。而功率放大器则可以增强信号的…...
SpringBoot ApplicationEvent详解
ApplicationStartingEvent 阶段 LoggingApplicationListener#onApplicationStartingEvent 初始化日志工厂,LoggingSystemFactory接口,可以通过spring.factories进行定制 可以通过System.setProperty("org.springframework.boot.logging.LoggingSystem",&q…...
WebSocket 报java.io.IOException: 远程主机强迫关闭了一个现有的连接。
在客户端强制关闭时,或者窗口强制关闭时,后端session没有关闭。 有时还会报:java.io.EOFException: 这个异常 前端心跳没有收到信息,还在心跳。 CloseReason close new CloseReason(CloseReason.CloseCodes.NORMAL_CLOSURE, &…...
关于git约定式提交IDEA
背景 因为git提交的消息不规范导致被乱喷,所以领导统一规定了约定式提交 官话 约定式提交官网地址 约定式提交规范是一种基于提交信息的轻量级约定。 它提供了一组简单规则来创建清晰的提交历史; 这更有利于编写自动化工具。 通过在提交信息中描述功能…...
【计算机网络】http协议
目录 前言 认识URL URLEncode和URLDecode http协议格式 http方法 GET POST GET与POST的区别 http状态码 http常见header 简易的http服务器 前言 我们在序列化和反序列化这一章中,实现了一个网络版的计算器。这个里面设计到了对协议的分析与处…...
仓库太大,clone 后,git pull 老分支成功,最新分支失败
由于 git 仓库太大,新加入的小伙伴在拉取时,无法切换到最新的分支,报错如下: 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: 中位数是有序列表中间的数,如果列表长度是偶数,中位数是中间两个数的平均值, 例如:[2,3,4]的中位数是3, [2,3]中位数是(23)/ 2 2.5 设计一个数据结构: …...
工厂模式 与 抽象工厂模式 的区别
工厂模式: // 抽象产品接口 interface Product {void showInfo(); }// 具体产品A class ConcreteProductA implements Product {Overridepublic void showInfo() {System.out.println("This is Product A");} }// 具体产品B class ConcreteProductB impl…...
安装虚拟机+安装/删除镜像
安装虚拟机 注意,官网可能无法登录,导致无法从官网下载,就自己去网上搜靠谱的下载,我用的16.2.3 删除镜像 Vm虚拟机怎么删除已经创建的系统?Vm虚拟机创建好之后iso删除方法 - 系统之家 (xitongzhijia.net) 安装镜像…...
MySQL的内置函数复合查询内外连接
文章目录 内置函数时间函数字符串函数数学函数其他函数 复合查询多表笛卡尔积自连接在where中使用子查询多列子查询在from中使用子查询 内连接外连接左外连接右外连接 内置函数 时间函数 函数描述current_date()当前日期current_time()当前时间current_timestamp()当前时间戳…...
操作系统(OS)与系统进程
操作系统(OS)与系统进程 冯诺依曼体系结构操作系统(Operator System)进程基本概念进程的描述(PCB)查看进程通过系统调用获取进程标示符(PID)通过系统调用创建进程(fork)进程状态&…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
Web中间件--tomcat学习
Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机,它可以执行Java字节码。Java虚拟机是Java平台的一部分,Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...
如何通过git命令查看项目连接的仓库地址?
要通过 Git 命令查看项目连接的仓库地址,您可以使用以下几种方法: 1. 查看所有远程仓库地址 使用 git remote -v 命令,它会显示项目中配置的所有远程仓库及其对应的 URL: git remote -v输出示例: origin https://…...
【阅读笔记】MemOS: 大语言模型内存增强生成操作系统
核心速览 研究背景 研究问题:这篇文章要解决的问题是当前大型语言模型(LLMs)在处理内存方面的局限性。LLMs虽然在语言感知和生成方面表现出色,但缺乏统一的、结构化的内存架构。现有的方法如检索增强生成(RA…...
五、jmeter脚本参数化
目录 1、脚本参数化 1.1 用户定义的变量 1.1.1 添加及引用方式 1.1.2 测试得出用户定义变量的特点 1.2 用户参数 1.2.1 概念 1.2.2 位置不同效果不同 1.2.3、用户参数的勾选框 - 每次迭代更新一次 总结用户定义的变量、用户参数 1.3 csv数据文件参数化 1、脚本参数化 …...
RabbitMQ work模型
Work 模型是 RabbitMQ 最基础的消息处理模式,核心思想是 多个消费者竞争消费同一个队列中的消息,适用于任务分发和负载均衡场景。同一个消息只会被一个消费者处理。 当一个消息队列绑定了多个消费者,每个消息消费的个数都是平摊的&a…...
SQL 注入开放与修复
开发: SQL 注入是一种数据库攻击手段。攻击者通过向应用程序提交恶意代码来改变原 SQL 语句的含义, 进而执行任意 SQL 命令,达到入侵数据库乃至操作系统的目的。 例如:下面代码片段中,动态构造并执行了一个 SQ…...
多层PCB技术解析:从材料选型到制造工艺的深度实践
在电子设备集成度与信号传输要求不断提升的背景下,多层PCB凭借分层布局优势,成为高速通信、汽车电子、工业控制等领域的核心载体。其通过导电层、绝缘层的交替堆叠,实现复杂电路的立体化设计,显著提升空间利用率与信号完整性。 一…...
