C/C++教程

LC2014-重复k次的最长子序列

本文主要是介绍LC2014-重复k次的最长子序列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

2014. 重复 K 次的最长子序列

  • 统计s中每个字符出现频率cnt,获得频率大于等于k的字符,答案只会由这些字符组成,因此dfs全排列再check该排列是否符合出现k次这一条件
  • 为了保证字典序,将chs逆序存储,并从大到小枚举字符串长度,遇到符合即返回答案
class Solution {
public:
    string s; int k;
    bool check(string &t){
        int cnt = 0;
        for(int i = 0, j = 0; i < s.size(); ++i){
            if(s[i] == t[j]) j++;
            if(j == t.size()) j = 0, cnt ++;
        }
        return cnt >= k;
    }
    bool dfs(vector<char> &chs, const int len, string &t, int used){
        if(t.size() == len){
            if(check(t)) return true;
            return false;
        }
        for(int i = 0; i < chs.size(); ++i){
            if(!(used >> i & 1)){
                t.push_back(chs[i]);
                if(dfs(chs, len, t, used | (1 << i))) return true;
                t.pop_back();
            }
        }
        return false;
    }
    string longestSubsequenceRepeatedK(string _s, int _k) {
        s = _s, k = _k;
        vector<int>cnt(26);
        vector<char>chs;
        for(auto x : s) ++cnt[x - 'a'];
        for(int i = 25; i >= 0; --i) //get 频率大于k的字符 倒序排序
            while(cnt[i] / k){
                chs.push_back(i + 'a');
                cnt[i] -= k;
            }
        for(int len = chs.size(); len >= 1; --len){ // 枚举长度
            string t = "";
            if(dfs(chs,len,t,0)) return t;
        }
        return "";
    }
};
这篇关于LC2014-重复k次的最长子序列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!