leetcode 886. 可能的二分法
给定一组 n 人(编号为 1, 2, …, n), 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人,那么他们不应该属于同一组。
给定整数 n 和数组 dislikes ,其中 dislikes[i] = [ai, bi] ,表示不允许将编号为 ai 和 bi的人归入同一组。当可以用这种方法将所有人分进两组时,返回 true;否则返回 false。
示例 1:
输入:n = 4, dislikes = [[1,2],[1,3],[2,4]]
输出:true
解释:group1 [1,4], group2 [2,3]
示例 2:
输入:n = 3, dislikes = [[1,2],[1,3],[2,3]]
输出:false
示例 3:
输入:n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
输出:false
提示:
1 <= n <= 2000
0 <= dislikes.length <= 104
dislikes[i].length == 2
1 <= dislikes[i][j] <= n
ai < bi
dislikes 中每一组都 不同
思路:用「染色法」来解决,第一组颜色标记为 1, 则相邻组的颜色标记为 2,遍历时,如果发现邻节点已经被染色,且和当前节点的颜色相同,说明是不能划分为两组的。
可采用 dfs 和 bfs 来做
import collections
class Solution:def dfs(self, color, f, index, co):color[index] = cofor x in f[index]:## 与3做异或,要么是 1,要么是2## 注意, 这儿不能直接写 return self.dfs(color, f, x, co^3)if color[x] == 0 and not self.dfs(color, f, x, co^3):return Falseelse: ## 和 当前进行比较,如果颜色相同, 直接返回 Falseif color[x] == co:return Falsereturn True## 转化成不能有环的问题,染色,两种颜色def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:if len(dislikes) == 0:return Truef = [[] for i in range(n+1)]color = [0]*(n+1)for i in range(0, len(dislikes)):x1, x2 = dislikes[i][0], dislikes[i][1]f[x1].append(x2)f[x2].append(x1)for i in range(1, n+1):if color[i] == 0:## 初始颜色设为 1, 设成 2 也 okif not self.dfs(color, f, i, 1):return Falsereturn True
bfs:
import collections
class Solution:## 转化成不能有环的问题def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:if len(dislikes) == 0:return True### 对已经遍历过&&并已加入 graph 的 index 做标记f = [[] for i in range(n+1)]vis = [0]*(n+1)for i in range(0, len(dislikes)):x1, x2 = dislikes[i][0], dislikes[i][1]f[x1].append(x2)f[x2].append(x1)for i in range(1, n+1):if vis[i] == 0:p = collections.deque()p.append((i, 1))while len(p) > 0:x1, color = p.popleft()vis[x1] = colornewColor = color^3for x in f[x1]:## 如果 x 没有被访问过if vis[x] == 0:p.append((x, newColor))else: ## 否则和当前的 colr 比较if color == vis[x]:return Falsereturn True
相关文章:
leetcode 886. 可能的二分法
给定一组 n 人(编号为 1, 2, …, n), 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人,那么他们不应该属于同一组。 给定整数 n 和数组 dislikes ,其中 dislikes[i] [ai, bi] ,表示不允许将…...
Elasticsearch:使用 ELSER 文本扩展进行语义搜索
在今天的文章里,我来详细地介绍如何使用 ELSER 进行文本扩展驱动的语义搜索。 安装 Elasticsearch 及 Kibana 如果你还没有安装好自己的 Elasticsearch 及 Kibana,请参考如下的链接来进行安装: 如何在 Linux,MacOS 及 Windows 上…...
OpenRadar DOA函数 Bartlett/CBF和Capon使用
Bartlett / CBF原理看这里 Capon原理看这里 这里只讲怎么调用openradar提供的aoa_bartlett和aoa_capon函数: 一些吐槽:虽然看起来openradar的作者代码水平很高,但里面有很多匪夷所思的写法,比如他demo里的解析文件格式就很迷啊等…...
二叉树--翻转二叉树
文章前言:如果有小白同学还是对于二叉树不太清楚,作者推荐:二叉树的初步认识_加瓦不加班的博客-CSDN博客 给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。 如果思路不清楚,请看动态页面&am…...
强化学习环境 - robogym - 学习 - 3
强化学习环境 - robogym - 学习 - 3 文章目录 强化学习环境 - robogym - 学习 - 3项目地址为什么选择 robogymObservation - 观测信息Action - 动作信息Initialization - 初始状态设置 项目地址 https://github.com/openai/robogym 为什么选择 robogym 自己的项目需要做一些机…...
CUDA+cuDNN+TensorRT 配置避坑指南
深度学习模型加速部署的环境配置,需要在本地安装NVIDIA的一些工具链和软件包,这是一个些许繁琐的过程,而且一步错,步步错。笔者将会根据自己的经验来提供建议,减少踩坑几率。当然可以完全按照官方教程操作,…...
关于PointHeadBox类的理解
forward函数 def forward(self, batch_dict):"""Args:batch_dict:batch_size:point_features: (N1 N2 N3 ..., C) or (B, N, C)point_features_before_fusion: (N1 N2 N3 ..., C)point_coords: (N1 N2 N3 ..., 4) [bs_idx, x, y, z]point_labels (opti…...
javascript二维数组(10)ajax的使用
在JQuery中,使用AJAX的方法主要有以下几种: $.ajax():这是JQuery中最通用的AJAX请求方法。它需要一个包含各种参数的对象,其中包括请求的URL、请求方式、数据类型、请求参数等。请求成功后执行的回调函数也是通过参数来定义的。 …...
CMMI5认证哪些企业可以申请
CMMI5认证哪些企业可以申请 什么是CMMI5认证 CMMI(Capability Maturity Model Integration)是一种用于评估组织的软件工程能力的国际标准。CMMI模型包括5个等级,其中CMMI5是最高等级,代表组织具有达到持续优化和创新的能力。获得…...
【iptables 实战】9 docker网络原理分析
在开始本章阅读之前,需要提前了解以下的知识 阅读本节需要一些docker的基础知识,最好是在linux上安装好docker环境。提前掌握iptables的基础知识,前文参考【iptables 实战】 一、docker网络模型 docker网络模型如下图所示 说明࿱…...
【多级缓存】
文章目录 1. JVM进程缓存2. Lua语法3. 实现多级缓存3.1 反向代理流程3.2 OpenResty快速入门 4. 查询Tomcat4.1 发送http请求的API4.2 封装http工具4.3 基于ID负载均衡4.4 流程小结 5. Redis缓存查询5.1 实现Redis查询 6. Nginx本地缓存6.1 本地缓存API6.2 实现本地缓存查询 7. …...
第五课 树与图
文章目录 第五课 树与图lc94.二叉树的中序遍历--简单题目描述代码展示 lc589.N叉树的层序遍历--中等题目描述代码展示 lc297.二叉树的序列化和反序列化--困难题目描述代码展示 lc105.从前序与中序遍历序列构造二叉树--中等题目描述代码展示 lc106.从中序与后序遍历序列构造二叉…...
2023-10-07 事业-代号z-副业-CQ私服-调研与分析
摘要: CQ作为一款运营了20年的游戏, 流传出的私服可以说是层出不穷, 到了现在我其实对这款游戏的长线运营的前景很悲观. 但是作为商业的一部分, 对其做谨慎的分析还是很有必要的. 传奇调研的来源: 一. 各种售卖私服的网站 传奇服务端版本库-传奇手游源码「免费下载」传奇GM论…...
合并不同门店数据-上下合并
项目背景:线下超市分店,统计产品的销售数量和销售额,并用透视表计算求和 merge()函数可以根据链接键横向连接两张不同表,concat()函数可以上下合并和左右合并2种不同的合并方式。merge()函数只能横向连接两张表,而con…...
学习记忆——数学篇——案例——算术——整除特点
理解记忆法 对于数的整除特征大家都比较熟悉:比如4看后两位(因为100是4的倍数),8看后三位(因为1000是8的倍数),5末尾是0或5,3与9看各位数字和等等,今天重点研究一下3,9,…...
PHP8中的魔术方法-PHP8知识详解
在PHP 8中,魔术方法是一种特殊的方法,它们以两个下划线(__)开头。魔术方法允许您定义类的行为,例如创建对象、调用其他方法或访问和修改类的属性。以下是一些常见的魔术方法: __construct(): 类的构造函数…...
[图论]哈尔滨工业大学(哈工大 HIT)学习笔记23-31
视频来源:4.1.1 背景_哔哩哔哩_bilibili 目录 1. 哈密顿图 1.1. 背景 1.2. 哈氏图 2. 邻接矩阵/邻接表 3. 关联矩阵 3.1. 定义 4. 带权图 1. 哈密顿图 1.1. 背景 (1)以地球为建模,从一个大城市开始遍历其他大城市并且返回…...
Nginx+Keepalived实现服务高可用
Nginx 和 Keepalived 是常用于构建高可用性(High Availability)架构的工具。Nginx 是一款高性能的Web服务器和反向代理服务器,而Keepalived则提供了对Nginx服务的健康状态监测和故障切换功能。 下载Nginx 在服务器1和服务器2分别下载nginx …...
picodet onnx转其它芯片支持格式时遇到
文章目录 报错信息解决方法两模型精度对比 报错信息 报错信息为: Upsample(resize) Resize_0 not support attribute coordinate_transformation_mode:half_pixel. 解决方法 整个模型转换过程是:paddle 动态模型转成静态,再用paddle2onnx…...
【学习笔记】CF704B Ant Man
智商不够啊,咋想到贪心的😅 非常经典的贪心模型🤔 首先,从小到大将每个 i i i插入到排列中,用 D P DP DP记录还有多少个位置可以插入,可以通过钦定新插入的位置左右两边是否继续插入数来提前计算贡献。注…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...
C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...
LabVIEW双光子成像系统技术
双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制,展现出显著的技术优势: 深层组织穿透能力:适用于活体组织深度成像 高分辨率观测性能:满足微观结构的精细研究需求 低光毒性特点:减少对样本的损伤…...
C语言中提供的第三方库之哈希表实现
一. 简介 前面一篇文章简单学习了C语言中第三方库(uthash库)提供对哈希表的操作,文章如下: C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...
