Re: [閒聊] 每日leetcode已回收
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)
-------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.138.187.253 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1713750317.A.007.html
推
04/22 10:14,
1年前
, 1F
04/22 10:14, 1F
推
04/22 10:19,
1年前
, 2F
04/22 10:19, 2F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 145 之 1552 篇)：