Re: [閒聊] 每日leetcode

[oinishere (是oin捏)]

※ 引述 《Rushia (早瀬ユウカの体操服)》 之銘言：
: 　
: 2370. Longest Ideal Subsequence
: https://leetcode.com/problems/longest-ideal-subsequence/description
: 給你一個字串s和一個數字k，找出一個子序列滿足相鄰的字元距離不相差超過k個，返回
: 最長是多長(note:a和z距離25而不是1)。


思路:

第一眼看到
我就想n^2了

然後想了一陣子
發現如果出現兩個a
後面的那個a完全可以繼承前面a的所有東西

然後要找最新的長度的話
只要看那個字母-k+k
產生出來的最後面的那個長度就好了


反正

就是用a~z的字母跟s字串dp

姆咪


class Solution {
public:
    int longestIdealString(string s, int k)
    {
        int len = s.size();

        vector<int> paper(26 , 0);

        int now = 0;
        for(int i = 0 ; i < len ; i ++)
        {
            now = 0;
            int sn = s[i]-'a';
            for(int j = max(0,sn-k) ; j <= min(25,sn+k) ; j ++)
            {
                now = max(now , paper[j]);
            }
            paper[sn] = now + 1;
        }

        int res = 0;
        for(int i = 0 ; i < 26 ; i ++)
        {
            res = max(res,paper[i]);
        }

        return res;
    }
};





--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.132.159 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1714020367.A.0FE.html
推 JIWP: 大師