如何基于python實(shí)現(xiàn)不鄰接植花
有 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è)花園中種植的花的種類?；ǖ姆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 <= 10000
0 <= 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-hout:{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] = 1
flowers=[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
簡化方法:利用集合快速搞定
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
以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
python和pywin32實(shí)現(xiàn)窗口查找、遍歷和點(diǎn)擊的示例代碼
這篇文章主要介紹了python和pywin32實(shí)現(xiàn)窗口查找、遍歷和點(diǎn)擊的示例代碼，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-04-04
這篇文章主要介紹了如何使用Python調(diào)整圖像大小，幫助大家更好的利用python處理圖像，感興趣的朋友可以了解下2020-09-09
這篇文章主要介紹了python爬蟲看看虎牙女主播中誰最“頂”,本文分步驟通過圖文實(shí)例相結(jié)合給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-12-12
Python實(shí)現(xiàn)周期性抓取網(wǎng)頁內(nèi)容的方法
這篇文章主要介紹了Python實(shí)現(xiàn)周期性抓取網(wǎng)頁內(nèi)容的方法,涉及Python時(shí)間函數(shù)及正則匹配的相關(guān)操作技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-11-11
Django分頁查詢并返回jsons數(shù)據(jù)(中文亂碼解決方法)
python進(jìn)階教程之函數(shù)參數(shù)的多種傳遞方法
