代码随想录训练营第三十七天 | 单调递增的数字&&*监控二叉树&&贪心总结

738.单调递增的数字

文章：22. 单调递增的数字

题目：738. 单调递增的数字

【思路】

从后往前遍历，这样可以避开从前往后时出现前一位比后两位的数字小的问题。

332->329->299

循环的起始点是比较倒数第二位（i）和倒数第一位（i-1）的数值

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int monotoneIncreasingDigits(int n) {
        //题目给的是数字，我们需要将其转化为一个char数组方便我们对其进行后续的修改。
        String s = String.valueOf(n);
        char[] ch = s.toCharArray();
        int start = s.length();
        for(int i = s.length()-2;i>=0;i--){
            if(ch[i]>ch[i+1]){
                ch[i]--;
                start=i+1;
            }
        }
        for(int i = start;i<s.length();i++){
            ch[i] = '9';
        }
        return Integer.parseInt(String.valueOf(ch));
    } 
}
  • Go实现

int转string类型的函数是: strconv.Itoa(num)

string转int类型的函数是: strconv.Atoi(string)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func monotoneIncreasingDigits(n int) int {
    s := strconv.Itoa(n)
    ss := []byte(s)
    start := len(ss)
    for i := len(ss)-2;i>=0;i--{
        if ss[i] > ss[i+1]{
            ss[i]--
            start = i+1
        }
    }
    for i := start;i <len(s);i++{
        ss[i] = '9'
    }
    res,_ := strconv.Atoi(string(ss))
    return res 
}

968.监控二叉树

文章：

题目：

【思路】

  • Java实现
1

  • Go实现
1

贪心算法总结篇

文章：24. 贪心算法总结篇

贪心：从局部最优推出全局最优

贪心理论基础

在贪心系列开篇词关于贪心算法，你该了解这些！ (opens new window)中，我们就讲解了大家对贪心的普遍疑惑。

  1. 贪心很简单，就是常识？

跟着一起刷题的录友们就会发现，贪心思路往往很巧妙，并不简单。

  1. 贪心有没有固定的套路？

贪心无套路，也没有框架之类的，需要多看多练培养感觉才能想到贪心的思路。

  1. 究竟什么题目是贪心呢？

Carl个人认为：如果找出局部最优并可以推出全局最优，就是贪心，如果局部最优都没找出来，就不是贪心，可能是单纯的模拟。（并不是权威解读，一家之辞哈）

但我们也不用过于强调什么题目是贪心，什么不是贪心，那就太学术了，毕竟学会解题就行了。

  1. 如何知道局部最优推出全局最优，有数学证明么？

在做贪心题的过程中，如果再来一个数据证明，其实没有必要，手动模拟一下，如果找不出反例，就试试贪心。面试中，代码写出来跑过测试用例即可，或者自己能自圆其说理由就行了

就像是 要用一下 1 + 1 = 2，没有必要再证明一下 1 + 1 究竟为什么等于 2。（例子极端了点，但是这个道理）

相信大家读完关于贪心算法，你该了解这些！ (opens new window)，就对贪心有了一个基本的认识了。

#贪心简单题

以下三道题目就是简单题，大家会发现贪心感觉就是常识。是的，如下三道题目，就是靠常识，但我都具体分析了局部最优是什么，全局最优是什么，贪心也要贪的有理有据！

#贪心中等题

贪心中等题，靠常识可能就有点想不出来了。开始初现贪心算法的难度与巧妙之处。

#贪心解决股票问题

大家都知道股票系列问题是动规的专长，其实用贪心也可以解决，而且还不止就这两道题目，但这两道比较典型，我就拿来单独说一说

#两个维度权衡问题

在出现两个维度相互影响的情况时，两边一起考虑一定会顾此失彼，要先确定一个维度，再确定另一个一个维度。

在讲解本题的过程中，还强调了编程语言的重要性，模拟插队的时候，使用C++中的list（链表）替代了vector(动态数组)，效率会高很多。

所以在贪心算法：根据身高重建队列（续集） (opens new window)详细讲解了，为什么用list（链表）更快！

大家也要掌握自己所用的编程语言，理解其内部实现机制，这样才能写出高效的算法！

#贪心难题

这里的题目如果没有接触过，其实是很难想到的，甚至接触过，也一时想不出来，所以题目不要做一遍，要多练！

#贪心解决区间问题

关于区间问题，大家应该印象深刻，有一周我们专门讲解的区间问题，各种覆盖各种去重。

#其他难题

贪心算法：最大子序和 (opens new window)其实是动态规划的题目，但贪心性能更优，很多同学也是第一次发现贪心能比动规更优的题目。

贪心算法：加油站 (opens new window)可能以为是一道模拟题，但就算模拟其实也不简单，需要把while用的很娴熟。但其实是可以使用贪心给时间复杂度降低一个数量级。

最后贪心系列压轴题目贪心算法：我要监控二叉树！ (opens new window)，不仅贪心的思路不好想，而且需要对二叉树的操作特别娴熟，这就是典型的交叉类难题了。