如何基于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]forjinG[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
classSolution: #整体思路采用BFS方法,还需考虑不连通图的问题,然后着手结果唯一 defgardenNoAdj(self,N:int,paths:List[List[int]])->List[int]: #构建一个answer数组 answer=[0for_inrange(N)] #构建所有节点 all_nodes=[] [all_nodes.append(i)foriinrange(1,N+1)] #构建visted列表 visted=dict.fromkeys(all_nodes,0) #初始化nei字典元素为空列表 nei=[[]for_inrange(N)] #构建无向邻接表，无邻居则不构建 forpathinpaths: nei[path[0]-1].append(path[1]) nei[path[1]-1].append(path[0]) #遍历每一个点，每个点保证自己邻接点不是和自己相同就行 answer[0]=1 fornodeinrange(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 forsinodeinnei[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]) ifnotfix: continue else: flowers=[1,2,3,4] fora_valinlist(fix): flowers.remove(a_val) answer[node-1]=flowers[0] returnanswer
简化方法:利用集合快速搞定
classSolution:
defgardenNoAdj(self,N:int,paths:List[List[int]])->List[int]:
#构建一个answer数组
answer=[0]*N
#初始化nei字典元素为空列表
nei=[[]for_inrange(N)]
#构建无向邻接表，无邻居则不构建
forpathinpaths:
nei[path[0]-1].append(path[1])
nei[path[1]-1].append(path[0])
fornodeinrange(1,N+1):#遍历所有节点
flowers={1,2,3,4}
#临时存储邻居含有的花类型
a=set()
forsinodeinnei[node-1]:#遍历邻居
a.add(answer[sinode-1])
flowers=flowers-a
answer[node-1]=flowers.pop()
returnanswer
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。