Re: [閒聊] 每日leetcode

看板Marginalman作者sustainer123 (caster )時間1周前 (2024/04/22 11:26)推噓5(5推 0噓 2→)

留言7則, 6人參與討論串146/184 (看更多)

※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言： : https://leetcode.com/problems/open-the-lock/description : 752. Open the Lock : 給你一個四個位數的密碼鎖，每個密碼由一個0~9的輪型裝置表示，每次你可以把其中 : 一位數往上轉或往下轉，該密碼鎖初始化為0000，如果轉成 deadends 裡面的密碼時密碼 : 鎖會卡死，求出最少幾步可以讓我們把密碼轉成target，如果不可能就返回-1。 : 思路： : 1.找最短路徑最簡單就bfs，每次我們都把四個位數分別往下轉和往上轉，看看是否最後 : 可以走到target，因為是bfs所以第一個碰到的一定最短step。 : 2.避免往回走用一個set紀錄走過的結果，deadends的值也可以丟進去。 : 3.如果走不到返回-1。 : py code: : ------------------------------------------- : class Solution: : def openLock(self, deadends: List[str], target: str) -> int: : visited = set(deadends) : # BFS : q = deque() : q.append(('0000', 0)) : while q: : curr_lock, step = q.popleft() : if curr_lock == target: : return step : if curr_lock in visited: : continue : visited.add(curr_lock) : for i in range(4): : s1 = curr_lock[:i] + self.wheel_up(curr_lock[i]) + : curr_lock[i + 1:] : s2 = curr_lock[:i] + self.wheel_down(curr_lock[i]) + : curr_lock[i + 1:] : q.append((s1, step + 1)) : q.append((s2, step + 1)) : return -1 : def wheel_up(self, lock: str): : return '0' if lock == '9' else str(int(lock) + 1) : def wheel_down(self, lock: str): : return '9' if lock == '0' else str(int(lock) - 1) : ------------------------------------------- 思路差不多不過我看解答才寫出來我原本的長這樣: Python Code: class Solution: def openLock(self, deadends: List[str], target: str) -> int: dic = defaultdict(list) for i in range(10): if i == 9: dic[9].append(0) dic[0].append(9) else: dic[i].append(i+1) dic[i+1].append(i) q = deque() q.append(("0000",0,0)) visited = set(deadends) while q: lock,node,step = q.popleft() if lock == target: return step if lock in visited: continue visited.add(lock) for i in range(4): for e in dic[node]: s = lock[:i]+str(e)+lock[i+1:] if s not in visited: q.append((s,e,step+1)) return -1 我感覺邏輯差不多ㄅ想不到哪裡出問題解答: Python Code class Solution: def openLock(self, deadends: List[str], target: str) -> int: q = deque() q.append(("0000",0)) visited = set(deadends) while q: lock,step = q.popleft() if lock == target: return step if lock in visited: continue visited.add(lock) for i in range(4): for e in [-1, 1]: s = lock[:i] + str((int(lock[i]) + e + 10) % 10) + lock[i+1:] if s not in visited: q.append((s,step+1)) return -1 想不到錯在哪姆咪 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.43.132.44 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1713756370.A.B00.html

推

SecondRun

04/22 11:26, 1周前 , 1^F

04/22 11:26, 1^F

推

digua

04/22 11:27, 1周前 , 2^F

04/22 11:27, 2^F

※ 編輯: sustainer123 (114.43.132.44 臺灣), 04/22/2024 11:29:39

推

JIWP

04/22 11:30, 1周前 , 3^F