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

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

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

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

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

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

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

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

以數(shù)組形式返回選擇的方案作為答案 answer,其中 answer[i] 為在第 (i+1) 個(gè)花園中種植的花的種類。花的種類用 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)入或離開。保證存在答案。

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

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

可以用字典來存儲(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是從左邊開始取

集合的相減

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

out:{1,2,3,4}

我的題解

題解1

class Solution: # 整體思路采用BFS方法,還需考慮不連通圖的問題,然后著手結(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)建無向鄰接表,無鄰居則不構(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,說明不是連通圖 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): #如果鄰居未被訪問過 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

簡(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)建無向鄰接表,無鄰居則不構(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ǔ)鄰居含有的花類型 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)文章:
主站蜘蛛池模板: 内窥镜-工业内窥镜厂家【上海修远仪器仪表有限公司】 | 铝镁锰板厂家_进口钛锌板_铝镁锰波浪板_铝镁锰墙面板_铝镁锰屋面-杭州军晟金属建筑材料 | 网优资讯-为循环资源、大宗商品、工业服务提供资讯与行情分析的数据服务平台 | 污水处理设备-海普欧环保集团有限公司 | 深圳侦探联系方式_深圳小三调查取证公司_深圳小三分离机构 | 一氧化氮泄露报警器,二甲苯浓度超标报警器-郑州汇瑞埔电子技术有限公司 | 南京蜂窝纸箱_南京木托盘_南京纸托盘-南京博恒包装有限公司 | RTO换向阀_VOC高温阀门_加热炉切断阀_双偏心软密封蝶阀_煤气蝶阀_提升阀-湖北霍科德阀门有限公司 | 二维运动混料机,加热型混料机,干粉混料机-南京腾阳干燥设备厂 | 低温柔性试验仪-土工布淤堵-沥青车辙试验仪-莱博特(天津)试验机有限公司 | 电地暖-电采暖-发热膜-石墨烯电热膜品牌加盟-暖季地暖厂家 | 东莞注册公司-代办营业执照-东莞公司注册代理记账-极刻财税 | 带锯机|木工带锯机圆木推台锯|跑车带锯机|河北茂业机械制造有限公司| | 河南空气能热水器-洛阳空气能采暖-洛阳太阳能热水工程-洛阳润达高科空气能商行 | 北京公司注册_代理记账_代办商标注册工商执照-企力宝 | Trimos测长机_测高仪_TESA_mahr,WYLER水平仪,PWB对刀仪-德瑞华测量技术(苏州)有限公司 | 广州印刷厂_广州彩印厂-广州艺彩印务有限公司 | 【官网】博莱特空压机,永磁变频空压机,螺杆空压机-欧能优 | 楼承板-开闭口楼承板-无锡海逵楼承板| 上海软件开发-上海软件公司-软件外包-企业软件定制开发公司-咏熠科技 | 承插管件_不锈钢承插管件_锻钢高压管件-温州科正阀门管件有限公司 | 聚合氯化铝厂家-聚合氯化铝铁价格-河南洁康环保科技 | 换网器_自动换网器_液压换网器--郑州海科熔体泵有限公司 | 贵州自考_贵州自学考试网| 长沙中央空调维修,中央空调清洗维保,空气能热水工程,价格,公司就找维小保-湖南维小保环保科技有限公司 | 除湿机|工业除湿机|抽湿器|大型地下室车间仓库吊顶防爆除湿机|抽湿烘干房|新风除湿机|调温/降温除湿机|恒温恒湿机|加湿机-杭州川田电器有限公司 | 红外光谱仪维修_二手红外光谱仪_红外压片机_红外附件-天津博精仪器 | 新疆系统集成_新疆系统集成公司_系统集成项目-新疆利成科技 | 蒸压釜_蒸养釜_蒸压釜厂家-山东鑫泰鑫智能装备有限公司 | 北京软件开发_软件开发公司_北京软件公司-北京宜天信达软件开发公司 | 不干胶标签,不干胶标签纸_厂家-山东同力胶粘制品 | 电位器_轻触开关_USB连接器_广东精密龙电子科技有限公司 | 中央空调温控器_风机盘管温控器_智能_液晶_三速开关面板-中央空调温控器厂家 | 塑料异型材_PVC异型材_封边条生产厂家_PC灯罩_防撞扶手_医院扶手价格_东莞市怡美塑胶制品有限公司 | 油罐车_加油机_加油卷盘_加油机卷盘_罐车人孔盖_各类球阀_海底阀等车用配件厂家-湖北华特专用设备有限公司 | Duoguan 夺冠集团| 污水处理设备维修_污水处理工程改造_机械格栅_过滤设备_气浮设备_刮吸泥机_污泥浓缩罐_污水处理设备_污水处理工程-北京龙泉新禹科技有限公司 | 绿萝净除甲醛|深圳除甲醛公司|测甲醛怎么收费|培训机构|电影院|办公室|车内|室内除甲醛案例|原理|方法|价格立马咨询 | 防弹玻璃厂家_防爆炸玻璃_电磁屏蔽玻璃-四川大硅特玻科技有限公司 | 动库网动库商城-体育用品专卖店:羽毛球,乒乓球拍,网球,户外装备,运动鞋,运动包,运动服饰专卖店-正品运动品网上商城动库商城网 - 动库商城 | 便携式表面粗糙度仪-彩屏硬度计-分体式粗糙度仪-北京凯达科仪科技有限公司 |