【每日一题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)进程状态&…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
线程同步:确保多线程程序的安全与高效!
全文目录: 开篇语前序前言第一部分:线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分:synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分ÿ…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...
如何应对敏捷转型中的团队阻力
应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中,明确沟通敏捷转型目的尤为关键,团队成员只有清晰理解转型背后的原因和利益,才能降低对变化的…...
GraphQL 实战篇:Apollo Client 配置与缓存
GraphQL 实战篇:Apollo Client 配置与缓存 上一篇:GraphQL 入门篇:基础查询语法 依旧和上一篇的笔记一样,主实操,没啥过多的细节讲解,代码具体在: https://github.com/GoldenaArcher/graphql…...
