lc820

后缀反转 字典序排序截取

 class Solution {

public:

   int minimumLengthEncoding(vector<string>& words)

{

    int N = words.size();

    // 反转每个单词

    vector<string> reversed_words;

    for (string word : words) {

        reverse(word.begin(), word.end());

        reversed_words.push_back(word);

    }

    // 字典序排序    

    sort(reversed_words.begin(), reversed_words.end());

 

    int res = 0;

    for (int i = 0; i < N; i++) {

        if (i+1 < N && reversed_words[i+1].find(reversed_words[i]) == 0) {

            // jump

        } else {

            res += reversed_words[i].length() + 1; // 单词加上一个 '#' 的长度

        }

    }

    return res;

}

};

桶排序(其实是没必要的，但也能做就是了

charToWords[word[0]].push_back(word); // 按反转后单词的首字母分组

 

unordered_set  的迭代器返回的是 const  引用，遍历其元素时不能使用非 const  引用

需将最后遍历 kept  的循环中 string&  改为 const string&  

class Solution {
public:
    int minimumLengthEncoding(vector<string>& words) {
    if (words.empty()) return 0;
    
    // 1：反转单词，并按首字母分组（桶排序的核心，键为首字母，值为反转后的单词列表）
    unordered_map<char, vector<string>> charToWords;
    for (string word : words) {
        reverse(word.begin(), word.end());
        charToWords[word[0]].push_back(word); // 按反转后单词的首字母分组
    }
    
    unordered_set<string> kept; 
    
    // 2：遍历每个首字母组，判断单词是否是同组内更长单词的前缀
    for (auto& pair : charToWords)

{
        vector<string>& group = pair.second;
        sort(group.begin(), group.end(), 
             [](const string& a, const string& b) { return a.size() > b.size(); }); 
        
        for (int i = 0; i < group.size(); ++i) {
            bool isPrefix = false;
            for (int j = 0; j < i; ++j) { 
                if (group[j].substr(0, group[i].size()) == group[i]) {
                    isPrefix = true;
                    break;
                }
            }
            if (!isPrefix) 
                kept.insert(group[i]);
        }
    }
    
    int res = 0;
    for (const string& s : kept) {
        res += s.size() + 1;
    }
    return res;
}

};

 

lc2289

很好的一个attention

 

单调栈从后往前遍历，维护每个元素需要经过的操作轮次：

当当前元素大于栈顶元素时，累加栈顶元素的操作轮次（取有效最大值），最终返回所有元素操作轮次的最大值，即为使数组非递减所需的操作数

class Solution {
public:
    int totalSteps(vector<int>& nums) {
        int n = nums.size();
        vector<int>time(n);
        stack<int>zan;
        for(int i = n-1;i >= 0;i--){
            while(!zan.empty() && nums[i] > nums[zan.top()]){
                time[i]++;
                time[i] += max(0,time[zan.top()]-time[i]);
                zan.pop();
            }
            zan.push(i);
        }
        return *max_element(time.begin(),time.end());
    }
};

 

lc3747

计算 [1, n] 区间内无重复数字的正整数个数，分两类统计： 
1. 数位长度比 n 短的数：直接用 9 的幂次计算（首位9种非0选择，后续每位9/8/...种不重复选择）

2. 数位长度与 n 相同的数：从高位到低位枚举，统计不大于 n 且无重复数字的数，最后验证 n 本身是否符合条件并补充计数

class Solution {
public:
    long long countDistinct(long long n) {
        // 预处理 9 的幂次
        const int MAXL = 18;
        long long P[MAXL];
        P[0] = 1;
        for (int i = 1; i < MAXL; i++) P[i] = P[i - 1] * 9;

        vector<int> A;
        for (; n; n /= 10) A.push_back(n % 10);

        long long ans = 0;
        // 先统计数位比 n 少的
        for (int i = 1; i < A.size(); i++) ans += P[i];
        bool ok = true;
        // 统计数位和 n 一样的，枚举最长公共前缀到哪个位置
        for (int i = A.size() - 1; i >= 0; i--) {
            // 这一位必须要填 0，后面不用看了
            if (A[i] == 0) { ok = false; break; }
            ans += (A[i] - 1) * P[i];
        }
        // 看看 n 本身是否有 0
        if (ok) ans++;
        return ans;
    }
};