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记录还有多少个位置可以插入,可以通过钦定新插入的位置左右两边是否继续插入数来提前计算贡献。注…...
云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地
借阿里云中企出海大会的东风,以**「云启出海,智联未来|打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办,现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...
Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案
在大数据时代,海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构,在处理大规模数据抓取任务时展现出强大的能力。然而,随着业务规模的不断扩大和数据抓取需求的日益复杂,传统…...
OCR MLLM Evaluation
为什么需要评测体系?——背景与矛盾 能干的事: 看清楚发票、身份证上的字(准确率>90%),速度飞快(眨眼间完成)。干不了的事: 碰到复杂表格(合并单元…...
大模型——基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程
基于Docker+DeepSeek+Dify :搭建企业级本地私有化知识库超详细教程 下载安装Docker Docker官网:https://www.docker.com/ 自定义Docker安装路径 Docker默认安装在C盘,大小大概2.9G,做这行最忌讳的就是安装软件全装C盘,所以我调整了下安装路径。 新建安装目录:E:\MyS…...
Java中HashMap底层原理深度解析:从数据结构到红黑树优化
一、HashMap概述与核心特性 HashMap作为Java集合框架中最常用的数据结构之一,是基于哈希表的Map接口非同步实现。它允许使用null键和null值(但只能有一个null键),并且不保证映射顺序的恒久不变。与Hashtable相比,Hash…...
