leetcode weekly contes 359

放水的一次周赛了，除了 T4 以外基本上都是非常简单的题目了，当然 T4 也是一个小技巧而已。

7004. 判别首字母缩略词

给你一个字符串数组 words 和一个字符串 s ，请你判断 s 是不是 words 的 首字母缩略词 。

如果可以按顺序串联 words 中每个字符串的第一个字符形成字符串 s ，则认为 s 是 words 的首字母缩略词。例如，"ab" 可以由 ["apple", "banana"] 形成，但是无法从 ["bear", "aardvark"] 形成。

如果 s 是 words 的首字母缩略词，返回 true ；否则，返回 false 。

示例 1：

输入：words = ["alice","bob","charlie"], s = "abc"
输出：true
解释：words 中 "alice"、"bob" 和 "charlie" 的第一个字符分别是 'a'、'b' 和 'c'。因此，s = "abc" 是首字母缩略词。

示例 2：

输入：words = ["an","apple"], s = "a"
输出：false
解释：words 中 "an" 和 "apple" 的第一个字符分别是 'a' 和 'a'。
串联这些字符形成的首字母缩略词是 "aa" 。
因此，s = "a" 不是首字母缩略词。

示例 3：

输入：words = ["never","gonna","give","up","on","you"], s = "ngguoy"
输出：true
解释：串联数组 words 中每个字符串的第一个字符，得到字符串 "ngguoy" 。
因此，s = "ngguoy" 是首字母缩略词。

提示：

1 <= words.length <= 100
1 <= words[i].length <= 10
1 <= s.length <= 100
words[i] 和 s 由小写英文字母组成

地址

https://leetcode.cn/contest/weekly-contest-359/problems/check-if-a-string-is-an-acronym-of-words/

题意

直接模拟

思路

拼接每个字符串的首字母即可，检测拼接后的字符串是否与 $s$ 相等。
复杂度分析：

时间复杂度：$O(n)$, 其中 $n$ 表示字符串的长度。
空间复杂度：$O(n)$, 其中 $n$ 表示字符串的长度。

代码

[sol1-C++]

class Solution:
    def isAcronym(self, words: List[str], s: str) -> bool:
        return ''.join(w[0] for w in words) == s

6450. k-avoiding 数组的最小总和

给你两个整数 n 和 k 。

对于一个由不同正整数组成的数组，如果其中不存在任何求和等于 k 的不同元素对，则称其为 k-avoiding 数组。

返回长度为 n 的 k-avoiding 数组的可能的最小总和。

示例 1：

输入：n = 5, k = 4
输出：18
解释：设若 k-avoiding 数组为 [1,2,4,5,6] ，其元素总和为 18 。
可以证明不存在总和小于 18 的 k-avoiding 数组。

示例 2：

输入：n = 2, k = 6
输出：3
解释：可以构造数组 [1,2] ，其元素总和为 3 。
可以证明不存在总和小于 3 的 k-avoiding 数组。

提示：

1 <= n, k <= 50

地址

https://leetcode.cn/contest/weekly-contest-359/problems/determine-the-minimum-sum-of-a-k-avoiding-array/

题意

贪心算法

思路

对于任意的元素 $x$，我们对于 $(x, k - x)$ 只能取其中一个，题目要求总和最小，因此我们尽可能选择每个 $x$ 尽可能的小即可。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 为给定的元素。
空间复杂度：$O(n)$，其中 $n$ 为给定的元素。

代码

class Solution {
public:
    int minimumSum(int n, int k) {
        int sum = 0;
        int tot = 0;
        vector<bool> valid(1000, true);
        for (int i = 1; i <= 1000; i++) {
            if (valid[i]) {
                tot++;
                sum += i;
                if (i <= k) {
                    valid[k - i] = false;
                }
            }
            if (tot == n) {
                break;
            }
        }
        return sum;
    }
};

7006. 销售利润最大化

给你一个整数 n 表示数轴上的房屋数量，编号从 0 到 n - 1 。

另给你一个二维整数数组 offers ，其中 offers[i] = [starti, endi, goldi] 表示第 i 个买家想要以 goldi 枚金币的价格购买从 starti 到 endi 的所有房屋。

作为一名销售，你需要有策略地选择并销售房屋使自己的收入最大化。

返回你可以赚取的金币的最大数目。

注意同一所房屋不能卖给不同的买家，并且允许保留一些房屋不进行出售。

示例 1：

输入：n = 5, offers = [[0,0,1],[0,2,2],[1,3,2]]
输出：3
解释：
有 5 所房屋，编号从 0 到 4 ，共有 3 个购买要约。
将位于 [0,0] 范围内的房屋以 1 金币的价格出售给第 1 位买家，并将位于 [1,3] 范围内的房屋以 2 金币的价格出售给第 3 位买家。
可以证明我们最多只能获得 3 枚金币。

示例 2：

