如何基于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-h

out:{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,邻接,植花
0
投稿

猜你喜欢

  • 网站浏览器兼容的底线

    2007-12-22 11:26:00
  • python 三种方法提取pdf中的图片

    2023-09-18 08:25:58
  • 关于VSCode 配置使用 PyLint 语法检查器的问题

    2023-06-18 17:10:33
  • CSDN 博客的代码高亮问题自己修复

    2022-07-28 11:33:25
  • python动态网站爬虫实战(requests+xpath+demjson+redis)

    2023-03-30 20:01:51
  • Python实现人脸识别并进行视频跟踪打码

    2022-08-04 22:57:25
  • vue.js移动端app之上拉加载以及下拉刷新实战

    2024-05-09 10:40:22
  • 解决Python 使用h5py加载文件,看不到keys()的问题

    2021-10-04 06:19:15
  • python如何使用contextvars模块源码分析

    2021-12-03 21:55:21
  • VScode查看python f.write()的文件乱码问题及解决方法

    2023-01-25 19:02:10
  • python thrift 实现 单端口多服务的过程

    2022-04-28 21:46:00
  • SQL行号排序和分页(SQL查询中插入行号 自定义分页的另类实现)

    2012-07-21 14:45:15
  • 不得不看的JS基础知识(事件触发篇)

    2008-12-04 16:38:00
  • 使用pandas 将DataFrame转化成dict

    2022-08-11 17:46:33
  • php中用socket模拟http中post或者get提交数据的示例代码

    2023-11-19 00:45:21
  • 解决vue请求接口第一次成功,第二次失败问题

    2023-07-02 16:59:59
  • 举例详解Python中smtplib模块处理电子邮件的使用

    2023-10-08 04:46:14
  • JavaScript内置对象math,global功能与用法实例分析

    2024-04-22 22:36:47
  • python中的lambda表达式用法详解

    2022-12-01 17:33:57
  • python 抓包保存为pcap文件并解析的实例

    2023-04-03 03:52:04
  • asp之家 网络编程 m.aspxhome.com