14天阅读挑战赛——贪心算法（二）

14天阅读挑战赛

程序员面试最难的部分就是手写代码，手写代码测试不但能够考察算法运用能力，思维能力，还能看出代码编写习惯。
想去大厂，还是需要及早刷题，这次有机会参与读算法。
本节是书中的第二章，贪心算法。

图书试阅读地址
https://www.epubit.com/onlineEbookReader?id=fb652b37-b7a6-4843-a933-5ed68b2395c1

算法知识点

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。

我一直觉得贪心和动态规划很像。其实通过看书、查资料，也得到一个规律，那就是贪心没有什么具体的公式。
如果找出局部最优并可以推出全局最优，就是贪心，如果局部最优都没找出来，就不是贪心，可能是单纯的模拟。

相关算法题型题目总结

贪心算法题目挺多，包括leetcode上面也有很多。我本身算法功底，数学功底还是偏弱，短时间内可能不适合看难题。本节就看一下中等难度的题目是怎么样的。

算法题目描述

leetcode-单调递增的数字

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

示例 1:

输入: N = 10
输出: 9
示例 2:

输入: N = 1234
输出: 1234
示例 3:

输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。

题目分析

作为一个小菜鸡程序员，看到题目内心os：就这还中等难度？不就是for循环的事嘛。
当然暴力解决肯定可以，就是不优雅。
运用贪心我们怎么做这个题目呢？

例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]–，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。

这一点如果想清楚了，这道题就好办了。

局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]–，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。

全局最优：得到小于等于N的最大单调递增的整数。

模板代码

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string strNum = to_string(N);
        // flag用来标记赋值9从哪里开始
        // 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行
        int flag = strNum.size();
        for (int i = strNum.size() - 1; i > 0; i--) {
            if (strNum[i - 1] > strNum[i] ) {
                flag = i;
                strNum[i - 1]--;
            }
        }
        for (int i = flag; i < strNum.size(); i++) {
            strNum[i] = '9';
        }
        return stoi(strNum);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19