devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode第 124 场双周赛个人题解

作者：繁依Fanyi0 | 2024-02-20 22:19:18

赞

踩

LeetCode第 124 场双周赛个人题解

目录

相同分数的最大操作数目 I

原题链接

题目描述

接口描述

思路分析

代码详解

3039. 进行操作使字符串为空

原题链接

题目描述

接口描述

思路分析

代码详解

相同分数的最大操作数目 II

原题链接

题目描述

接口描述

思路分析

代码详解

100205. 修改数组后最大化数组中的连续元素数目

原题链接

题目描述

接口描述

思路分析

代码详解

相同分数的最大操作数目 I

原题链接

相同分数的最大操作数目 I - 力扣 (LeetCode) 竞赛

题目描述

给你一个整数数组 nums ，如果 nums 至少 包含 2 个元素，你可以执行以下操作：

  • 选择 nums 中的前两个元素并将它们删除。

一次操作的 分数 是被删除元素的和。

在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。

请你返回按照上述要求 最多 可以进行的操作次数。

示例 1：

输入：nums = [3,2,1,4,5]
输出：2
解释：我们执行以下操作：
- 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,4,5] 。
- 删除前两个元素，分数为 1 + 4 = 5 ，nums = [5] 。
由于只剩下 1 个元素，我们无法继续进行任何操作。

示例 2：

输入：nums = [3,2,6,1,4]
输出：1
解释：我们执行以下操作：
- 删除前两个元素，分数为 3 + 2 = 5 ，nums = [6,1,4] 。
由于下一次操作的分数与前一次不相等，我们无法继续进行任何操作。

接口描述

  1. class Solution {
  2. public:
  3.     int maxOperations(vector<int>& nums) {
  4.  
  5.     }
  6. };

思路分析

直接模拟即可，时间复杂度O(N)

代码详解

  1. class Solution {
  2. public:
  3.     int maxOperations(vector<int>& nums) {
  4.         int ret = 0;
  5.         for(int i = 0, t = -1, n = nums.size(); i < n - 1; i += 2){
  6.             if(~t && nums[i] + nums[i + 1] != t) return ret;
  7.             ret++, t = nums[i] + nums[i + 1];
  8.         }
  9.         return ret;
  10.     }
  11. };

3039. 进行操作使字符串为空

原题链接

3039. 进行操作使字符串为空

　　

题目描述

　　

给你一个字符串 s 。

请你进行以下操作直到 s 为 空 ：

  • 每次操作 依次 遍历 'a' 到 'z'，如果当前字符出现在 s 中，那么删除出现位置 最早 的该字符。

请你返回进行 最后 一次操作 之前 的字符串 s 。

示例 1：

输入：s = "aabcbbca"
输出："ba"
解释：我们进行以下操作：
- 删除 s = "aabcbbca" 中加粗加斜字符，得到字符串 s = "abbca" 。
- 删除 s = "abbca" 中加粗加斜字符，得到字符串 s = "ba" 。
- 删除 s = "ba" 中加粗加斜字符，得到字符串 s = "" 。
进行最后一次操作之前的字符串为 "ba" 。

示例 2：

输入：s = "abcd"
输出："abcd"
解释：我们进行以下操作：
- 删除 s = "abcd" 中加粗加斜字符，得到字符串 s = "" 。
进行最后一次操作之前的字符串为 "abcd" 。

接口描述

　　

  1. class Solution {
  2. public:
  3.     string lastNonEmptyString(string s) {
  4.         
  5.     }
  6. };

思路分析

哈希计数+模拟

统计字符集的数目，然后每轮对剩余字符减一，当最大字符数目为1时，我们break，此时剩余的字符就是要返回的字符，其顺序和在s中最后出现位置的相对顺序相同

时间复杂度O(N)，空间复杂度O(U)，U为字符集大小

