如何基于python实现不邻接植花
159 浏览量
2020-12-20
10:52:04
上传
评论
收藏 52KB PDF 举报
如何基于如何基于python实现不邻接植花实现不邻接植花
有 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-h
out:{1,2,3,4}
我的题解我的题解
题解1
class Solution:
# 整体思路采用BFS方法,还需考虑不连通图的问题,然后着手结果唯一
评论0
最新资源