如何基于python實(shí)現(xiàn)不鄰接植花
有 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)。
相關(guān)文章:
1. 使用Hangfire+.NET 6實(shí)現(xiàn)定時(shí)任務(wù)管理(推薦)2. Xml簡(jiǎn)介_(kāi)動(dòng)力節(jié)點(diǎn)Java學(xué)院整理3. 如何在jsp界面中插入圖片4. jsp實(shí)現(xiàn)登錄驗(yàn)證的過(guò)濾器5. phpstudy apache開(kāi)啟ssi使用詳解6. JSP之表單提交get和post的區(qū)別詳解及實(shí)例7. jsp文件下載功能實(shí)現(xiàn)代碼8. 詳解瀏覽器的緩存機(jī)制9. vue3+ts+elementPLus實(shí)現(xiàn)v-preview指令10. xml中的空格之完全解說(shuō)
