Re: [閒聊] 每日leetcode
https://leetcode.com/problems/freedom-trail/description
514. Freedom Trail
https://assets.leetcode.com/uploads/2018/10/22/ring.jpg
給你一個字串ring表示一個轉盤的文字順序，key 表示密碼，我們可以有兩個操作：
1. 把轉盤往左或往右
2. 把轉盤當前的密碼輸入
求出最少要幾個操作可以把密碼輸入完，題目保證密碼字元一定存在於ring
思路：
1.輸入密碼最少要len(key)次
2.我先往是否可以貪婪想，也就是局部最佳解是否可以得到全域最佳解，反例：
A
B C
B
如果左邊的B比較近 右邊的B比較遠但是離C比較近 他會是更佳解 所以局部最佳解
不能決定全域最佳解 需要窮舉
3.模擬轉盤往左和往右，最少要轉的步數為：
MIN(
往左轉找到key需要的步數 + 從左邊位置繼續找下一個,
往右轉找到key需要的步數 + 從右邊位置繼續找下一個
)
因為會有許多重複步驟所以需要DP(記憶化搜索)
4.返回輸入密碼的次數+轉盤的最小次數
py code:
-------------------------------------------------------
class Solution:
def findRotateSteps(self, ring: str, key: str) -> int:
n = len(ring)
def findLeft(idx: int, target: str):
step = 0
for i in range(idx, -1, -1):
if ring[i] == target:
return (i, step)
step += 1
for i in range(n - 1, idx, -1):
if ring[i] == target:
return (i, step)
step += 1
def findRight(idx: int, target: str):
step = 0
for i in range(idx, n):
if ring[i] == target:
return (i, step)
step += 1
for i in range(idx):
if ring[i] == target:
return (i, step)
step += 1
@cache
def dfs(curr_idx: int, key_idx: int):
if key_idx == len(key):
return 0
l_idx, l_step = findLeft(curr_idx, key[key_idx])
r_idx, r_step = findRight(curr_idx, key[key_idx])
left_res = l_step + dfs(l_idx, key_idx + 1)
right_res = r_step + dfs(r_idx, key_idx + 1)
return min(left_res, right_res)
return len(key) + dfs(0, 0)
-------------------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1714192454.A.A60.html
推
04/27 12:40,
1月前
, 1F
04/27 12:40, 1F
推
04/27 12:42,
1月前
, 2F
04/27 12:42, 2F
推
04/27 12:43,
1月前
, 3F
04/27 12:43, 3F
討論串 (同標題文章)