备案控制台
探索云世界
开发者社区 开发与运维 文章 正文

区间合并|LeetCode2963:统计好分割方案的数目

2024-01-22 26
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 区间合并|LeetCode2963:统计好分割方案的数目

题目

给你一个下标从 0 开始、由 正整数 组成的数组 nums。

将数组分割成一个或多个 连续 子数组，如果不存在包含了相同数字的两个子数组，则认为是一种 好分割方案 。

返回 nums 的 好分割方案 的 数目。

由于答案可能很大，请返回答案对 109 + 7 取余 的结果。

示例 1：

输入：nums = [1,2,3,4]

输出：8

解释：有 8 种 好分割方案 ：([1], [2], [3], [4]), ([1], [2], [3,4]), ([1], [2,3], [4]), ([1], [2,3,4]), ([1,2], [3], [4]), ([1,2], [3,4]), ([1,2,3], [4]) 和 ([1,2,3,4]) 。

示例 2：

输入：nums = [1,1,1,1]

输出：1

解释：唯一的 好分割方案 是：([1,1,1,1]) 。

示例 3：

输入：nums = [1,2,1,3]

输出：2

解释：有 2 种 好分割方案 ：([1,2,1], [3]) 和 ([1,2,1,3]) 。

参数范围：

1 <= nums.length <= 105

1 <= nums[i] <= 109

区间合并

时间复杂度: O(nlogn)

分析

如果存在两个相同的数，则两者必须在同一个子数组。比如：{1,2,1,3},不能像这样分：

一，{1},{2,1,3}

二，{1,2},{1,3}

假定有数组中x有两个或更多，第一个的索引是xi1，最后一个的索引是xi2。在区间[xi1,xi2)处不能被拆分。

如果y也存在2个或更多，且yi1 > xi1，如果yi1 <= xi2，则两个区间合并成[xi1,max(xi2,yi2)]。

处了区间[xi1,xi2] 的[xi1,xi2)共有(xi2-xi1)位不能分块外，其它都可以拆分。

总共有n-1个位置，可以拆分，扣掉各区间不能拆分的位置，假定有m个位置可以拆分，则结果是2m。

代码

核心代码

template<int MOD = 1000000007>
class C1097Int
{
public:
  C1097Int(long long llData = 0) :m_iData(llData% MOD)
  {
  }
  C1097Int  operator+(const C1097Int& o)const
  {
    return C1097Int(((long long)m_iData + o.m_iData) % MOD);
  }
  C1097Int& operator+=(const C1097Int& o)
  {
    m_iData = ((long long)m_iData + o.m_iData) % MOD;
    return *this;
  }
  C1097Int& operator-=(const C1097Int& o)
  {
    m_iData = (m_iData + MOD - o.m_iData) % MOD;
    return *this;
  }
  C1097Int  operator-(const C1097Int& o)
  {
    return C1097Int((m_iData + MOD - o.m_iData) % MOD);
  }
  C1097Int  operator*(const C1097Int& o)const
  {
    return((long long)m_iData * o.m_iData) % MOD;
  }
  C1097Int& operator*=(const C1097Int& o)
  {
    m_iData = ((long long)m_iData * o.m_iData) % MOD;
    return *this;
  }
  bool operator<(const C1097Int& o)const
  {
    return m_iData < o.m_iData;
  }
  C1097Int pow(long long n)const
  {
    C1097Int iRet = 1, iCur = *this;
    while (n)
    {
      if (n & 1)
      {
        iRet *= iCur;
      }
      iCur *= iCur;
      n >>= 1;
    }
    return iRet;
  }
  C1097Int PowNegative1()const
  {
    return pow(MOD - 2);
  }
  int ToInt()const
  {
    return m_iData;
  }
private:
  int m_iData = 0;;
};
class Solution {
public:
  int numberOfGoodPartitions(vector<int>& nums) {
    m_c = nums.size();
    std::map<int, int> mLeftRight;
    {
      std::unordered_map<int, std::pair<int, int>> mValueToFirstEnd;
      for (int i = 0; i < m_c; i++)
      {
        if (!mValueToFirstEnd.count(nums[i]))
        {
          mValueToFirstEnd[nums[i]] = std::make_pair(i, i);
        }
        else
        {
          mValueToFirstEnd[nums[i]].second = i;
        }
      }
      for (const auto& [tmp, it] : mValueToFirstEnd)
      {
        mLeftRight[it.first] = it.second;
      }
    }
    vector<std::pair<int, int>> vLeftRight;
    for (auto it = mLeftRight.begin(); it != mLeftRight.end(); ++it)
    {
      int iRight = it->second;
      auto ij = std::next(it);
      while ( (mLeftRight.end() != ij) && (ij->first <= iRight))
      {
        iRight = max(iRight, ij->second);
        ij++;
      }
      mLeftRight.erase(std::next(it), ij);
      vLeftRight.emplace_back(it->first, iRight);
    }
    int iCanSplitPos = m_c - 1;
    for (const auto& [left,right] : vLeftRight)
    {
      iCanSplitPos -= right - left;
    }
    return C1097Int<>(2).pow(iCanSplitPos).ToInt();
  }
  int m_c;
};

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    assert(v1[i] == v2[i]);
  }
}
template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
int main()
{
  Solution slu;
  vector<int> nums;
  int k;
  {
    Solution slu;
    nums = { 2, 4, 7, 1, 2 };
    auto res = slu.numberOfGoodPartitions(nums);
    Assert(1, res);
  }
  {
    Solution slu;
    nums = { 1,2,1,3 };
    auto res = slu.numberOfGoodPartitions(nums);
    Assert(2,res );
  }
  {
    Solution slu;
    nums = { 1,1,1,1 };
    auto res = slu.numberOfGoodPartitions(nums);
    Assert(1, res);
  }
}

