php网站开发工具,建设职业学校精品网站,网站建设活动方案,房子装修风格大全2021新款作者推荐
视频算法专题
本文涉及知识点
动态规划汇总 数论 区间合并
LeetCode3041. 修改数组后最大化数组中的连续元素数目
给你一个下标从 0 开始只包含 正 整数的数组 nums 。 一开始#xff0c;你可以将数组中 任意数量 元素增加 至多 1 。 修改后#xff0c;你可以从…作者推荐
视频算法专题
本文涉及知识点
动态规划汇总 数论 区间合并
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 105 1 nums[i] 106
数论
先排序。 合并方式一如果[left,r]中的数至少出现1次则可以通过将所有数1从[left,r]转化成[left1,r1]。 合并方式二如果[left,r]中的数至少出现1次且至少一个数x出现两次。则可以将[left,r]转化成[left,r1]。x → \rightarrow →x1,x1 → \rightarrow →x2 ⋯ \cdots ⋯ r → \rightarrow → r1。 如 {1,1,2,3} → \rightarrow → {1,2,3,4} 如果 [l1,r1] 和[l2,r2] 是合法区间r12 l2 方式一合并后变成[l11,r2] 由于缺少l1,合并后无法合并更小的区间。 方式二合并后变成[l1,r2]可以继续合并更小的区间。 合并后的重复数字以[l2,r2]为准[l1,r1]无论有多少个数字多不能变成r12所以不会影响新区间。 我们枚举方式二的开始如果 [l1,r1] 和[l2,r2] 能通过方式二合并则无需枚举[l2,r2]。
代码
核心代码 templateclass 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(vectorint nums) {sort(nums.begin(), nums.end());vectortupleint, 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_mapint, int mEndToLen;for (const auto [left, r, tmp] : vLRTow){mEndToLen[r] r - left 1;}vectortupleint, int, bool vLRTow2;for (int i 0; i vLRTow.size(); ){ vLRTow2.emplace_back(vLRTow[i]);i;for ( ; i vLRTow.size(); i ){if (get2(vLRTow2.back()) (get1(vLRTow2.back()) 2 get0(vLRTow[i]))){get2(vLRTow2.back()) get2(vLRTow[i]);get1(vLRTow2.back()) get1(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()
{vectorint 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);}
}优化代码简洁 templateclass 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(vectorint nums) {sort(nums.begin(), nums.end());vectortupleint, 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 get1(vLRTow[i]) get2(vLRTow[i]);for (; j vLRTow.size(); j){if (get2(vLRTow[j-1]) (get1(vLRTow[j - 1]) 2 get0(vLRTow[j]))){right get1(vLRTow[j]) get2(vLRTow[j]);}else{break;}} int pre ((i 0) (get1(vLRTow[i - 1]) 2 get0(vLRTow[i]))) ? (get1(vLRTow[i - 1]) - get0(vLRTow[i - 1]) 1) : 0;MaxSelf(iRet, right - get0(vLRTow[i])1 pre );i j;}return iRet;}
};动态规划
动态规划的状态
dp[x]表示以x结尾的最长连续数量。
动态规划的初始值
无或者或全部为0。
动态规划的状态方程 { d p [ x 1 ] m a x ( d p [ x 1 ] , d p [ x ] 1 ) x 加一 d p [ x ] m a x ( d p [ x ] , d p [ x − 1 ] 1 ) x 不变 \begin{cases} dp[x1] max(dp[x1],dp[x]1) x加一 \\ dp[x] max(dp[x],dp[x-1]1) x不变\\ \end{cases} {dp[x1]max(dp[x1],dp[x]1)dp[x]max(dp[x],dp[x−1]1)x加一x不变
动态规划的填表顺序
x从小到大。先处理x1再处理x。否则{1}的结果是dp[1]1,dp[2]2。
代码
templateclass ELE
void MaxSelf(ELE* seft, const ELE other)
{*seft max(*seft, other);
}class Solution {
public:int maxSelectedElements(vectorint nums) {sort(nums.begin(), nums.end());unordered_mapint, 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
相关
下载
想高屋建瓴的学习算法请下载《喜缺全书算法册》doc版 https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用**C**实现。
