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

您的位置:首頁(yè)技術(shù)文章
文章詳情頁(yè)

如何基于python實(shí)現(xiàn)不鄰接植花

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

有 N 個(gè)花園,按從 1 到 N 標(biāo)記。在每個(gè)花園中,你打算種下四種花之一。

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

另外,沒(méi)有花園有 3 條以上的路徑可以進(jìn)入或者離開(kāi)。

你需要為每個(gè)花園選擇一種花,使得通過(guò)路徑相連的任何兩個(gè)花園中的花的種類(lèi)互不相同。

以數(shù)組形式返回選擇的方案作為答案 answer,其中 answer[i] 為在第 (i+1) 個(gè)花園中種植的花的種類(lèi)。花的種類(lèi)用 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 條或者更多路徑可以進(jìn)入或離開(kāi)。保證存在答案。

知識(shí)準(zhǔn)備

在python中可以使用列表作為隊(duì)列,list用append添加元素

可以用字典來(lái)存儲(chǔ)鄰接節(jié)點(diǎn)nei = {}

在集合中使用for循環(huán)

{res[j] for j in G[i]}

集合的pop函數(shù)

flowers = {1,2,3,4} #集合直接相減即可flowers.pop()# 集合不能獲取某個(gè)元素這樣子的操作print(flowers)

out: {2,3,4}集合中的pop是從左邊開(kāi)始取

集合的相減

flowers = {1,2,3,4}h = {0}flowers-h

out:{1,2,3,4}

我的題解

題解1

class Solution: # 整體思路采用BFS方法,還需考慮不連通圖的問(wèn)題,然后著手結(jié)果唯一 def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]: #構(gòu)建一個(gè)answer數(shù)組 answer = [0 for _ in range(N)] #構(gòu)建所有節(jié)點(diǎn) all_nodes = [] [all_nodes.append(i) for i in range(1,N+1)] #構(gòu)建visted列表 visted = dict.fromkeys(all_nodes, 0) #初始化nei字典元素為空列表 nei = [[] for _ in range(N)] # 構(gòu)建無(wú)向鄰接表,無(wú)鄰居則不構(gòu)建 for path in paths: nei[path[0]-1].append(path[1]) nei[path[1]-1].append(path[0]) #遍歷每一個(gè)點(diǎn),每個(gè)點(diǎn)保證自己鄰接點(diǎn)不是和自己相同就行 answer[0] = 1 for node in range(1,N+1): #遍歷所有節(jié)點(diǎn) visted[node] = 1 fix = set() if(answer[node-1]==0): #如果為0,說(shuō)明不是連通圖 answer[node-1] = 1flowers=[1,2,3,4] nei[node-1] = sorted(nei[node-1]) #排序鄰居節(jié)點(diǎn) flowers.pop(answer[node-1]-1) #彈出父節(jié)點(diǎn)的flowers for sinode in nei[node-1]: #遍歷鄰居 if(visted[sinode] == 0): #如果鄰居未被訪問(wèn)過(guò) answer[sinode-1] = flowers[0] #使用1,彈出1 flowers.pop(0) else: #如果鄰居被訪問(wèn)過(guò) 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

簡(jiǎn)化方法:利用集合快速搞定

class Solution: def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]: #構(gòu)建一個(gè)answer數(shù)組 answer = [0]*N #初始化nei字典元素為空列表 nei = [[] for _ in range(N)] # 構(gòu)建無(wú)向鄰接表,無(wú)鄰居則不構(gòu)建 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): #遍歷所有節(jié)點(diǎn) flowers={1,2,3,4} #臨時(shí)存儲(chǔ)鄰居含有的花類(lèi)型 a = set() for sinode in nei[node-1]: #遍歷鄰居a.add(answer[sinode-1]) flowers = flowers - a answer[node-1] = flowers.pop() return answer

以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持好吧啦網(wǎng)。

