电脑知识|欧美黑人一区二区三区|软件|欧美黑人一级爽快片淫片高清|系统|欧美黑人狂野猛交老妇|数据库|服务器|编程开发|网络运营|知识问答|技术教程文章 - 好吧啦网

您的位置:首頁技術文章
文章詳情頁

如何基于python實現不鄰接植花

瀏覽:2日期:2022-07-26 17:08:29

有 N 個花園,按從 1 到 N 標記。在每個花園中,你打算種下四種花之一。

paths[i] = [x, y] 描述了花園 x 到花園 y 的雙向路徑。

另外,沒有花園有 3 條以上的路徑可以進入或者離開。

你需要為每個花園選擇一種花,使得通過路徑相連的任何兩個花園中的花的種類互不相同。

以數組形式返回選擇的方案作為答案 answer,其中 answer[i] 為在第 (i+1) 個花園中種植的花的種類?;ǖ姆N類用 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 <= 100000 <= 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] = 1flowers=[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

以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持好吧啦網。

標簽: Python 編程
相關文章:
主站蜘蛛池模板: 上海盐水喷雾试验机_两厢式冷热冲击试验箱-巨怡环试 | 航拍_专业的无人机航拍摄影门户社区网站_航拍网 | 隐形纱窗|防护纱窗|金刚网防盗纱窗|韦柏纱窗|上海青木装潢制品有限公司|纱窗国标起草单位 | 留学生辅导网-在线课程论文辅导-留学生挂科申诉机构 | 恒温水槽与水浴锅-上海熙浩实业有限公司| 临沂招聘网_人才市场_招聘信息_求职招聘找工作请认准【马头商标】 | 焊管生产线_焊管机组_轧辊模具_焊管设备_焊管设备厂家_石家庄翔昱机械 | elisa试剂盒价格-酶联免疫试剂盒-猪elisa试剂盒-上海恒远生物科技有限公司 | 回转支承-转盘轴承-回转驱动生产厂家-洛阳隆达轴承有限公司 | 合肥防火门窗/隔断_合肥防火卷帘门厂家_安徽耐火窗_良万消防设备有限公司 | 底部填充胶_电子封装胶_芯片封装胶_芯片底部填充胶厂家-东莞汉思新材料 | 多功能干燥机,过滤洗涤干燥三合一设备-无锡市张华医药设备有限公司 | 上海质量认证办理中心 | 航拍_专业的无人机航拍摄影门户社区网站_航拍网 | 陶瓷加热器,履带式加热器-吴江市兴达电热设备厂 | 生物风-销售载体,基因,质粒,ATCC细胞,ATCC菌株等,欢迎购买-百风生物 | VOC检测仪-甲醛检测仪-气体报警器-气体检测仪厂家-深恒安科技有限公司 | 半自动预灌装机,卡式瓶灌装机,注射器灌装机,给药器灌装机,大输液灌装机,西林瓶灌装机-长沙一星制药机械有限公司 | 合肥废气治理设备_安徽除尘设备_工业废气处理设备厂家-盈凯环保 合肥防火门窗/隔断_合肥防火卷帘门厂家_安徽耐火窗_良万消防设备有限公司 | 好物生环保网、环保论坛 - 环保人的学习交流平台 | 集菌仪厂家_全封闭_封闭式_智能智能集菌仪厂家-上海郓曹 | 气动隔膜阀_气动隔膜阀厂家_卫生级隔膜阀价格_浙江浙控阀门有限公司 | 泵阀展|阀门展|水泵展|流体机械展 -2025上海国际泵管阀展览会flowtech china | 三氯异氰尿酸-二氯-三氯-二氯异氰尿酸钠-优氯净-强氯精-消毒片-济南中北_优氯净厂家 | 杭州翻译公司_驾照翻译_专业人工翻译-杭州以琳翻译有限公司官网 组织研磨机-高通量组织研磨仪-实验室多样品组织研磨机-东方天净 | HDPE土工膜,复合土工膜,防渗膜价格,土工膜厂家-山东新路通工程材料有限公司 | 珠海白蚁防治_珠海灭鼠_珠海杀虫灭鼠_珠海灭蟑螂_珠海酒店消杀_珠海工厂杀虫灭鼠_立净虫控防治服务有限公司 | 超声骨密度仪,双能X射线骨密度仪【起草单位】,骨密度检测仪厂家 - 品源医疗(江苏)有限公司 | 杭州荣奥家具有限公司-浙江办公家具,杭州办公家具厂 | 谈股票-今日股票行情走势分析-牛股推荐排行榜| 双齿辊破碎机-大型狼牙破碎机视频-对辊破碎机价格/型号图片-金联机械设备生产厂家 | FAG轴承,苏州FAG轴承,德国FAG轴承-恩梯必传动设备(苏州)有限公司 | 扒渣机,铁水扒渣机,钢水扒渣机,铁水捞渣机,钢水捞渣机-烟台盛利达工程技术有限公司 | HV全空气系统_杭州暖通公司—杭州斯培尔冷暖设备有限公司 | 电磁铁_推拉电磁铁_机械手电磁吸盘电磁铁厂家-广州思德隆电子公司 | 盘古网络技术有限公司| 高精度电阻回路测试仪-回路直流电阻测试仪-武汉特高压电力科技有限公司 | 浙江红酒库-冰雕库-气调库-茶叶库安装-医药疫苗冷库-食品物流恒温恒湿车间-杭州领顺实业有限公司 | 专业甜品培训学校_广东糖水培训_奶茶培训_特色小吃培训_广州烘趣甜品培训机构 | SPC工作站-连杆综合检具-表盘气动量仪-内孔缺陷检测仪-杭州朗多检测仪器有限公司 | 欧必特空气能-商用空气能热水工程,空气能热水器,超低温空气源热泵生产厂家-湖南欧必特空气能公司 |