LeetCode 第 388 场周赛个人题解

目录

100233. 重新分装苹果

原题链接

思路分析

AC代码

100247. 幸福值最大化的选择方案

原题链接

思路分析

AC代码

100251. 数组中的最短非公共子字符串

原题链接

思路分析

AC代码

100216. K 个不相交子数组的最大能量值

原题链接

思路分析

AC代码

100233. 重新分装苹果

原题链接

100233. 重新分装苹果

思路分析

直接模拟

降序排序capacity，倒序累加，当大于苹果总重量的时候我们就返回

时间复杂度：O(nlgon)

AC代码

class Solution {
public:
    int minimumBoxes(vector& apple, vector& capacity) {
        int s = accumulate(apple.begin(), apple.end(), 0);
        int n = capacity.size();
        sort(capacity.begin(), capacity.end(), [](int x, int y){return y = s) return i + 1;
        }
        return n;
    }
};

100247. 幸福值最大化的选择方案

原题链接

　　100247. 幸福值最大化的选择方案

思路分析

　　贪心

优先分配幸福值大的孩子，然后直接模拟

时间复杂度：O(nlgon)

AC代码

class Solution {
public:
    long long maximumHappinessSum(vector& a, long long k) {
        long long ret = 0;
        sort(a.begin(), a.end(), [](int x, int y){return x > y;});
        for(int i = 0, t = 0; i  t) ret += a[i] - t;
        }
        return ret;
    }
};

100251. 数组中的最短非公共子字符串

原题链接

100251. 数组中的最短非公共子字符串

思路分析

其实直接暴力就行了

用哈希表或者字典树存储所有字符串的所有子串，然后遍历每个字符串的子串找到不在哈希表或者字典树中的子串中最短并且字典序最小的那个

想着复习下字典树就敲了下字典树

时间复杂度分析：

子串长度有k种，起点有k个，那么存储一个长度为k的字符串的所有子串就是O(k^3)

然后枚举n个字符串的所有字串并判断就是O(n*k^3)

因为k最大也就20，n最大100，因而整体也就1e6左右

故时间复杂度O(n*k^3)是可以的

AC代码

struct node{
    unordered_mapch;
    unordered_set words;
};
class Solution {
public:
    vector shortestSubstrings(vector& arr) {
        node* rt = new node, *cur;
        vector ret;
        for(int k = 0, sz = arr.size(); k ch.count(arr[k][j])) cur->ch[arr[k][j]] = new node;
                    cur = cur->ch[arr[k][j]], cur->words.insert(k);
                }
                    
            }
        for(int k = 0, sz = arr.size(); k ch[arr[k][j]];
                    if(cur->words.size() == 1){
                        if(tmp.empty() || j - i + 1  
100216. K 个不相交子数组的最大能量值
 
 
原题链接
 
100216. K 个不相交子数组的最大能量值
 
思路分析
 
　　考虑题目说n*k