网站开发原型工具,网站开发公司 网站空间,在线咨询免费,html5 网站源码作者推荐
【贪心算法】【中位贪心】.执行操作使频率分数最大
涉及知识点
单调栈 动态规划 map
题目
给定一个整数数组 A#xff0c;你可以从某一起始索引出发#xff0c;跳跃一定次数。在你跳跃的过程中#xff0c;第 1、3、5… 次跳跃称为奇数跳跃#xff0c;而第 2、…作者推荐
【贪心算法】【中位贪心】.执行操作使频率分数最大
涉及知识点
单调栈 动态规划 map
题目
给定一个整数数组 A你可以从某一起始索引出发跳跃一定次数。在你跳跃的过程中第 1、3、5… 次跳跃称为奇数跳跃而第 2、4、6… 次跳跃称为偶数跳跃。 你可以按以下方式从索引 i 向后跳转到索引 j其中 i j 在进行奇数跳跃时如第 135… 次跳跃你将会跳到索引 j使得 A[i] A[j]A[j] 是可能的最小值。如果存在多个这样的索引 j你只能跳到满足要求的最小索引 j 上。 在进行偶数跳跃时如第 246… 次跳跃你将会跳到索引 j使得 A[i] A[j]A[j] 是可能的最大值。如果存在多个这样的索引 j你只能跳到满足要求的最小索引 j 上。 对于某些索引 i可能无法进行合乎要求的跳跃。 如果从某一索引开始跳跃一定次数可能是 0 次或多次就可以到达数组的末尾索引 A.length - 1那么该索引就会被认为是好的起始索引。 返回好的起始索引的数量。 示例 1 输入[10,13,12,14,15] 输出2 解释 从起始索引 i 0 出发我们可以跳到 i 2因为 A[2] 是 A[1]A[2]A[3]A[4] 中大于或等于 A[0] 的最小值然后我们就无法继续跳下去了。 从起始索引 i 1 和 i 2 出发我们可以跳到 i 3然后我们就无法继续跳下去了。 从起始索引 i 3 出发我们可以跳到 i 4到达数组末尾。 从起始索引 i 4 出发我们已经到达数组末尾。 总之我们可以从 2 个不同的起始索引i 3, i 4出发通过一定数量的跳跃到达数组末尾。 示例 2 输入[2,3,1,1,4] 输出3 解释 从起始索引 i0 出发我们依次可以跳到 i 1i 2i 3 在我们的第一次跳跃奇数中我们先跳到 i 1因为 A[1] 是A[1]A[2]A[3]A[4]中大于或等于 A[0] 的最小值。 在我们的第二次跳跃偶数中我们从 i 1 跳到 i 2因为 A[2] 是A[2]A[3]A[4]中小于或等于 A[1] 的最大值。A[3] 也是最大的值但 2 是一个较小的索引所以我们只能跳到 i 2而不能跳到 i 3。 在我们的第三次跳跃奇数中我们从 i 2 跳到 i 3因为 A[3] 是A[3]A[4]中大于或等于 A[2] 的最小值。 我们不能从 i 3 跳到 i 4所以起始索引 i 0 不是好的起始索引。 类似地我们可以推断 从起始索引 i 1 出发 我们跳到 i 4这样我们就到达数组末尾。 从起始索引 i 2 出发 我们跳到 i 3然后我们就不能再跳了。 从起始索引 i 3 出发 我们跳到 i 4这样我们就到达数组末尾。 从起始索引 i 4 出发我们已经到达数组末尾。 总之我们可以从 3 个不同的起始索引i 1, i 3, i 4出发通过一定数量的跳跃到达数组末尾。 示例 3 输入[5,1,3,4,2] 输出3 解释 我们可以从起始索引 124 出发到达数组末尾。 提示 1 A.length 20000 0 A[i] 100000
代码
单调栈
此方法比map巧妙性能差不多值得学习。时间复杂度O(nlogn)。
变量函数解析
indexs计算奇数跳时arr[index[i]] 升序且相等的元素相对顺序不变。计算偶数跳时arr[index[i]] 降序且相等的元素相对顺序不变。Next计算奇偶数跳的下一个位置如果无法跳则值为m_cvStatus记录偶数奇数跳能否跳到队尾。vStatus[0][m_c]和vStatus[0][m_c]为false避免处理边界条件
Next奇数跳为例
令jindex[jj],按jj从小到的顺序将j入栈由于arr[index[jj]]是升序所以规则一arr[栈中元素] arr[j]。 (sta.top() j 成立说明 规则二j在sta.top()右边。 规则三令index[jj2] 为sta.top(),arr[index(jj2,j)]中的数即大于等于arr[sta.top()] 同时小于等于arr[j]的数全部在sta.top()的左边否则出栈了。 结合规则一二三stat.top()的下一步就是j。
核心代码
class Solution {
public:int oddEvenJumps(vectorint arr) {m_c arr.size();vectorint indexs(m_c);iota(indexs.begin(), indexs.end(), 0);sort(indexs.begin(), indexs.end(), [](const int i1, const int i2) {return (arr[i1] arr[i2]) || ((arr[i1] arr[i2]) (i1 i2)); });const auto v1 Next(indexs);sort(indexs.begin(), indexs.end(), [](const int i1, const int i2) {return (arr[i1] arr[i2]) || ((arr[i1] arr[i2]) (i1 i2)); });const auto v2 Next(indexs);vectorvectorbool vStatus(2, vectorbool(m_c1));int iRet 1;vStatus[0][m_c-1] true;vStatus[1][m_c - 1] true;for (int i m_c - 1 - 1; i 0; i--){vStatus[0][i] vStatus[1][v2[i]];//偶数跳vStatus[1][i] vStatus[0][v1[i]];//奇数跳iRet (int)vStatus[1][i];}return iRet;}vectorint Next(const vectorint indexs){vectorint vNext(indexs.size(), indexs.size());stackint sta;for (int j : indexs){while (sta.size() (sta.top() j)){vNext[sta.top()] j;sta.pop();}sta.emplace(j);}return vNext;}int m_c;
};测试用例
templateclass T
void Assert(const T t1, const T t2)
{assert(t1 t2);
}templateclass T
void Assert(const vectorT v1, const vectorT v2)
{if (v1.size() ! v2.size()){assert(false);return;}for (int i 0; i v1.size(); i){Assert(v1[i], v2[i]);}
}int main()
{vectorint arr;{Solution slu;arr { 10,13,12,14,15 };auto res slu.oddEvenJumps(arr);Assert(2, res);}{Solution slu;arr { 2,3,1,1,4 };auto res slu.oddEvenJumps(arr);Assert(3, res);}{Solution slu;arr { 5,1,3,4,2 };auto res slu.oddEvenJumps(arr);Assert(3, res);}//CConsole::Out(res);
}2023年3月版map
利用map性能和单调栈差不多好理解。从后向前遍历各元素map的键对应arr[i]map的值对应i。如果arr[i]i小的后加入的覆盖前面的。 时间复杂度O(nlogn)。
map
map可以分成有序(单调)map和无序(哈希)map。还可分成单键map和多键map允许重复的键。 class Solution {public:int oddEvenJumps(vectorint arr) {vectorvectorbool result;result.assign(arr.size(), vectorbool(2));result[arr.size() - 1][0] true;result[arr.size() - 1][1] true;std::mapint, int mValueIndex;mValueIndex[arr.back()] arr.size()-1;for (int i arr.size() - 2; i 0; i--){{//奇数跳跃auto it mValueIndex.lower_bound(arr[i]);if (mValueIndex.end() ! it){result[i][0] result[it-second][1];}}{//偶数跳跃auto it2 mValueIndex.upper_bound(arr[i]);if (mValueIndex.begin() ! it2){--it2;result[i][1] result[it2-second][0];}mValueIndex[arr[i]] i;}}int iNum 0;for (int i 0; i arr.size(); i){if (result[i][0]){iNum;}}return iNum;}};扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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 实现。
