软件开发网站开发学习,wordpress手机号码登录,深圳专业制作网站技术,网站建设工程属于科技档案吗贪心算法的详细逻辑这个问题的最优解可以用 贪心算法 在 O(N) 时间 内解决。它的核心思想是#xff1a;每次操作尽可能覆盖最长的连续非零区间#xff0c;并通过数学分析发现#xff1a;最小操作次数等于所有“上升台阶”的高度差之和。1. 直观理解假设 steps [1, 2, 3, 2,…贪心算法的详细逻辑这个问题的最优解可以用 贪心算法 在 O(N) 时间 内解决。它的核心思想是
每次操作尽可能覆盖最长的连续非零区间并通过数学分析发现最小操作次数等于所有“上升台阶”的高度差之和。1. 直观理解假设 steps [1, 2, 3, 2, 1]我们可以这样操作第一次操作覆盖整个数组 [1,2,3,2,1] → [0,1,2,1,0]操作次数 1第二次操作覆盖 [1,2,1] → [0,0,1,0,0]操作次数 1第三次操作覆盖 [1] → [0,0,0,0,0]操作次数 1总操作次数 3正好等于 1 (初始) (2-1) (3-2) 3。
2. 贪心策略的数学证明关键观察如果当前数字 steps[i] 比前一个数字 steps[i-1] 大说明需要 新增 steps[i] - steps[i-1] 次操作。如果 steps[i] steps[i-1]说明它可以被之前的操作覆盖无需新增操作次数。数学表达text
总操作次数 steps[0] Σ max(steps[i] - steps[i-1], 0) (i 1 to N-1)
3. 代码实现cpp
#include vector
#include iostream
using namespace std;int GetMinStep(const vectorint steps) {if (steps.empty()) return 0;int res steps[0]; // 初始必须有 steps[0] 次操作for (int i 1; i steps.size(); i) {if (steps[i] steps[i-1]) {res steps[i] - steps[i-1]; // 增加新的操作}}return res;
}int main() {vectorint steps1 {1, 2, 3, 2, 1};cout GetMinStep(steps1) endl; // 输出 3vectorint steps2 {3, 2, 1, 2, 3};cout GetMinStep(steps2) endl; // 输出 5vectorint steps3 {4, 1, 2, 3, 1};cout GetMinStep(steps3) endl; // 输出 6 (4 0 1 1 0)return 0;
}
4. 为什么贪心算法是正确的反证法假设贪心算法不是最优的那么存在某个 steps[i] 没有被正确覆盖情况 1steps[i] steps[i-1]如果少操作会导致 steps[i] 无法归零矛盾。情况 2steps[i] steps[i-1]它已经被之前的操作覆盖无需额外操作。因此贪心策略的正确性得证。
5. 对比原始模拟方法方法时间复杂度适用场景原始模拟每次找最长区间减1O(N²)直观但较慢贪心算法数学优化O(N)最优解
6. 实际应用示例示例 1steps [3, 2, 1, 2, 3]计算过程res 3初始i1: 2 3 → 不增加i2: 1 2 → 不增加i3: 2 1 → res 1 → res4i4: 3 2 → res 1 → res5总操作次数 5示例 2steps [4, 1, 2, 3, 1]计算过程res 4初始i1: 1 4 → 不增加i2: 2 1 → res 1 → res5i3: 3 2 → res 1 → res6i4: 1 3 → 不增加总操作次数 6
7. 总结贪心策略利用高度差直接计算最小操作次数。优势O(N) 时间无需模拟每次操作。适用场景题目允许数学分析时优先使用贪心算法。这种方法高效且优雅能完美解决问题
资源
#include iostream
#include vector
#include climits
#include queue
#include list
#include unordered_set
using namespace std;
void PrintList(listpairint,int lists)
{for(auto l:lists){coutl.first l.second ;}coutendl;
}int Solution(const int frameNum, const int windowSize, const vectorint pages)
{int ret 0;// 记录访问次数访问时间// 51 1 52 1 53 1// 52 1 53 1 54 1// 要么遍历一遍时间要么遍历一遍page要么加空间// 链表比较合适listpairint,int pagesList;for(auto page:pages){auto it pagesList.begin();bool flagFind false;while(it!pagesList.end()){if(it-first page){flagFind true;it-second;break;}it;}if(flagFind false){if(pagesList.size()frameNum){pagesList.push_back(make_pair(page,1));}else // 触发置换{//从头节点开始取windowSize个//遍历得到最小值auto left pagesList.begin();int nums windowSize;int minof INT_MAX;while (nums0){minof min(minof,left-second);left;nums--;}nums windowSize;left pagesList.begin();while (nums0){if(left-secondminof){pagesList.erase(left);pagesList.push_back(make_pair(page,1));break;}left;nums--;}ret;}}//PrintList(pagesList);//coutretendl;}return ret;
}
单词统计
int Solution(const vectorstring lines)
{// 需要特殊处理的 . , -string allLines;int ret 0;for(int l0;llines.size();l){int i 0;if(lines[l] -){ } else{ while (ilines[l].size()){while(ilines[l].size()(lines[l][i],||lines[l][i].||lines[l][i] )){i;}if(ilines[l].size()){ret;while((ilines[l].size())(lines[l][i]zlines[l][i]a)){i;} }if((ilines[l].size()-1 ) lines[l][i]-) {i;if(l1lines.size()lines[l1][0]alines[l1][0]z) { ret--;}if(l1lines.size()lines[l1]-){ret--;}}}}}return ret;
}
