Leetcode 第 359 场周赛题解
Leetcode 第 359 场周赛题解
- Leetcode 第 359 场周赛题解
- 题目1：2828. 判别首字母缩略词
- 思路
- 代码
- 复杂度分析
- 题目2：2829. k-avoiding 数组的最小总和
- 思路
- 代码
- 复杂度分析
- 题目3：2830. 销售利润最大化
- 思路
- 代码
- 复杂度分析
- 题目4：2831. 找出最长等值子数组
- 思路
- 代码
- 复杂度分析
Leetcode 第 359 场周赛题解
题目1：2828. 判别首字母缩略词
思路
遍历，判断。
代码
class Solution
{
public:
bool isAcronym(vector<string> &words, string s)
{
int n = words.size(), len = s.size();
if (n != len)
return false;
for (int i = 0; i < n; i++)
{
if (words[i].front() != s[i])
return false;
}
return true;
}
};
复杂度分析
时间复杂度：O(n)，其中 n 是字符串 s 的长度。
空间复杂度：O(1)。
题目2：2829. k-avoiding 数组的最小总和
思路
从 1 枚举开始数组元素 x， 用一个哈希表存储数组元素，有两种情况：
- k-x 在哈希表中：为保证不存在任何求和等于 k 的不同元素对，跳过 x。
- k-x 不在哈希表中：将 x 插入哈希表
当哈希表里有 n 个元素时，返回其中的元素和。
代码
class Solution
{
public:
int minimumSum(int n, int k)
{
unordered_set<int> visited;
int sum = 0;
for (int x = 1; x <= 2 * n; x++)
{
if (!visited.count(k - x))
{
sum += x;
visited.insert(x);
if (visited.size() == n)
break;
}
}
return sum;
}
};
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)。
题目3：2830. 销售利润最大化
思路
定义 dp[i+1] 表示销售编号不超过 i 的房屋的最大盈利。
考虑编号为 i 的房屋卖或不卖：
- 不卖，有 dp[i+1]=dp[i]。
- 卖，那么遍历所有 endj=i 的购买请求，有 dp[i+1]=max(dp[startj]+goldj)。
两种情况取最大值。
初始值 dp[0]=0。
最终答案为 dp[n]。
代码
/*
* @lc app=leetcode.cn id=2830 lang=cpp
*
* [2830] 销售利润最大化
*/
// @lc code=start
class Solution
{
public:
int maximizeTheProfit(int n, vector<vector<int>> &offers)
{
int m = offers.size();
// 对购买请求按照 end 值从小到大排序
sort(offers.begin(), offers.end(), [](vector<int> &o1, vector<int> &o2)
{ return o1[1] < o2[1]; });
// dp[i + 1] 表示从前往后卖到编号为 i 的房子时，总的最大获利
vector<int> dp(n + 1, 0);
int index = 0;
// 状态转移
for (int i = 0; i < n; i++)
{
// 不卖编号为 i 的房子
dp[i + 1] = dp[i];
// 卖编号为 i 的房子，选获利最多的方案
while (index < m && i == offers[index][1])
{
dp[i + 1] = max(dp[i + 1], offers[index][2] + dp[offers[index][0]]);
index++;
}
}
return dp[n];
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n+m)，其中 m 为数组 offers 的长度。
空间复杂度：O(n+m)，其中 m 为数组 offers 的长度。
题目4：2831. 找出最长等值子数组
思路
题目要求找到数组中删除最多 k 个元素后最长等值子数组的长度，所谓最长等值子数组即数组种连续相同元素的最长长度。假设可以找到数组中每个不同元素构成的的最长等值子数组，即可找到全局的最大值。首先我们需要对数组中的元素进行分类，然后依次枚举求出每个不同元素构成的最长等值子数组长度。
首先分析一个简单问题，假定给定区间 [l,r]，此时元素 x 在区间出现的次数为 cnt[x]，则该区间中以要构造以 x 为等值子数组需要删除的元素个数即为 r−l+1−cnt[x]，如果此时 r−l+1−cnt[x]≤k，则可以构成一个符合题意的等值子数组。
我们不必枚举所有的区间，可以利用滑动窗口的思路，只需枚举区间的右端点 ai，当区间 [aj, ai] 需要删除的元素大于 k 时我们再移动 ai，直到区间需要删除的元素小于等于 k，即此时满足 ai-aj−(i−j)≤k 即可。找到所有合法等值子数组的长度，返回最大值即可。
代码
/*
* @lc app=leetcode.cn id=2831 lang=cpp
*
* [2831] 找出最长等值子数组
*/
// @lc code=start
class Solution
{
public:
int longestEqualSubarray(vector<int> &nums, int k)
{
int n = nums.size();
unordered_map<int, vector<int>> posList;
for (int i = 0; i < n; i++)
posList[nums[i]].push_back(i);
int ans = INT_MIN;
for (auto &[_, pos] : posList)
{
int left = 0;
for (int right = 0; right < pos.size(); right++)
{
// subLen 是子数组的长度
int subLen = pos[right] - pos[left] + 1;
// count 是等值元素的个数
int count = right - left + 1;
while (subLen - count > k)
{
left++;
subLen = pos[right] - pos[left] + 1;
count = right - left + 1;
}
ans = max(ans, count);
}
}
return ans;
}
};
// @lc code=end
复杂度分析
时间复杂度：O(n)，其中 n 表示数组 nums 的长度。分组需要的时间复杂度为 O(n)，通过滑动窗口找到每种元素的最大长度只需遍历所有的连续相等字符的长度计数即可，最多有 n 个连续字符串的长度计数，因此总的时间复杂度为 O(n)。
空间复杂度：O(n)，其中 n 表示数组 nums 的长度。分组保存每种元素的索引序列需要的空间为 O(n)。