如何基于python实现不邻接植花
作者:云上男孩 发布时间:2023-10-14 16:35:45
有 N 个花园,按从 1 到 N 标记。在每个花园中,你打算种下四种花之一。
paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径。
另外,没有花园有 3 条以上的路径可以进入或者离开。
你需要为每个花园选择一种花,使得通过路径相连的任何两个花园中的花的种类互不相同。
以数组形式返回选择的方案作为答案 answer,其中 answer[i] 为在第 (i+1) 个花园中种植的花的种类。花的种类用 1, 2, 3, 4 表示。保证存在答案。
示例 1:
输入:N = 3, paths = [[1,2],[2,3],[3,1]]
输出:[1,2,3]
示例 2:
输入:N = 4, paths = [[1,2],[3,4]]
输出:[1,2,1,2]
示例 3:
输入:N = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
输出:[1,2,3,4]
提示:
1 <= N <= 10000
0 <= paths.size <= 20000
不存在花园有 4 条或者更多路径可以进入或离开。
保证存在答案。
知识准备
在python中可以使用列表作为队列,list用append添加元素
可以用字典来存储邻接节点nei = {}
在集合中使用for循环
{res[j] for j in G[i]}
集合的pop函数
flowers = {1,2,3,4} #集合直接相减即可
flowers.pop()
# 集合不能获取某个元素这样子的操作
print(flowers)out: {2,3,4}集合中的pop是从左边开始取
集合的相减
flowers = {1,2,3,4}
h = {0}
flowers-hout:{1,2,3,4}
我的题解
题解1
class Solution:
# 整体思路采用BFS方法,还需考虑不连通图的问题,然后着手结果唯一
def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
#构建一个answer数组
answer = [0 for _ in range(N)]
#构建所有节点
all_nodes = []
[all_nodes.append(i) for i in range(1,N+1)]
#构建visted列表
visted = dict.fromkeys(all_nodes, 0)
#初始化nei字典元素为空列表
nei = [[] for _ in range(N)]
# 构建无向邻接表,无邻居则不构建
for path in paths:
nei[path[0]-1].append(path[1])
nei[path[1]-1].append(path[0])
#遍历每一个点,每个点保证自己邻接点不是和自己相同就行
answer[0] = 1
for node in range(1,N+1): #遍历所有节点
visted[node] = 1
fix = set()
if(answer[node-1]==0): #如果为0,说明不是连通图
answer[node-1] = 1
flowers=[1,2,3,4]
nei[node-1] = sorted(nei[node-1]) #排序邻居节点
flowers.pop(answer[node-1]-1) #弹出父节点的flowers
for sinode in nei[node-1]: #遍历邻居
if(visted[sinode] == 0): #如果邻居未被访问过
answer[sinode-1] = flowers[0] #使用1,弹出1
flowers.pop(0)
else: #如果邻居被访问过
if(answer[sinode-1]==answer[node-1]):
answer[node-1] = flowers[0]
flowers.pop(0)
fix.add(answer[sinode-1])
if not fix:
continue
else:
flowers=[1,2,3,4]
for a_val in list(fix):
flowers.remove(a_val)
answer[node-1] = flowers[0]
return answer
简化方法:利用集合快速搞定
class Solution:
def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
#构建一个answer数组
answer = [0]*N
#初始化nei字典元素为空列表
nei = [[] for _ in range(N)]
# 构建无向邻接表,无邻居则不构建
for path in paths:
nei[path[0]-1].append(path[1])
nei[path[1]-1].append(path[0])
for node in range(1,N+1): #遍历所有节点
flowers={1,2,3,4}
#临时存储邻居含有的花类型
a = set()
for sinode in nei[node-1]: #遍历邻居
a.add(answer[sinode-1])
flowers = flowers - a
answer[node-1] = flowers.pop()
return answer
来源:https://www.cnblogs.com/cloudboy/p/12806509.html
猜你喜欢
- python:simplified-chinese-menu:中文汉化(英文差的)代码高亮:Atom自带自动补全:autocomplete-
- 创建 NumPy ndarray 对象NumPy 用于处理数组,NumPy 中的数组对象称为 ndarray。我们可以使用 array()
- #coding=utf8__author__ = 'Administrator'# 当函数的参数不确定时,可以使用*args
- php的命名空间功能已经出来很久了,但是一直以来没怎么深究过,这次赶着有时间所以特意翻着手册做一个整理和总结帮助自己完善完善,原本准备一篇写
- 本篇文章主要介绍Java操作MongoDB。开发环境:System:WindowsIDE:eclipse、MyEclipse 8Databa
- 今天因为做一个效果的时候需要CSS的定位来实现,于是我就根据自己原来对CSS的了解,用absolute和relative摆弄了好一阵子,总是
- 一、什么是执行计划(explain plan) 执行计划:一条查询语句在ORACLE中的执行过程或访问路径的描述。 二、如何查看执行计划 1
- 前言回调函数是我们在python编程中经常会遇到的一个问题,而想在将来某一时刻进行函数回调,可以使用call_later()函数来实现,第一
- 数据分析师肯定每天都被各种各样的数据数据报表搞得焦头烂额,老板的,运营的、产品的等等。而且大部分报表都是重复性的工作,这篇文章就是帮助大家如
- 本文实例讲述了Python实现调用另一个路径下py文件中的函数方法。分享给大家供大家参考,具体如下:针对这个问题,网上有很多的解决方式。其实
- 这篇文章主要介绍了Python列表切片常用操作实例解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋
- TihuanWords.txt文档格式注意:同一行的词用单个空格隔开,每行第一个词为同行词的替换词。年休假 年假 年休究竟 到底回家场景 我
- oracle 的表空间实例详解查询表空间SELECT UPPER(F.TABLESPACE_NAME) "表空间名",
- API的设计是一个艺术活。往往需要其简单、易懂、整洁、不累赘。很多时候,我们在底层封装一个方法给高层用,而其它的方法只是为了辅助这个方法的。
- ORACLE EBS操作某一个FORM界面,或者后台数据库操作某一个表时发现一直出于"假死"状态,可能是该表被某一用户锁
- 本文实例讲述了wxPython框架类和面板类的使用方法,分享给大家供大家参考。具体分析如下:实现代码如下:import wx c
- Python下实现定时任务的方式有很多种方式。下面介绍几种循环sleep:这是一种最简单的方式,在循环里放入要执行的任务,然后sleep一段
- 一、打开摄像头import cv2import numpy as npdef video_demo(): capture = c
- 用VBS语言实现的一个简单网页计算器,功能:可以进行加法、减法、乘法、除法、取反、开根号、及指数运算。虽然简单但是比起windows xp自
- 本文实例讲述了python清除指定目录内所有文件中script的方法。分享给大家供大家参考。具体如下:将脚本存储为stripscripts.