优化

最后的循环，可以删除。

class Solution {
public:
int numberOfGoodPartitions(vector& nums) {
m_c = nums.size();
std::map mLeftRight;
{
std::unordered_map> mValueToFirstEnd;
for (int i = 0; i < m_c; i++)
{
if (!mValueToFirstEnd.count(nums[i]))
{
mValueToFirstEnd[nums[i]] = std::make_pair(i, i);
}
else
{
mValueToFirstEnd[nums[i]].second = i;
}
}
for (const auto& [tmp, it] : mValueToFirstEnd)
{
mLeftRight[it.first] = it.second;
}
}
int iCanSplitPos = m_c - 1;
for (auto it = mLeftRight.begin(); it != mLeftRight.end(); ++it)
{
int iRight = it->second;
auto ij = std::next(it);
while ( (mLeftRight.end() != ij) && (ij->first <= iRight))
{
iRight = max(iRight, ij->second);
ij++;
}
mLeftRight.erase(std::next(it), ij);
iCanSplitPos -= iRight - it->first;
}
return C1097Int<>(2).pow(iCanSplitPos).ToInt();
}
int m_c;
};

旧代码

template
class C1097Int
{
public:
C1097Int(long long llData = 0) :m_iData(llData% MOD)
{
}
C1097Int  operator+(const C1097Int& o)const
{
  return C1097Int(((long long)m_iData + o.m_iData) % MOD);
}
C1097Int& operator+=(const C1097Int& o)
{
  m_iData = ((long long)m_iData + o.m_iData) % MOD;
  return *this;
}
C1097Int& operator-=(const C1097Int& o)
{
  m_iData = (m_iData + MOD - o.m_iData) % MOD;
  return *this;
}
C1097Int  operator-(const C1097Int& o)
{
  return C1097Int((m_iData + MOD - o.m_iData) % MOD);
}
C1097Int  operator*(const C1097Int& o)const
{
  return((long long)m_iData * o.m_iData) % MOD;
}
C1097Int& operator*=(const C1097Int& o)
{
  m_iData = ((long long)m_iData * o.m_iData) % MOD;
  return *this;
}
bool operator<(const C1097Int& o)const
{
  return m_iData < o.m_iData;
}
C1097Int pow(long long n)const
{
  C1097Int iRet = 1, iCur = *this;
  while (n)
  {
    if (n & 1)
    {
      iRet *= iCur;
    }
    iCur *= iCur;
    n >>= 1;
  }
  return iRet;
}
C1097Int PowNegative1()const
{
  return pow(MOD - 2);
}
int ToInt()const
{
  return m_iData;
}
private:
int m_iData = 0;;
};
class Solution {
public:
int numberOfGoodPartitions(vector& nums) {
m_c = nums.size();
std::map mLeftRight;
{
std::unordered_map> mValueToFirstEnd;
for (int i = 0; i < m_c; i++)
{
if (!mValueToFirstEnd.count(nums[i]))
{
mValueToFirstEnd[nums[i]] = std::make_pair(i, i);
}
else
{
mValueToFirstEnd[nums[i]].second = i;
}
}
for (const auto& [tmp, it] : mValueToFirstEnd)
{
mLeftRight[it.first] = it.second;
}
}
vector> vLeftRight;
vLeftRight.emplace_back(0, 0);
for (auto it = mLeftRight.begin(); it != mLeftRight.end(); ++it)
{
int iRight = it->second;
auto ij = std::next(it);
while ( (mLeftRight.end() != ij) && (ij->first <= iRight))
{
iRight = max(iRight, ij->second);
ij++;
}
mLeftRight.erase(std::next(it), ij);
vLeftRight.emplace_back(it->first, iRight);
}
vLeftRight.emplace_back(m_c-1, m_c-1);
C1097Int<> biRet = 1;
for (int i = 1; i < vLeftRight.size(); i++)
{
C1097Int<> biTmp = 2;
biRet *= biTmp.pow(vLeftRight[i].first - vLeftRight[i - 1].second);
}
return biRet.ToInt();
}
int m_c;
};


