Re: [閒聊] 每日leetcode

看板Marginalman作者DJYOSHITAKA (franchouchouISBEST)時間1周前 (2024/04/25 22:20)推噓2(2推 0噓 1→)

留言3則, 3人參與討論串161/197 (看更多)

2370. Longest Ideal Subsequence 一開始有想到大方向但做起來有點不順沒有把dp定義的清楚一點的話寫起來就會錯東錯西第i輪的dp[c] 定義成走到第i輪的時候若str[i]==c的話當時的長度所以for loop最前面可以更新ans 然後再來更新以c上下找k的範圍裏面的dp arr = dp[c]+1 (如果比較大的話) 我第一個錯是dp沒有initialize成1 會出問題第二個是更新的時候我一開始寫成dp[idx] = max(dp[idx], dp[s[i]-'a']+1); 這樣會把自己重複加造成c的右半會被誤加簡單來說我好爛 int longestIdealString(string s, int k) { vector<int> dp(26, 1); int ans = 0; for(int i=0; i<s.size(); i++) { ans = max(ans, dp[s[i]-'a']); int cur_cnt = dp[s[i]-'a']; for(int idx=max((s[i] - 'a') - k, 0); idx<=min((s[i] - 'a') + k, 25); idx++) { dp[idx] = max(dp[idx], cur_cnt+1); } } return ans; } -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.83.190 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1714054858.A.1A0.html

推

sustainer123

04/25 22:24, 1周前 , 1^F

04/25 22:24, 1^F

→

DJYOSHITAKA

04/25 22:24, 1周前 , 2^F

04/25 22:24, 2^F

推

pandix

04/25 22:33, 1周前 , 3^F

04/25 22:33, 3^F