LeetCode 第 388 场周赛个人题解-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode 第 388 场周赛个人题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

100233. 重新分装苹果

原题链接

思路分析

AC代码

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

原题链接

思路分析

AC代码

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

原题链接

思路分析

AC代码

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

原题链接

思路分析

AC代码

100233. 重新分装苹果

原题链接

100233. 重新分装苹果

思路分析

直接模拟

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

时间复杂度：O(nlgon)

AC代码

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

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

原题链接

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

思路分析

　　贪心

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

时间复杂度：O(nlgon)

AC代码

class Solution {
public:
    long long maximumHappinessSum(vector<int>& 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 < k; i++, t++){
            if(a[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_map<char,node*>ch;
    unordered_set<int> words;
};
class Solution {
public:
    vector<string> shortestSubstrings(vector<string>& arr) {
        node* rt = new node, *cur;
        vector<string> ret;
        for(int k = 0, sz = arr.size(); k < sz; k++)
            for(int i = 0, n = arr[k].size(); i < n; i++){
                cur = rt;
                for(int j = i; j < n; j++){
                    if(!cur->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 < sz; k++){
            string tmp;
            for(int i = 0, j, n = arr[k].size(); i < n; i++){
                cur = rt;
                for(j = i; j < n; j++){
                    cur = cur->ch[arr[k][j]];
                    if(cur->words.size() == 1){
                        if(tmp.empty() || j - i + 1 < tmp.size() || (j - i + 1 == tmp.size() && arr[k].substr(i, j - i + 1) < tmp)) tmp = arr[k].substr(i, j - i + 1);
                        break;
                    }
                }
            }
            ret.emplace_back(tmp);
        }
        return ret;
    }
};

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

原题链接

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

思路分析

　　考虑题目说n*k <= 1e6，所以想到用dp

定义状态

f[i][j][0]为前i个元素拆出j个子数组且第i个元素在第j个子数组中的最大能量和

f[i][j][1]为前i个元素拆出j个子数组且第i个元素不在第j个子数组中的最大能量和

那么有转移方程

f[i][j][1] = max(f[i - 1][j][0], f[i - 1][j][1]);即不选第i个数，那么直接由上一行转移

选第i个数并且单独成第j组，那么前i-1个数要拆出j-1组，第i-1个数在不在第j-1组取大的那个
if(j)
f[i][j][0] = max(f[i][j][0], max(f[i - 1][j - 1][1], f[i - 1][j - 1][0]) + 1LL * (j & 1 ? 1 : -1) * (k - j + 1) * nums[i - 1]);
选第i个数并且加入第j组
f[i][j][0] = max(f[i][j][0], f[i - 1][j][0] + 1LL * (j & 1 ? 1 : -1) * (k - j + 1) * nums[i - 1]);

时间复杂度O(nk)文章来源地址https://www.toymoban.com/news/detail-840071.html

AC代码

class Solution {
public:
    long long maximumStrength(vector<int>& nums, int k) {
        int n = nums.size();
        vector<vector<vector<long long>>> f(n + 1, vector<vector<long long>>(k + 1, vector<long long>(2, -1e18)));
        f[0][0][1] = 0;
        
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= k; j++){
                //不选
                f[i][j][1] = max(f[i - 1][j][0], f[i - 1][j][1]);
                //选
                //单独成组
                if(j)
                    f[i][j][0] = max(f[i][j][0], max(f[i - 1][j - 1][1], f[i - 1][j - 1][0]) + 1LL * (j & 1 ? 1 : -1) * (k - j + 1) * nums[i - 1]);
                //加到前面
                f[i][j][0] = max(f[i][j][0], f[i - 1][j][0] + 1LL * (j & 1 ? 1 : -1) * (k - j + 1) * nums[i - 1]);
            }
        }
        
        return max(f[n][k][0], f[n][k][1]);
    }
};

到了这里，关于LeetCode 第 388 场周赛个人题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！