1 题目分类

• 第一个大分类是算法。本书先从最简单的贪心算法讲起，然后逐渐进阶到二分查找、排序算法和搜索算法，最后是难度比较高的动态规划和分治算法。

• 第二个大分类是数学，包括偏向纯数学的数学问题，和偏向计算机知识的位运算问题。这类问题通常用来测试你是否聪敏，在实际工作中并不常用，笔者建议可以优先把精力放在其它大类上。

• 第三个大分类是数据结构，包括 C++ STL 内包含的常见数据结构、字符串处理、链表、树和图。其中，链表、树、和图都是用指针表示的数据结构，且前者是后者的子集。最后我们也将介绍一些更加复杂的数据结构，比如经典的并查集和 LRU。

2 最易懂的贪心算法

2.1 算法解释

• 顾名思义，贪心算法或贪心思想采用贪心的策略，保证每次操作都是局部最优的，从而使最后得到的结果是全局最优的。举一个最简单的例子：小明和小王喜欢吃苹果，小明可以吃五个，小王可以吃三个。已知苹果园里有吃不完的苹果，求小明和小王一共最多吃多少个苹果。在这个例子中，我们可以选用的贪心策略为，每个人吃自己能吃的最多数量的苹果，这在每个人身上都是局部最优的。又因为全局结果是局部结果的简单求和，且局部结果互不相干，因此局部最优的策略也同样是全局最优的策略。

2.2 分配问题

455. 分发饼干

题目描述

• 有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有一个大小。每个孩子只能吃一个饼干，且只有饼干的大小不小于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩子可以吃饱。

输入输出样例

• 输入两个数组，分别代表孩子的饥饿度和饼干的大小。输出最多有多少孩子可以吃饱的数量。

Input: [1,2], [1,2,3] 前面数组是孩子，后面是饼干

Output: 2

在这个样例中，我们可以给两个孩子喂 [1,2]、[1,3]、[2,3] 这三种组合的任意一种。

题解

因为饥饿度最小的孩子最容易吃饱，所以我们先考虑这个孩子。为了尽量使得剩下的饼干可以满足饥饿度更大的孩子，所以我们应该把大于等于这个孩子饥饿度的、且大小最小的饼干给这个孩子。满足了这个孩子之后，我们采取同样的策略，考虑剩下孩子里饥饿度最小的孩子，直到没有满足条件的饼干存在。

简而言之，这里的贪心策略是，给剩余孩子里最小饥饿度的孩子分配最小的能饱腹的饼干，以此类推。

至于具体实现，因为我们需要获得大小关系，一个便捷的方法就是把孩子和饼干分别排序。这样我们就可以从饥饿度最小的孩子和大小最小的饼干出发，计算有多少个对子可以满足条件。

注意

对数组或字符串排序是常见的操作，方便之后的大小比较。

注意

在之后的讲解中，若我们谈论的是对连续空间的变量进行操作，我们并不会明确区分数组和字符串，因为他们本质上都是在连续空间上的有序变量集合。一个字符串“abc”可以被看作一个数组 [‘a’,‘b’,‘c’]。

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin() , g.end());
        sort(s.begin() , s.end());

        int childen = 0;
        int cookies = 0;
        
        while(cookies < s.size() && childen < g.size() )
        {
            if(s[cookies] >= g[childen]) childen++;
            cookies++;
        }
        return childen;
    }
};

135. 分发糖果

题目描述

一群孩子站成一排，每一个孩子有自己的评分。现在需要给这些孩子发糖果，规则是如果一个孩子的评分比自己身旁的一个孩子要高，那么这个孩子就必须得到比身旁孩子更多的糖果；所有孩子至少要有一个糖果。求解最少需要多少个糖果。

输入输出样例

输入是一个数组，表示孩子的评分。输出是最少糖果的数量。

Input: [1,0,2]

Output: 5

在这个样例中，最少的糖果分法是 [2,1,2]。

题解

做完了题目 455，你会不会认为存在比较关系的贪心策略一定需要排序或是选择？

虽然这一道题也是运用贪心策略，但我们只需要简单的两次遍历即可：把所有孩子的糖果数初始化为 1；先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的糖果数加 1；再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加 1。

通过这两次遍历，分配的糖果就可以满足题目要求了。这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一侧的大小关系。在样例中，我们初始化糖果分配为 [1,1,1]，第一次遍历更新后的结果为 [1,1,2]，第二次遍历更新后的结果为 [2,1,2]

