作者推荐
本文涉及的基础知识点
区间合并
题目
给你一个下标从 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<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; } } 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<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; 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; };
。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙,那算法就是他的是睛|
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境:
VS2022 C++17