代码详解

  1. class Solution
  2. {
  3. public:
  4.     string lastNonEmptyString(string s)
  5.     {
  6.         int last[26]{0}, n = s.size(), ma = 0;
  7.         unordered_map<char, int> mp;
  8.         string ret;
  9.         for (int i = 0; i < n; i++)
  10.             last[s[i] - 'a'] = i, mp[s[i]]++;
  11.         for (auto p : mp)
  12.             ma = max(ma, p.second);
  13.         while (mp.size() && ma > 1)
  14.         {
  15.             string del;
  16.             ma = 0;
  17.             for (auto& p : mp)
  18.             {
  19.                 if (!(--p.second))
  20.                     del.push_back(p.first);
  21.                 else
  22.                     ma = max(ma, p.second);
  23.             }
  24.             for(auto x : del) mp.erase(x);
  25.         }
  26.         for (auto p : mp)
  27.         {
  28.             ret.push_back(p.first);
  29.         }
  30.         sort(ret.begin(), ret.end(), [&](char x, char y){return last[x-'a'] < last[y-'a'];});
  31.         return ret;
  32.     }
  33. };

　

相同分数的最大操作数目 II

原题链接

　　相同分数的最大操作数目 II - 力扣 (LeetCode) 竞赛

题目描述

　　

给你一个整数数组 nums ，如果 nums 至少 包含 2 个元素，你可以执行以下操作中的 任意 一个：

  • 选择 nums 中最前面两个元素并且删除它们。
  • 选择 nums 中最后两个元素并且删除它们。
  • 选择 nums 中第一个和最后一个元素并且删除它们。

一次操作的 分数 是被删除元素的和。

在确保 所有操作分数相同 的前提下，请你求出 最多 能进行多少次操作。

请你返回按照上述要求 最多 可以进行的操作次数。

示例 1：

输入：nums = [3,2,1,2,3,4]
输出：3
解释：我们执行以下操作：
- 删除前两个元素，分数为 3 + 2 = 5 ，nums = [1,2,3,4] 。
- 删除第一个元素和最后一个元素，分数为 1 + 4 = 5 ，nums = [2,3] 。
- 删除第一个元素和最后一个元素，分数为 2 + 3 = 5 ，nums = [] 。
由于 nums 为空，我们无法继续进行任何操作。

示例 2：

输入：nums = [3,2,6,1,4]
输出：2
解释：我们执行以下操作：
- 删除前两个元素，分数为 3 + 2 = 5 ，nums = [6,1,4] 。
- 删除最后两个元素，分数为 1 + 4 = 5 ，nums = [6] 。
至多进行 2 次操作。

接口描述

　　

  1. class Solution
  2. {
  3. public:
  4.     int f[2005][2005];
  5.  
  6.     int maxOperations(vector<int> &nums)
  7.     {
  8.     }
  9. };

思路分析

区间DP

从数据范围上看应该用O(N^2)的算法，而题目所给操作都是在数组边界上进行，则很容易想到区间dp

首先要明白最大操作次数对应的每次操作的元素和k只有三种情况：nums[0] + nums[1], nums[n - 1] + nums[n - 2], nums[0] + nums[n - 1]

定义状态f[l][r]为最大操作次数对应的每次操作的元素和为k时的最大操作次数

那么转移方程有三，分别对应三种操作：

                if (nums[l] + nums[l + 1] == k)
                    res = max(res, dfs(l + 2, r) + 1);
                if (nums[l] + nums[r] == k)
                    res = max(res, dfs(l + 1, r - 1) + 1);
                if (nums[r - 1] + nums[r] == k)
                    res = max(res, dfs(l, r - 2) + 1);

我们进行三次区间DP即可

时间复杂度O(N^2)，空间复杂度O(N^2)

代码详解

  1. class Solution
  2. {
  3. public:
  4.     int f[2005][2005];
  5.  
  6.     int maxOperations(vector<int> &nums)
  7.     {
  8.         int ret = 0, n = nums.size();
  9.         for (auto k : {nums[0] + nums[1], nums[n - 1] + nums[n - 2], nums[0] + nums[n - 1]})
  10.         {
  11.             memset(f, -1, sizeof(f));
  12.             function<int(int, int)> dfs = [&](int l, int r)
  13.             {
  14.                 if (l >= r)
  15.                     return 0;
  16.                 if (~f[l][r])
  17.                     return f[l][r];
  18.                 int res = 0;
  19.                 if (nums[l] + nums[l + 1] == k)
  20.                     res = max(res, dfs(l + 2, r) + 1);
  21.                 if (nums[l] + nums[r] == k)
  22.                     res = max(res, dfs(l + 1, r - 1) + 1);
  23.                 if (nums[r - 1] + nums[r] == k)
  24.                     res = max(res, dfs(l, r - 2) + 1);
  25.                 return f[l][r] = res;
  26.             };
  27.             ret = max(ret, dfs(0, n - 1));
  28.         }
  29.         return ret;
  30.     }
  31. };

　