class Solution {
public:
    int candy(vector<int>& ratings) {
        int size = ratings.size();
        if(size == 1)return 1;

        vector<int> num(size , 1);
        for(int i = 1 ; i < size ; ++i)
        {
            if(ratings[i] > ratings[i - 1])
            {
                num[i] = num[i - 1] + 1;
            }
        }

        for(int i = size - 1 ; i > 0 ; --i)
        {
            if(ratings[i] < ratings[i - 1])
            {
                //和上次分配的糖果进行比较,取最大值
                num[i - 1] = max(num[i - 1] , num[i] + 1);
            }
        }

        // std::accumulate 可以很方便地求和
        return accumulate(num.begin() , num.end() , 0);
    }
};

2.3 区间问题

题目描述

• 给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。

输入输出样例

输入是一个数组，数组由多个长度固定为 2 的数组组成，表示区间的开始和结尾。输出一个整数，表示需要移除的区间数量。

Input: [[1,2], [2,4], [1,3]]

Output: 1

在这个样例中，我们可以移除区间 [1,3]，使得剩余的区间 [[1,2], [2,4]] 互不重叠。

题解

在选择要保留区间时，区间的结尾十分重要：选择的区间结尾越小，余留给其它区间的空间就越大，就越能保留更多的区间。因此，我们采取的贪心策略为，优先保留结尾小且不相交的区间。

具体实现方法为，先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选择的区间不重叠的区间。我们这里使用 C++ 的 Lambda，结合 std::sort() 函数进行自定义排序。

在样例中，排序后的数组为 [[1,2], [1,3], [2,4]]。按照我们的贪心策略，首先初始化为区间[1,2]；由于 [1,3] 与 [1,2] 相交，我们跳过该区间；由于 [2,4] 与 [1,2] 不相交，我们将其保留。因此最终保留的区间为 [[1,2], [2,4]]。

注意

需要根据实际情况判断按区间开头排序还是按区间结尾排序。

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size() == 1)return 0;

        sort(intervals.begin() , intervals.end() , [](vector<int>& a , vector<int>& b){
            return a[1] < b[1]; //按照区间第二个数来排序,越小排的越前面
        });

        int pre = intervals[0][1] , total = 0 ;

        for(int i = 1 ; i < intervals.size() ; ++i)
        {
            //如果这两个有重叠,那么就略过这个元素往后继续找
            if(pre > intervals[i][0]){
                total++;
            }
            else{
                pre = intervals[i][1];
            }
        }
        return total;
    }
};

2.4 练习

605. 种花问题

题目描述

• 假设有一个很长的花坛，一部分地块种植了花，另一部分却没有，花不能种植在相邻的地块上，给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

示例 1：

输入：flowerbed = [1,0,0,0,1], n = 1
输出：true

题解

判断每个位置是否可以种花，需要当前节点，前置节点，后置节点同时为0，

另外有两个特殊节点，就是如果是第一个节点则没有前置节点（置为 0），如果是最后一个节点，那么后置节点（置为 0）。

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {

        for(int i = 0; i< flowerbed.size() && n > 0 ; ++i)
        {
            if(flowerbed[i] == 1)continue;

            //到达此处意味着,上一个点为0
            //这里找出这个点两旁的元素是否为0,如果都为0那么可以插入
            //这里考虑到两端,一个没有前驱,一个没有后继,所以用三元运算符
            int pre = (i == 0 ? 0 : flowerbed[i - 1]);
            int next = (i == flowerbed.size() - 1 ? 0 : flowerbed[i + 1]);
            if(pre == 0 && next ==0){
                n--;
                flowerbed[i] = 1;
            }
        }
        return n == 0;
    }
};

452. 用最少数量的箭引爆气球

题目描述

• 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。给你一个数组 points ，返回引爆所有气球所必须射出的最小弓箭数 。

示例 1：

输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：气球可以用2支箭来爆破:
在x = 6处射出箭，击破气球[2,8]和[1,6]。
在x = 11处发射箭，击破气球[10,16]和[7,12]。

示例 2：

输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
解释：每个气球需要射出一支箭，总共需要4支箭。

题解：

先给数组排序，这样好找出不重叠的区间

找到所有不重叠空间的数量，就是要射出剑的个数。

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {

        sort(points.begin() , points.end() , [](vector<int>& v1 , vector<int>& v2){
            return v1[1] < v2[1];//区间第二个数小的排前面，是便于后面找是否有重叠
        });

        int cur = points[0][1];
        int count = 1;
        for(int i =1 ; i < points.size() ; ++i)
        {
            if(cur >= points[i][0])continue;

            //若气球没有重叠，则再加一只箭
            cur = points[i][1];
            count++;
        }
        return count;
    }
};