输入：n = 5, offers = [[0,0,1],[0,2,10],[1,3,2]]
输出：10
解释：有 5 所房屋，编号从 0 到 4 ，共有 3 个购买要约。
将位于 [0,2] 范围内的房屋以 10 金币的价格出售给第 2 位买家。
可以证明我们最多只能获得 10 枚金币。

提示：

1 <= n <= 105
1 <= offers.length <= 105
offers[i].length == 3
0 <= starti <= endi <= n - 1
1 <= goldi <= 103

地址

https://leetcode.cn/contest/weekly-contest-359/problems/maximize-the-profit-as-the-salesman/

题意

动态规划

思路

非常简单的动态规划，设 $dp[i]$ 表示前 $i$ 个房屋可以得到的最大利润，将所有的 offer 按照 end 从小到大进行排序，每次访问 $i$ 时，如果此时以 $i$ 为结尾的出价为 $[l,i,cost]$，此时可以得到：

$$dp[i] = max(dp[i-1], dp[l-1] + cost)$$

利用上述递推公式求的最大值即可，结果返回 $dp[n-1]$ 即可。
复杂度分析：

时间复杂度：$O(n + m)$，其中 $n$ 表示给定房屋的数量， $m$ 表示 $offer$ 的数量；
空间复杂度：$O(n)$，其中 $n$ 表示给定房屋的数量。

代码

class Solution {
public:
    int maximizeTheProfit(int n, vector<vector<int>>& offers) {
        vector<vector<pair<int, int>>> arr(n);
        for (auto v : offers) {
            arr[v[1]].emplace_back(v[0], v[2]);
        }
        vector<int> dp(n);
        for (int i = 0; i < n; i++) {
            if (i > 0) dp[i] = dp[i - 1];
            for (auto [l, cost] : arr[i]) {
                if (l > 0) {
                    dp[i] = max(dp[i], dp[l - 1] + cost);
                } else {
                    dp[i] = max(dp[i], cost);
                }
            }
        }
        return dp[n - 1];
    }
};

6467. 找出最长等值子数组

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。

从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。

子数组 是数组中一个连续且可能为空的元素序列。

示例 1：

输入：nums = [1,3,2,3,1,3], k = 3
输出：3
解释：最优的方案是删除下标 2 和下标 4 的元素。
删除后，nums 等于 [1, 3, 3, 3] 。
最长等值子数组从 i = 1 开始到 j = 3 结束，长度等于 3 。
可以证明无法创建更长的等值子数组。

示例 2：

输入：nums = [1,1,2,2,1,1], k = 2
输出：4
解释：最优的方案是删除下标 2 和下标 3 的元素。 
删除后，nums 等于 [1, 1, 1, 1] 。 
数组自身就是等值子数组，长度等于 4 。 
可以证明无法创建更长的等值子数组。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= nums.length
0 <= k <= nums.length

地址

https://leetcode.cn/contest/weekly-contest-359/problems/find-the-longest-equal-subarray/

题意

双指针

思路

题目的关键在于如何删除连续相同元素之间的不同元素，使得连续相同元素的长度最长，首先我们应该枚举相同的元素，这就需要我们对数组进行预处理，将相同元素放到同一个分组里面，其次我们要依次尝试删除 $k$ 次后最多可以使得多少相同的元素连续。
- 此时我们使用双指针 $[l,r]$ ，此时 $l$ 指向相同元素的起点， $r$ 指向相同元素的终点，每次我们将 $r$ 向右移动时，此时统计需要删除的次数为 $tot$, 此时连续的元素的最长长度为 $curr$;
- 每次将 $r$ 向右移动时，此时我们需要增加 $tot$, 当 $tot$ 大于 $k$ 时，此时需要向右移动 $l$,知道 $tot$ 小于等于 $k$ 为止，同时减少 $curr$,此时的长度为 $curr$,
- 依次尝试所有的可能找到最大值为止。
复杂度分析：

时间复杂度：$O(n)$，其中 $n$ 表示数组的长度。
空间复杂度：$O(n)$，其中 $n$ 表示数组的长度。

代码

class Solution {
public:
    int longestEqualSubarray(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, vector<pair<int, int>>> cnt;
        int i = 0;
        while (i < n) {
            int l = i;
            while (i < n && nums[i] == nums[l]) {
                i++;
            }
            cnt[nums[l]].emplace_back(l, i);
        }
        int ans = 0;
        for (auto [x, vec] : cnt) {
            int m = vec.size();
            int tot = k;
            int curr = 0;
            for (int i = 0, j = 0; i < m; i++) {
                curr += vec[i].second - vec[i].first;
                if (i > 0) tot -= vec[i].first - vec[i - 1].second;
                while (tot < 0) {
                    curr -= vec[j].second - vec[j].first;
                    tot += vec[j + 1].first - vec[j].second;
                    j++;
                }
                ans = max(ans, curr);
            }
        }
        return ans;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://whistle-wind.com/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 题解力扣周赛赛

← leetcode weekly contes 359 leetcode weekly contes 360 →

扫描二维码，分享此文章