100205. 修改数组后最大化数组中的连续元素数目

　　

原题链接

　　修改数组后最大化数组中的连续元素数目 - 力扣 (LeetCode) 竞赛

题目描述

　　

给你一个下标从 0 开始只包含 正 整数的数组 nums 。

一开始，你可以将数组中 任意数量 元素增加 至多 1 。

修改后，你可以从最终数组中选择 一个或者更多 元素，并确保这些元素升序排序后是 连续 的。比方说，[3, 4, 5] 是连续的，但是 [3, 4, 6] 和 [1, 1, 2, 3] 不是连续的。

请你返回 最多 可以选出的元素数目。

示例 1：

输入：nums = [2,1,5,1,1]
输出：3
解释：我们将下标 0 和 3 处的元素增加 1 ，得到结果数组 nums = [3,1,5,2,1] 。
我们选择元素 [3,1,5,2,1] 并将它们排序得到 [1,2,3] ，是连续元素。
最多可以得到 3 个连续元素。

示例 2：

输入：nums = [1,4,7,10]
输出：1
解释：我们可以选择的最多元素数目是 1 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 106

接口描述

　　

  1. class Solution
  2. {
  3. public:
  4.     int maxSelectedElements(vector<int> &nums)
  5.     {
  6.  
  7.     }
  8. };

思路分析

最长连续子序列变形

如果给你一个序列，求最长连续子序列，那么一次遍历就能得到

那么现在给你一个乱序的nums，并且允许你将某些数字加1，让你求最长连续子序列，又该如何呢？

首先我们将nums升序排序，然后注意到数组长度范围1e5而数据范围只有1e6，这是本题的关键

那么我们可以统计记录nums的最小值l和最大值r，然后记录每个数字出现次数cnt[x]

对于cnt[x]>1的数字，我们直接拿出一个变成x+1，因为这样只会让连续序列更长（注意维护r，因为这一点导致我没有AC，有几个样例没过QAQ）

然后我们一次遍历得到最长连续子序列即可，不过有所不同，我们注意到有一些cnt[x]=1的数字+1也是有可能让最长连续子序列变长的，所以求解步骤如下：

  • 枚举i，从l遍历到r，当前最长连续子序列长度为s，s的最长可操作后缀长度为pre
  • 如果i存在，那么s++，否则s = pre，pre=0（因为当前序列断了，我们把前面能右移的后缀拿过来）
  • 如果i在nums中存在并且未进行+1操作，那么pre++，否则pre=0
  • 维护ret即可

时间复杂度O(nlogn)，空间复杂度O(n)

代码详解

  1. class Solution
  2. {
  3. public:
  4.     int cnt[1000005];
  5.     int maxSelectedElements(vector<int> &nums)
  6.     {
  7.         memset(cnt, 0, sizeof cnt);
  8.         bitset<1000005> vis;
  9.         unordered_set<int> mp(nums.begin(), nums.end());
  10.         sort(nums.begin(), nums.end());
  11.         int l = nums[0], r = nums.back(), ret = 1;
  12.         for (auto x : nums)
  13.             cnt[x]++;
  14.         for (auto x : nums)
  15.             if (cnt[x] > 1)
  16.                 cnt[x + 1]++, cnt[x]--, vis[x] = 1, r = max(r , x + 1);
  17.         for (int i = l, pre = 0, s = 0; i <= r; i++)
  18.         {
  19.             if(cnt[i])  s++;
  20.             else{
  21.                 s = pre, pre = 0;continue;}
  22.             if (mp.count(i) && !vis[i])    pre++;
  23.             else    pre = 0;
  24.             ret = max(ret , s);
  25.         }
  26.         return ret;
  27.     }
  28. };

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/121028
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号