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] 。
  由于下一次操作的分数与前一次不相等，我们无法继续进行任何操作。

  接口描述

  class Solution {
  public:
      int maxOperations(vector& nums) {
      }
  };

  思路分析

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

  代码详解

  class Solution {
  public:
      int maxOperations(vector& nums) {
          int ret = 0;
          for(int i = 0, t = -1, n = nums.size(); i  
   
   
  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" 。

    接口描述

    　　

    class Solution {
    public:
        string lastNonEmptyString(string s) {
            
        }
    };

    思路分析

    哈希计数+模拟

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

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

    代码详解

    class Solution
    {
    public:
        string lastNonEmptyString(string s)
        {
            int last[26]{0}, n = s.size(), ma = 0;
            unordered_map mp;
            string ret;
            for (int i = 0; i  1)
            {
                string del;
                ma = 0;
                for (auto& p : mp)
                {
                    if (!(--p.second))
                        del.push_back(p.first);
                    else
                        ma = max(ma, p.second);
                }
                for(auto x : del) mp.erase(x);
            }
            for (auto p : mp)
            {
                ret.push_back(p.first);
            }
            sort(ret.begin(), ret.end(), [&](char x, char y){return last[x-'a']  
    　
     
    相同分数的最大操作数目 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 次操作。

      接口描述

      　　

      class Solution
      {
      public:
          int f[2005][2005];
          int maxOperations(vector &nums)
          {
          }
      };

      思路分析

      区间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)

      代码详解

      class Solution
      {
      public:
          int f[2005][2005];
          int maxOperations(vector &nums)
          {
              int ret = 0, n = nums.size();
              for (auto k : {nums[0] + nums[1], nums[n - 1] + nums[n - 2], nums[0] + nums[n - 1]})
              {
                  memset(f, -1, sizeof(f));
                  function dfs = [&](int l, int r)
                  {
                      if (l >= r)
                          return 0;
                      if (~f[l][r])
                          return f[l][r];
                      int res = 0;
                      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);
                      return f[l][r] = res;
                  };
                  ret = max(ret, dfs(0, n - 1));
              }
              return ret;
          }
      };

      　

      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