標(biāo)簽: Python 編程
相關(guān)文章:
主站蜘蛛池模板: 光谱仪_积分球_分布光度计_灯具检测生产厂家_杭州松朗光电【官网】 | 番茄畅听邀请码怎么输入 - Dianw8.com| 煤机配件厂家_刮板机配件_链轮轴组_河南双志机械设备有限公司 | 无尘烘箱_洁净烤箱_真空无氧烤箱_半导体烤箱_电子防潮柜-深圳市怡和兴机电 | 接地电阻测试仪[厂家直销]_电缆故障测试仪[精准定位]_耐压测试仪-武汉南电至诚电力设备 | 工业PH计|工业ph酸度计|在线PH计价格-合肥卓尔仪器仪表有限公司 济南画室培训-美术高考培训-山东艺霖艺术培训画室 | 深圳装修_店面装修设计_餐厅设计_装修全包价格-尚泰装饰设计 | 烟台螺纹,烟台H型钢,烟台钢材,烟台角钢-烟台市正丰金属材料有限公司 | 盘煤仪,盘料仪,盘点仪,堆料测量仪,便携式激光盘煤仪-中科航宇(北京)自动化工程技术有限公司 | 聚氨酯催化剂K15,延迟催化剂SA-1,叔胺延迟催化剂,DBU,二甲基哌嗪,催化剂TMR-2,-聚氨酯催化剂生产厂家 | 光纤测温-荧光光纤测温系统-福州华光天锐光电科技有限公司 | 成都竞价托管_抖音代运营_网站建设_成都SEM外包-成都智网创联网络科技有限公司 | 玻纤土工格栅_钢塑格栅_PP焊接_单双向塑料土工格栅_复合防裂布厂家_山东大庚工程材料科技有限公司 | 空气净化器租赁,空气净化器出租,全国直租_奥司汀净化器租赁 | 工业铝型材生产厂家_铝合金型材配件批发精加工定制厂商 - 上海岐易铝业 | 科箭WMS仓库管理软件-TMS物流管理系统-科箭SaaS云服务 | 回转支承-转盘轴承-回转驱动生产厂家-洛阳隆达轴承有限公司 | EPK超声波测厚仪,德国EPK测厚仪维修-上海树信仪器仪表有限公司 | 游泳池设计|设备|配件|药品|吸污机-东莞市太平洋康体设施有限公司 | 自动售货机_无人售货机_专业的自动售货机运营商_免费投放售货机-广州富宏主官网 | 立式矫直机_卧式矫直机-无锡金矫机械制造有限公司 | 元拓建材集团官方网站| ★店家乐|服装销售管理软件|服装店收银系统|内衣店鞋店进销存软件|连锁店管理软件|收银软件手机版|会员管理系统-手机版,云版,App | 威实软件_软件定制开发_OA_OA办公系统_OA系统_办公自动化软件 | 欧洲MV日韩MV国产_人妻无码一区二区三区免费_少妇被 到高潮喷出白浆av_精品少妇自慰到喷水AV网站 | 生态板-实木生态板-生态板厂家-源木原作生态板品牌-深圳市方舟木业有限公司 | 奇酷教育-Python培训|UI培训|WEB大前端培训|Unity3D培训|HTML5培训|人工智能培训|JAVA开发的教育品牌 | 恒湿机_除湿加湿一体机_恒湿净化消毒一体机厂家-杭州英腾电器有限公司 | OpenI 启智 新一代人工智能开源开放平台 | 伸缩节_伸缩器_传力接头_伸缩接头_巩义市联通管道厂 | 煤矿人员精确定位系统_矿用无线通信系统_煤矿广播系统 | 高温链条油|高温润滑脂|轴承润滑脂|机器人保养用油|干膜润滑剂-东莞卓越化学 | 接地电阻测试仪[厂家直销]_电缆故障测试仪[精准定位]_耐压测试仪-武汉南电至诚电力设备 | 邢台人才网_邢台招聘网_邢台123招聘【智达人才网】 | 凝胶成像仪,化学发光凝胶成像系统,凝胶成像分析系统-上海培清科技有限公司 | 北京工业设计公司-产品外观设计-产品设计公司-千策良品工业设计 北京翻译公司-专业合同翻译-医学标书翻译收费标准-慕迪灵 | 考勤系统_考勤管理系统_网络考勤软件_政企|集团|工厂复杂考勤工时统计排班管理系统_天时考勤 | 气动调节阀,电动调节阀,自力式压力调节阀,切断阀「厂家」-浙江利沃夫自控阀门 | 车件|铜件|车削件|车床加工|五金冲压件-PIN针,精密车件定制专业厂商【东莞品晔】 | 硬质合金模具_硬质合金非标定制_硬面加工「生产厂家」-西迪技术股份有限公司 | 深圳公司注册-工商注册公司-千百顺代理记账公司|