2023‐07‐23 第 355 场周赛

按分隔符拆分字符串

• 第一题模拟就完事了

class Solution {
public:
    vector<string> splitWordsBySeparator(vector<string>& words, char sep) {
        vector<string> res;
        
        string s = "";
        
        for (auto word : words) {
            for (int i = 0; i < word.size(); i ++) {
                if (word[i] == sep) {
                    if (s != "")res.emplace_back(s);
                    
                    s = "";
                } else s.push_back(word[i]);
            }
            
            if (s != "") res.emplace_back(s);
            
            s = "";
        }
        
        return res;
    }
};

合并后数组中的最大元素

• 第二题思路一开始没想好
• 逆向思维

class Solution {
public:
    long long maxArrayValue(vector<int>& nums) {
        // 数组单调递增
        int n = nums.size();
        
        int i = n - 2;
        
        long long sum = nums[n - 1];
        
        long long res = 0;
        
        while (i >= 0) {
            if (nums[i] <= sum) { // 递减
                sum += nums[i];
                i --;
                
                res = max(res, sum);
            
                continue;
            } else {
                nums[i + 1] = sum;
                sum = nums[i];
                res = max(res, sum);
                i --;
            }
        }
        
        res = max(res, sum);
    
        return res;
    }
};

长度递增组的最大数目

• 题目看着是挺简单的
• 最后还差 6 个样例没有过
• 超时了

class Solution {
public:
    int maxIncreasingGroups(vector<int>& usa) {
        // 按次数进行排序
        // 每个组严格大于前一个组 除了第一个
        // 每次选最大的
        
        sort(usa.begin(), usa.end());
        
        int n = usa.size(); // 大于 0 的个数
        
        int cnt = 1; // 层数
        
        while (n - cnt >= 0 && usa[n - cnt] > 0) { // 正数个数满足层数要求
            
            int idx = 0;
            int f = usa.size() - 1;
            
            while (idx < cnt && f >= 0) {
                
                if (usa[f] > 0) usa[f] --, idx ++, f --;
                
                else break;
            }
            
            sort(usa.begin(), usa.end());
            
            cnt ++;
        }
        
        return cnt - 1;
    }
};

正确思路

class Solution {
public:
    int maxIncreasingGroups(vector<int>& v) {
        int n = v.size();
        sort(v.begin(), v.end());
        int ned = 1;
        long long lef = 0;
        int ans = 0;
        for(int i = 0; i < n; i ++) {
            if(v[i] >= ned) {
                ans ++;
                lef += v[i] - ned;
                ned ++;
            }
            else if(v[i] + lef >= ned) {
                ans ++;
                lef -= ned - v[i];
                ned ++;
            }
            else lef += v[i];
        }
        return ans;
    }
};