【动态规划】【数论】【区间合并】3041. 修改数组后最大化数组中的连续元素数目-阿里云开发者社区

【动态规划】【数论】【区间合并】3041. 修改数组后最大化数组中的连续元素数目

2024-04-10 30

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【动态规划】【数论】【区间合并】3041. 修改数组后最大化数组中的连续元素数目

本文涉及知识点

动态规划汇总

数论区间合并

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

给你一个下标从 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 <= 10⁵

1 <= nums[i] <= 10⁶

数论

先排序。

合并方式一：如果[left,r]中的数至少出现1次，则可以通过将所有数+1，从[left,r]转化成[left+1,r+1]。

合并方式二：如果[left,r]中的数至少出现1次，且至少一个数x出现两次。则可以将[left,r]转化成[left,r+1]。x→ \rightarrow→x+1,x+1→ \rightarrow→x+2 ⋯ \cdots⋯ r → \rightarrow→ r+1。如： {1,1,2,3} → \rightarrow→ {1,2,3,4}

如果 [l1,r1] 和[l2,r2] 是合法区间，r1+2= l2

方式一合并后，变成[l1+1,r2] ，由于缺少l1,合并后无法合并更小的区间。

方式二合并后，变成[l1,r2]，可以继续合并更小的区间。

合并后的重复数字以[l2,r2]为准，[l1,r1]无论有多少个数字多不能变成r1+2，所以不会影响新区间。

我们枚举方式二的开始，如果 [l1,r1] 和[l2,r2] 能通过方式二合并，则无需枚举[l2,r2]。

代码

核心代码

template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
  *seft = max(*seft, other);
}
#define MacEnumMask(mask,maskMax) for (int mask = maskMax; mask; mask = (mask - 1) & maskMax) 
class Solution {
public:
  int maxSelectedElements(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<tuple<int, int, bool>> vLRTow;
    int left = 0;
    bool bRepeat = false;
    for (int i = 1; i < nums.size(); i++)
    {
      if (nums[i] == nums[i - 1])
      {
        bRepeat = true;
      }
      else if (nums[i] != nums[i - 1] + 1)
      {
        vLRTow.emplace_back(nums[left], nums[i - 1], bRepeat);
        left = i;
        bRepeat = false;
      }
    }
    vLRTow.emplace_back(nums[left], nums.back(), bRepeat);
    std::unordered_map<int, int> mEndToLen;
    for (const auto& [left, r, tmp] : vLRTow)
    {
      mEndToLen[r] = r - left + 1;
    }
    vector<tuple<int, int, bool>> vLRTow2;
    for (int i = 0; i  < vLRTow.size(); )
    {   
      vLRTow2.emplace_back(vLRTow[i]);
      i++;
      for ( ; i < vLRTow.size(); i ++)
      {
        if (get<2>(vLRTow2.back()) && (get<1>(vLRTow2.back()) + 2 == get<0>(vLRTow[i])))
        {
          get<2>(vLRTow2.back()) = get<2>(vLRTow[i]);
          get<1>(vLRTow2.back()) = get<1>(vLRTow[i]);
        }
        else
        {
          break;
        }
      }     
    }   
    int iRet = 0;
    for (int i = 0 ; i < vLRTow2.size();i++)
    {
      const auto& [left, r, bReapt] = vLRTow2[i];
      int pre = mEndToLen.count(left-2 )? mEndToLen[left-2] :0;
      MaxSelf(&iRet, pre + r - left + 1 + bReapt);
    }
    return iRet;
  }
};

测试用例

int main()
{
  vector<int> nums;
  
  {
    Solution sln;
    nums = { 16,1,6,14,5,10,16,3,3,7,12,18,6,11,10,10,9,16 };
    auto res = sln.maxSelectedElements(nums);
    Assert(13, res);
  }
  {
    Solution sln;
    nums = { 9, 8, 8, 5, 15, 9, 12, 5, 1, 3, 7, 18, 10 };
    auto res = sln.maxSelectedElements(nums);
    Assert(9, res);
  }
  {
    Solution sln;
    nums = { 8,13,18,10,16,19,11,17,15,18,9,12,15,8,9,14,7 };
    auto res = sln.maxSelectedElements(nums);
    Assert(14, res);
  }
  {
    Solution sln;
    nums = { 12, 11, 8, 7, 2, 10, 18, 12 };
    auto res = sln.maxSelectedElements(nums);
    Assert(6, res);
  }
  {
    Solution sln;
    nums = { 8,10,6,12,9,12,2,3,13,19,11,18,10,16 };
    auto res = sln.maxSelectedElements(nums);
    Assert(8, res);
  }
  
  {
    Solution sln;
    nums = { 2,1,4,1,1 };
    auto res = sln.maxSelectedElements(nums);
    Assert(4, res);
  }
  {
    Solution sln;
    nums = { 2,1,5,1,1 };
    auto res = sln.maxSelectedElements(nums);
    Assert(3, res);
  } 
}

优化代码：简洁

template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
  *seft = max(*seft, other);
}
#define MacEnumMask(mask,maskMax) for (int mask = maskMax; mask; mask = (mask - 1) & maskMax) 
class Solution {
public:
  int maxSelectedElements(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<tuple<int, int, bool>> vLRTow;
    int left = 0;
    bool bRepeat = false;
    for (int i = 1; i < nums.size(); i++)
    {
      if (nums[i] == nums[i - 1])
      {
        bRepeat = true;
      }
      else if (nums[i] != nums[i - 1] + 1)
      {
        vLRTow.emplace_back(nums[left], nums[i - 1], bRepeat);
        left = i;
        bRepeat = false;
      }
    }
    vLRTow.emplace_back(nums[left], nums.back(), bRepeat);
    int iRet = 0;
    for (int i = 0; i < vLRTow.size(); )
    { 
      int j = i + 1;
      int right = get<1>(vLRTow[i]) + get<2>(vLRTow[i]);
      for (; j < vLRTow.size(); j++)
      {
        if (get<2>(vLRTow[j-1]) && (get<1>(vLRTow[j - 1]) + 2 == get<0>(vLRTow[j])))
        {
          right = get<1>(vLRTow[j]) + get<2>(vLRTow[j]);
        }
        else
        {
          break;
        }
      }     
      int pre = ((i > 0) && (get<1>(vLRTow[i - 1]) + 2 == get<0>(vLRTow[i]))) ? (get<1>(vLRTow[i - 1]) - get<0>(vLRTow[i - 1]) + 1) : 0;
      MaxSelf(&iRet, right - get<0>(vLRTow[i])+1 + pre );
      i = j;
    }
    return iRet;
  }
};

动态规划

动态规划的状态

dp[x]表示以x结尾的最长连续数量。

动态规划的初始值

无，或者或全部为0。

动态规划的状态方程

动态规划的填表顺序

x从小到大。先处理x+1，再处理x。否则{1}的结果是dp[1]=1,dp[2]=2。

代码

template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
  *seft = max(*seft, other);
}
class Solution {
public:
  int maxSelectedElements(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    unordered_map<int, int> dp;
    for (const auto& n : nums)
    {
      MaxSelf(&dp[n + 1], dp[n] + 1);
      MaxSelf(&dp[n ], dp[n - 1] + 1);
    }
    int iRet = 0;
    for (const auto& [tmp, len] : dp)
    {
      MaxSelf(&iRet, len);
    }
    return iRet;
  }
};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。

https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程

https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17

或者操作系统：win10 开发环境： VS2022 C++17

如无特殊说明，本算法用**C++**实现。