python实现不邻接植花的方法-创新互联
这篇文章主要讲解了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-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
标题名称:python实现不邻接植花的方法-创新互联
网页链接:http://myzitong.com/article/coieic.html