最长特殊子序列（二）

C++ 解法, 执行用时: 3ms, 内存消耗: 424KB, 提交时间: 2022-08-05

class Solution {
  public:
    int longestUniqueSubsequence(vector<string>& strs) {
        int j = 0;
        int z = -1;
        for (int i = 0; i < strs.size(); ++i) {
            for (j = 0; j < strs.size(); ++j) {
                if (i == j) continue;
                if (func(strs[i], strs[j])) {
                    break;
                }
            }
            int H = strs[i].size();
            if (j == strs.size()) z = max(z, H);
        }
        return z;
    }
    
    bool func(string& a, string& b) {
        int j = 0;
        for (int i = 0; i < b.size() && j < a.size(); ++i) {
            if (a[j] == b[i]) j++;
        }
        return j == a.size();
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 468KB, 提交时间: 2022-07-09

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param strs string字符串vector 
     * @return int整型
     */
    int partition(vector<string>& a,int low,int high){
        int i=low,j=high;
        string pivot=a[low],t;
        while(i<=j){
            while(i<j&&a[j].length()<pivot.length())j--;
            while(i<j&&a[i].length()>=pivot.length())i++;
            if(i==j)break;
            t=a[j];
            a[j]=a[i];
            a[i]=t;
        }
        a[low]=a[i];
        a[i]=pivot;
        return i;
    }
    void quickSort(vector<string>& a,int low,int high){
        if(low>=high)return;
        int mid=partition(a,low,high);
        quickSort(a,low,mid-1);
        quickSort(a,mid+1,high);
    }
    int longestUniqueSubsequence(vector<string>& strs) {
        // write code here
        quickSort(strs,0,strs.size()-1);
        string s=strs[0];
        unordered_map<string,int>u;
        u[s]++;
        for(int i=1;i<strs.size();i++){
            if(strs[i].length()<s.length())break;
            if(u[strs[i]]>0)return -1;
            else u[strs[i]]++;
        }
        return s.length();
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 420KB, 提交时间: 2022-08-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param strs string字符串vector 
     * @return int整型
     */
    int longestUniqueSubsequence(vector<string>& strs) {
        // write code here
        int j=0;
        int z=-1;
        for(int i=0;i<strs.size();++i)
        {
            for(j=0;j<strs.size();++j)
            {
                if(i==j)
                    continue;
                if(func(strs[i],strs[j]))
                {
                    break;
                }
            }
            int H=strs[i].size();
            if(j==strs.size())
                z=max(z,H);
        }
        return z;
    }
    bool func(string &a,string &b)
    {
        int j=0;
        for(int i=0;i<b.size()&&j<a.size();++i)
        {
            if(a[j]==b[i])
                j++;
        }
        return j==a.size();
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 424KB, 提交时间: 2022-07-07

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param strs string字符串vector 
     * @return int整型
     */
    int longestUniqueSubsequence(vector<string>& strs) {
        // write code here
        int j=0;
        int res=-1;
        for(int i=0;i<strs.size();++i){
            for(j=0;j<strs.size();++j){
                if(i==j) continue;
                if(func(strs[i],strs[j])){
                    break;
                }
            }
            int len=strs[i].size();
            if(j==strs.size()) res=max(res,len);
        }
        return res;
    }
    bool func(string& a,string& b){
        int j=0;
        for(int i=0;i<b.size()&&j<a.size();++i){
            if(a[j]==b[i]) j++;
        }
        return j==a.size();
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 436KB, 提交时间: 2022-07-09

typedef pair<string, int> PAIR;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param strs string字符串vector 
     * @return int整型
     */
    static bool cmp(string a, string b)
    {
        if(a.length() == b.length())
        {
            return a > b;
        }
        return a.length() > b.length();
    }
    static bool cmp2(PAIR a, PAIR b)
    {
        if(a.first.length() == b.first.length())
        {
            return a.first > b.first;
        }
        return a.first.length() > b.first.length();
    }
    int longestUniqueSubsequence(vector<string>& strs) {
        // write code here
        int ans = -1;
        sort(strs.begin(), strs.end(), cmp);
        map<string, int> mp;
        
        for(auto s : strs)
        {
            mp[s] += 1;
        }
        
        vector<PAIR> v(mp.begin(), mp.end());
        sort(v.begin(), v.end(), cmp2);
        int vis[105] = {0};
        for(int i = 0; i < strs.size(); i++)
        {
            if(vis[i])
                continue;
            for(int j = i+1; j < strs.size(); j++)
            {
                if(vis[j])
                    continue;
                if(strs[i].find(strs[j]) != -1)
                {
                    if(strs[i].size() == strs[j].size())
                    {
                        vis[i] = 1;
                        //cout << v[i].first << " " << v[j].first << endl;
                    }
                        
                    vis[j] = 1;
                }
            }
            if(vis[i] == 0)
            {
                return strs[i].length();
            }
        }
            
        return ans;
    }
};

详情