扩展阅读

视频课程

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

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

如何你想快

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

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

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653

。也就是我们常说的专业的人做专业的事。 |

|如果程序是一条龙，那算法就是他的是睛|

测试环境

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

或者 操作系统：win10 开发环境：

VS2022 C++17



文章标签：
算法
测试技术
索引
C++
C#
关键词：
LeetCode统计数目
LeetCode数目
LeetCode统计
区间LeetCode
区间LeetCode统计分割
闻缺陷则喜何志丹
目录
相关文章
闻缺陷则喜何志丹
|
3月前
|
算法 测试技术 C#
【二分查找】【区间合并】LeetCode2589:完成所有任务的最少时间
【二分查找】【区间合并】LeetCode2589:完成所有任务的最少时间
闻缺陷则喜何志丹
27 0
程序员三木
|
4天前
[leetcode～数位动态规划] 2719. 统计整数数目 hard
[leetcode～数位动态规划] 2719. 统计整数数目 hard
程序员三木
15 6
肖宜
|
1月前
|
存储
leetcode2744. 最大字符串配对数目
leetcode2744. 最大字符串配对数目
肖宜
17 0
肖宜
|
1月前
leetcode2376. 统计特殊整数
leetcode2376. 统计特殊整数
肖宜
15 1
肖宜
|
1月前
|
Serverless
leetcode2719. 统计整数数目
leetcode2719. 统计整数数目
肖宜
13 0
qiuqiushuibx
|
3月前
代码随想录Day30 贪心05 LeetCode T435无重叠区间 T763划分字母区间 T56 合并区间
代码随想录Day30 贪心05 LeetCode T435无重叠区间 T763划分字母区间 T56 合并区间
qiuqiushuibx
30 0
闻缺陷则喜何志丹
|
3月前
|
算法 测试技术 C#
LeetCode2444: 统计定界子数组的数目
LeetCode2444: 统计定界子数组的数目
闻缺陷则喜何志丹
28 0
闻缺陷则喜何志丹
|
3月前
|
算法 测试技术 C#
【单调栈】【区间合并】LeetCode85:最大矩形
【单调栈】【区间合并】LeetCode85:最大矩形
闻缺陷则喜何志丹
24 0
吹吹晚风
|
1月前
|
机器学习/深度学习 算法
力扣刷题日常（一）
力扣刷题日常（一）
吹吹晚风
20 2
起飞的风筝
|
1月前
|
存储 索引
《LeetCode》—— LeetCode刷题日记
《LeetCode》—— LeetCode刷题日记
起飞的风筝
28 0

热门文章

最新文章

  • 1
    代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结
  • 2
    力扣刷题日常（一）
  • 3
    标准库中的string类（中）+仅仅反转字母+字符串中的第一个唯一字符+字符串相加——“C++”“Leetcode每日一题”
  • 4
    【力扣经典面试题】80. 删除有序数组中的重复项 II
  • 5
    C++和Java中的随机函数你玩明白了吗？内附LeetCode470.rand7()爆改rand10()巨详细题解，带你打败LeetCode%99选手
  • 6
    代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形
  • 7
    【力扣】94. 二叉树的中序遍历、144. 二叉树的前序遍历、145. 二叉树的后序遍历
  • 8
    每日一题：LeetCode-209. 长度最小的子数组（滑动窗口）
  • 9
    【leetcode】剑指 Offer II 105. 岛屿的最大面积-【深度优先DFS】
  • 10
    【力扣经典面试题】121. 买卖股票的最佳时机
  • 1
    《LeetCode》—— 买卖股票的最佳时机
    19
  • 2
    《LeetCode》—— 摆动序列
    24
  • 3
    《LeetCode》—— LeetCode刷题日记
    28
  • 4
    《LeetCode》—— 哈希
    21
  • 5
    《LeetCode》——LeetCode刷题日记3
    19
  • 6
    《LeetCode》——LeetCode刷题日记2
    14
  • 7
    《LeetCode》——LeetCode刷题日记1
    28
  • 8
    《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数
    25
  • 9
    《 LeetCode 热题 HOT 100》——无重复字符的最长子串
    22
  • 10
    《LeetCode 热题 HOT 100》—— 两数相加
    15

    • 相关课程

    更多
  • 【医学搜索Query相关性判断】赛题及baseline解读

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）