Re: [閒聊] 每日leetcode已回收
2370. Longest Ideal Subsequence
https://leetcode.com/problems/longest-ideal-subsequence/description
給你一個字串s和一個數字k，找出一個子序列滿足相鄰的字元距離不相差超過k個，返回
最長是多長(note:a和z距離25而不是1)。
思路：
1.第一眼看覺得是動態規劃，最暴力的方法就兩個for迴圈，dp[i]找i前面的所有j，如
果相差不超過k就 dp[i] = max(dp[i], dp[j] + 1) 但 n=10^4 果不其然 TLE。
2.既然TLE了那就只能想辦法減少迴圈做的事，實際上我們不用找前面j個dp，只要找
"前面某某字母結尾"的最長子序列長度就好，頂多做26次，這樣時間複雜度就變O(n)了。
3.然後我迴圈是從 c-k 跑到 c+k+1 (對應距離左邊k和右邊k)，恰好等於c的時候要另外
處理，直接放到迴圈裡會因為順序問題出錯，解釋起來滿麻煩的直接看代碼。
py code:
-----------------------------------
class Solution:
def longestIdealString(self, s: str, k: int) -> int:
n = len(s)
map = {}
res = 1
for i in range(n):
idx = ord(s[i]) - ord('a')
if idx not in map:
map[idx] = 1
else:
map[idx] += 1
for j in range(max(0, idx - k), min(26, idx + k + 1), 1):
if j not in map or idx == j:
continue
map[idx] = max(map[idx], map[j] + 1)
res = max(res, map[idx])
return res
-----------------------------------
送出後只有20% 恨dp
然後翻了別了寫的
-----------------------------------
class Solution:
def longestIdealString(self, s: str, k: int) -> int:
dp = [0] * 126
for c in s:
idx = ord(c)
dp[idx] = max(dp[idx - k : idx + k + 1]) + 1
return max(dp)
-----------------------------------
我寫了好多廢話 哭了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.139.237.196 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1714013609.A.CEC.html
※ 編輯: Rushia (101.139.237.196 臺灣), 04/25/2024 11:00:17
推
04/25 11:00,
1年前
, 1F
04/25 11:00, 1F
推
04/25 11:14,
1年前
, 2F
04/25 11:14, 2F
推
04/25 12:46,
1年前
, 3F
04/25 12:46, 3F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 159 之 1548 篇)：