企业网站文章,做期货看什么网站,app推广之家,信誉好的大连网站建设代码随想录刷题60Day 目录
前言
单调递增数列
贪心算法总结 前言
今天是贪心算法刷题的最后一天#xff0c;今天本来是打算刷两道题#xff0c;其中的一道hard题做了好久都没有做出来(主要思路错了)。然后再总结一下。 单调递增数列 int monotoneIncreasingDigits(int n…代码随想录刷题60Day 目录
前言
单调递增数列
贪心算法总结 前言
今天是贪心算法刷题的最后一天今天本来是打算刷两道题其中的一道hard题做了好久都没有做出来(主要思路错了)。然后再总结一下。 单调递增数列 int monotoneIncreasingDigits(int n) {if (n 10)return n;vectorint num;int result 0;int j num.size() - 2, k;while (n){num.push_back(n % 10);n / 10;}for (j num.size() - 2,k j 1; j 0; --j){if (num[j] num[k]){--num[k];break;}else if (num[j] num[k])k j;}if (j 0) k 0;for (int i num.size() - 1; i 0; --i){if (i k)result result * 10 num[i];elseresult result * 10 9;}return result;}
未解决题 贪心算法总结
贪心算法是一种常见的算法设计技术用于在每个步骤中做出局部最优选择以期望达到全局最优解。下面是对贪心算法的总结
1. 基本思想贪心算法每次都选择当前最优的解决方案而不考虑未来的后果。它通过贪心选择策略在每个步骤上做出局部最优选择以期望达到全局最优解。
2. 常规步骤 · 确定问题的最优子结构。 · 构建贪心选择策略即每一步选择局部最优解。 · 证明贪心选择的正确性。 · 设计递归算法或迭代算法实现贪心选择策略。 · 分析算法的时间复杂度和空间复杂度。
3. 优点 · 算法简单易实现。 · 在某些问题上能够快速得到近似最优解。 · 时间复杂度较低通常为线性或近似线性时间。
4. 缺点 · 贪心选择策略可能会导致无法达到全局最优解。 · 对于某些问题贪心算法不一定能给出正确的解决方案。 · 需要证明贪心选择的正确性有时需要较高的数学推理能力。
总的来说贪心算法是一种简单而有效的算法设计技术适用于满足贪心选择性质和最优子结构性质的问题。它通过每一步的局部最优选择期望达到全局最优解。然而贪心算法并不适用于所有问题有时需要综合考虑其他算法技术或进行适当的修改。
