Re: [閒聊] 每日leetcode

[sustainer123 (caster )]

※ 引述《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: 大師
推 digua: 大師
※ 編輯: sustainer123 (114.43.132.44 臺灣), 04/22/2024 11:29:39
推 JIWP: 大師
推 DJYOSHITAKA: 大師
推 pandix: node定義怪怪的 上下轉應該是for e in dic[int(lock[i])]
→ pandix:  之類的東西
→ sustainer123: 啊 我懂了 我不用多搞個node