2022-06-27

[Zheaoli]

2022-06-27

[SaraadKun]

522. 最长特殊序列 II

class Solution {
    public int findLUSlength(String[] strs) {
        //输入数组按长度降序排序，从最大长度的字符串开始，检查当前字符串是否为特殊序列，若是则直接返回当前长度
        //检查逻辑为：
        //  1.对于当前str，若数组中有重复的元素则不符合要求；
        //  2.从已遍历过的长度不小于str.length()的字符串集合中进行筛查，若当前字符串为其子序列则不符合要求；
        //  3. 1.2.两步筛查后仍然未排除的str，即为最长特殊序列（之一）
        Arrays.sort(strs, ((o1, o2) -> o2.length() - o1.length()));
        Set<String> set = new HashSet<>();
        int idx = 0, len = strs[0].length();
        Map<String, Integer> map = new HashMap<>();
        for (int i = len; i > 0; i--) {
            while (idx < strs.length && strs[idx].length() == i) {
                map.put(strs[idx], map.getOrDefault(strs[idx], 0) + 1);
                idx++;
            }
            out: for (String s : map.keySet()) {
                if (map.get(s) == 1) {
                    for (String str : set) {
                        if (check(str, s)) {
                            continue out;
                        }
                    }
                    return i;
                }
                set.add(s);
            }
            map.clear();
        }
        return -1;
    }

    private boolean check(String str, String s) {
        int n = str.length(), m = s.length(), i = 0, j = 0;
        while (i < n && j < m) {
            if (str.charAt(i) == s.charAt(j))
                j++;
            i++;
        }
        return j == m;
    }
}

---

WeChat: Saraad

[SaraadKun]

1689. Partitioning Into Minimum Number Of Deci-Binary Numbers

class Solution {
    public int minPartitions(String n) {
        //answer only depends on the single digit, find the maximum digit
        char[] chs = n.toCharArray();
        char ans = '0';
        for (char ch : chs) {
            if (ch > ans)
                ans = ch;
            if (ans == '9')
                return 9;
        }
        return ans - '0';
    }
}

---

WeChat: Saraad

[dreamhunter2333]

#include <iostream>
#include <vector>
using namespace std;
/*
 * @lc app=leetcode.cn id=522 lang=cpp
 *
 * [522] 最长特殊序列 II
 */

// @lc code=start
class Solution
{
public:
    int findLUSlength(vector<string> &strs)
    {
        int res = -1;
        int n = strs.size();
        for (size_t i = 0; i < n; i++)
        {
            bool check = true;
            for (size_t j = 0; j < n; j++)
            {
                if (i != j && is_sub(strs[j], strs[i]))
                {
                    check = false;
                    break;
                }
            }
            if (check)
                res = max(res, static_cast<int>(strs[i].size()));
        }
        return res;
    }
    bool is_sub(string &word1, string &word2)
    {
        int i = 0, j = 0;
        int n = word1.size();
        int m = word2.size();
        while (i < n && j < m)
        {
            if (word1[i] == word2[j])
                j++;
            i++;
        }
        return j == m;
    }
};
// @lc code=end
int main()
{
    Solution s = Solution();
    string strs[] = {"aba", "cdc", "eae"};
    vector<string> vect(strs, strs + 3);
    cout << s.findLUSlength(vect) << endl;
}

---

微信id: 而我撑伞 来自 vscode 插件