0. 理论

贪心算法的基本要素包括两个部分，分别是：

贪心选择性质：所求问题的整体最优解可以通过一系列的局部最优解得到
最优子结构性质：一个问题的最优解包含其子问题的最优解

note that 动态规划只包含第二个性质，因此我们需要把每个子问题的最优解都存储起来。

1. 实践

1.1 Non-overlapping Intervals - LeetCode 435 [link]

解析：这个题是贪心算法最典型的问题——活动安排问题换了一个问法。题目既然最少要求删去多少个interval才能使得剩余的interval不重叠，那我们只需要求最多能排列几个不重叠的interval即可。因此我们的做法应该是：我们按照所有间隔的终止时间进行排序，然后从头到尾进行遍历，如果后一个间隔的开始时间大于等于前一个的终止时间，便可以排下，否则舍弃掉后一个间隔。

上代码：

class Solution {
public:
    static bool cmp(const std::vector<int> & a,const std::vector<int> &b)
    {
        return a.at(1)<b.at(1);
    }


    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        std::sort(intervals.begin(),intervals.end(),cmp);

        int n = intervals.size();
        int n_compatible = 0;
        int pre_end_time = -50001;  //题目中说最早的开始时间是-50000
        for(auto & interval : intervals)
        {
            if(interval.at(0)>=pre_end_time)
            {
                n_compatible++;
                pre_end_time = interval.at(1);
            }
        }
        return n - n_compatible;
        
    }
};

1.2 Minimum Number of Arrows to Burst Balloons - LeetCode 452 [link]

解析上一个题目是为了让不同的区间尽可能错开，这个题目则反其道行之，旨在让不同的区间尽可能相交，试想如果我们能让一支箭正好射中多个气球的交接处，那样便可以用最少的箭射爆所有气球。因此我们的做法是：按照气球的左端点从小到大排序，遍历得到的序列，在遍历的时候维护一个值x，该值代表上一个箭射击的位置，这个值同时也是其所能射爆的所有气球中右端点最小的一个。在遍历过程中，如果某个气球其左端点比x要大，那么说明上一只箭无法覆盖当前气球，只能多花一只箭；否则说明上一只箭头可以射中当前这只气球，不需要新增箭，这时需要注意，我们需要将x的值更新为新气球的左端点和x中更小的一个。这是因为，如果上一只箭覆盖的气球是[1,6] [2,7],如果新的气球是[2,5] 的话，这只箭最远只能射在5的位置才能保证射爆3只气球

上代码

class Solution {
public:
    static bool cmp(const std::vector<int> & a, const std::vector<int> & b) 
    {
        return a.at(0)<b.at(0);
    }

    int findMinArrowShots(vector<vector<int>>& points) {
        std::sort(points.begin(),points.end(),cmp);
        int min_right_bound= points.at(0).at(1); //第一个区间的右侧边界作为起点

        int ans=1;

        for(int i=0;i<points.size();i++)
        {
            if(points.at(i).at(0)<=min_right_bound)//要是后面的点的左边界比当前点的右边界小，那就可以共享一支箭头
            {
                if(points.at(i).at(1)<min_right_bound)
                    min_right_bound=points.at(i).at(1);
                continue;
            }
                
            else
            {
                ans++;
                min_right_bound=points.at(i).at(1);
            }
        }
        return ans; 
    }
};

1.3 Partition Labels - LeetCode 763 [link]

解析这一题和上一题极为相似但在细节上又有微妙的不同。要求我们划分尽可能多的区间，但需要保证对于每一个字母，该字母只能在一个区间内出现。因此对于每个单词我们维护一个hash table, 记录其第一次出现的位置和最后一次出现的位置，在我们最后的结果中，这个区间必定是其中一个区间的子集。而如果有两个字母的存在区间但凡有一点重叠，我们就必须将其扩充成一个新的大区间。因此我们的做法是：将字母按照第一次出现的位置进行排列，从左到右遍历，如果新出现的字母的第一次出现的位置大于当前维护区间的右端点，我们就开一个新的区间；否则，我们就把这个区间合并在原有区间里面。这里需要注意的是，新区间的右端点是要取一个最大值（这里和上一题进行对比，上一题在更新箭的位置时是取最小值因为要保证一支箭可以射中所有气球；这里取较大值是为了保证当前的区间可以覆盖当前的字母，比如前一个字母的区间是[1,5] , 后一个是[2, 6], 那么至少得需要一个[1,6] 的区间。

上代码

struct info
{
    char ch;
    int first_pos=-1;
    int last_pos=0;
    bool operator<(const info & a)const
    {
        return this->first_pos<a.first_pos;
    }

};

class Solution {
public:
    vector<int> partitionLabels(string s) {
        //std::map<int,info> letter2info;

        std::vector<info> letter2info(26); //只有26个字母，用vector作hash好了

        for(int i=0;i<26;i++)
            letter2info.at(i).ch='a'+i;

        for (int i=0;i<s.size();i++)
        {
            if(letter2info.at(s.at(i)-'a').first_pos==-1)
                letter2info.at(s.at(i)-'a').first_pos=i;
            letter2info.at(s.at(i)-'a').last_pos=i;
        }
        std::sort(letter2info.begin(),letter2info.end());
        std::vector<int> ans;

        int start;

        for(int i=0;i<26;i++)
        {
            if(letter2info.at(i).first_pos!=-1)
            {
                start=i;
                break;
            }
        }
        int right_bound= letter2info.at(start).last_pos;
        int left_bound=letter2info.at(start).first_pos;

        for( int i=start+1; i<26 ;i++)
        {
            if(letter2info.at(i).first_pos<=right_bound)
               right_bound=std::max(right_bound,letter2info.at(i).last_pos)
            else //新的区间
            {
                ans.push_back(right_bound-left_bound+1);
                left_bound=letter2info.at(i).first_pos;
                right_bound=letter2info.at(i).last_pos;
            }
        }
        ans.push_back(right_bound-left_bound+1);
        return ans;
    }
};

1.4 最小生成树

最小生成树的定义在此不再赘述，在连通图中构建最小生成树的方法主要包括Prim算法和Kruskal 算法。这两种算法都基于MST性质。

MST性质： 假设$G=(V,E)$是连通带权图，U是V的真子集。如果$(u,v)\in E$, 且$u\in U$，$v\in V-U$，且在所有这样的边中，(u,v)的权$c[u][v]$最小，那么一定存在G的一棵最小生成树，它以$(u,v)$为其中一条边。

MST性质的证明略。

Prim算法和Kruskal算法分别着眼于最小生成树的节点和最小生成树的边。

1.4.1 Prim算法

在prim算法中，我们首先将图中的所有节点拆分为两个集合$s1$和$s2=V-s1$，其中第一个集合最初包含第0个节点（方便起见）。

随后，我们循环 $n-1$ （n是节点数目）次，在每次循环中，我们取连接$s1$中节点和$s2$中节点的权值最小的一条边$(u,v)$，将$s2$ 中的节点$v$ 取出放入$s1$ 中，直到$s1$ 中包含所有节点，而我们每次取出的节点构成了最小生成树。

我们以这个题目为例 leetcode 1584

在这里面我们创建了两个数组：$closest$和 $lowest$ ，其中$closest$ 中存储的是$s2$ 中的节点连接 $s1$ 中节点的所有的边中权重最短的一条边在$s1$ 中的连接点；$lowest$ 中存储的是$s2$ 中的节点连接 $s1$ 中节点的所有的边中权重最短边的权重，即有 $$ lowest[j]=map[closest[j]][j] $$ 另外一个数组$is_visited$ 用来表示节点在$s1$ 集合中还是在$V-s1$ 集合中。

需要说明的是本题中$closest$ 存在感不强，主要是因为题目只要最小的权重，没要求具体的树的信息。

代码如下

class Solution {
public:

    int distance(std::vector<int> & p1, std::vector<int> & p2)
    {
        return abs(p1.at(0)-p2.at(0))+abs(p1.at(1)-p2.at(1));
    }

    int minCostConnectPoints(vector<vector<int>>& points) {
        int map[1000][1000];

        for(int i=0;i<points.size();i++)
            for(int j=i;j<points.size();j++)
                if(j==i)
                    map[i][j]=0;
                else
                    map[i][j]=map[j][i]=distance(points.at(i),points.at(j));

        int is_visited [1000];
        for(int i=0;i<points.size();i++)
            is_visited[i]=0;
        is_visited[0]=1;

        int closest[1000];  //代表V-s1里面的点到s1距离最小的那个连接点
        for(int i=0;i<points.size();i++)
            closest[i]=0;

        int lowest[1000];  // 代表V-s1里面的点到s1最小的距离
        for(int i=0;i<points.size();i++)
            lowest[i]=map[i][0];

        int ans=0;
        int max_value=1e7;
        int min_len; 
        int min_idx;
        for(int i=0;i<points.size()-1;i++)
        {
            min_len=max_value;
            min_idx=0;
            for(int j=0;j<points.size();j++)
            {
                if(is_visited[j]==0&& lowest[j]<min_len)
                {
                    min_idx=j;
                    min_len=lowest[j];
                }
            }
            is_visited[min_idx]=1;
            ans+=min_len;

            //更新lowest
            for(int i=1;i<points.size();i++)
            {
                if(!is_visited[i] && map[min_idx][i]<lowest[i])
                {
                    closest[i]=min_idx;
                    lowest[i]= map[min_idx][i];
                }
            }
        }

        return ans;
    }
};

1.4.2 Kruskal 算法

Kruskal算法是对于边来进行的，起初，该算法将所有节点看作孤立的分支，然后按照权重从小到大的顺序遍历每一条边，如果发现这条边的两个节点不在一个分支中，就把他们归到一个分支里面；如果当前的边对应的两个顶点已经属于一个连通分支了，则跳过该边，直到所有节点都被放到一个连通分支为止。

这里需要说明的是，在判断两个节点是否属于一个分支的过程中，我们使用了简单的并查集。

代码如下，还是上面那个题 leetcode 1584

class Solution {
public:
    struct edge
    {
        int id1=0;
        int id2=1;
        int len=0;
        bool operator<(const edge a) const
        {
            return this->len<a.len;
        }
    };

    int distance(std::vector<int> & p1, std::vector<int> & p2)
    {
        return abs(p1.at(0)-p2.at(0))+abs(p1.at(1)-p2.at(1));
    }

    int find(int i,const std::vector<int> & fathers)
    {
        if(fathers.at(i)==i)
            return i;
        else
            return find(fathers.at(i),fathers);
    }

    bool union_ (int i,int j, std::vector<int> & fathers)
    {
        int x=find(i,fathers);
        int y=find(j,fathers);
        if(x==y)
            return false;
        else
        {
            fathers.at(x)=y;
            return true;
        }
    }
    int minCostConnectPoints(vector<vector<int>>& points) 
    {
        
        if(points.size()==1)
            return 0;

        std::vector<edge> edges;
        for(int i=0;i<points.size();i++)
        {
            for(int j=i+1;j<points.size();j++)
            {
                if(i!=j)
                {
                    edge new_edge;
                    new_edge.id1=i;
                    new_edge.id2=j;
                    new_edge.len=distance(points.at(i),points.at(j));
                    edges.push_back(new_edge);         
                }     
            }
        }

        std::sort(edges.begin(),edges.end());
        std::vector<int> fathers=std::vector<int>(1000);

        for(int i=0; i<points.size() ;i++)
            fathers.at(i)=i;
        int ans=0;
        int k=0;

        for(auto & edge :edges)
        {
            int i=edge.id1;
            int j=edge.id2;

            if(union_(i,j,fathers))
            {
                ans+=edge.len;
                k++;
            }

            if(k>=points.size())
                break;
        }
        return ans;
    }
};

1.5 Best Time to Buy and Sell Stock II - LeetCode 122 link

解析这道题是相当经典的贪心了，对于给定一个时间序列内的股价且不限交易次数，能得到最多利润的办法就是在local minimum处买入，在买入后的第一个local maximum处卖出。这一方法的贪心性质也很好证明：假设在local maximum的某个时间后股价更高的时间点卖出可以得到更多的利润。那么我们设买入的价格是 v1, local maximum是v2 , v2后一个时间戳的股价为v3, v3后某个股价高于v2的值为v4, 容易得到 (v2-v1)+(v4-v3) > v4-v1 (因为v3比v2小)。

代码如下

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int min_price=prices.at(0);
        int max_price=min_price;
        int profit=0;
        for(int i=1;i<prices.size();i++)
        {
            if(prices.at(i)<max_price) //一旦在max price后面出现更小的值，说明max value是local maximum
            {
                profit+=max_price-min_price;
                min_price=max_price=prices.at(i);
            }

            else
            {
                min_price=std::min(min_price,prices.at(i));
                max_price=std::max(max_price,prices.at(i));
            }
        }
        profit+=max_price-min_price;
        return profit;
    }
};

1.6 Queue Reconstruction by Height - LeetCode 406 link

解析这个题看题干有点晦涩，不如直接看例子。由于每个tuple的第二个元素代表的是在它之前且比它大的元素，我们很容易想到我们先按照大小排序，然后对于每个tuple, 将其向后挪动x个位置即可（x为第二个元素的值）。由于前一个tuple的挪动会干扰到后一个元素（考虑[(1,1)(2,1)(3,0)], 正确的结果应该是[(3,0),(1,1),(2,1)], 但由于(1,1)先一步向后挪动了一个位置，导致后挪动的(2,1) 的移动操作仅仅使得列表恢复到原来的状态），我们逆序遍历排好序的列表并执行上述操作。

代码如下

class Solution {
public:
    static bool cmp(const std::vector<int> & a, const std::vector<int> & b ) 
    {
        if (a.at(0)<b.at(0))
            return true;
        else if (a.at(0)==b.at(0) && a.at(1)<b.at(1) )
            return true;
        return false;
    }
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {

        std::sort(people.begin(),people.end(),cmp);

        for (int i=people.size()-1; i>=0 ;i--)
        {
            int num_geq=people.at(i).at(1);
            int current_height= people.at(i).at(0);

            for(int j=i-1;j>=0;j--)
            {
                if(people.at(j).at(0)==current_height)
                    num_geq--;
                if(num_geq==0)
                    break;
            }
            //geq 是多少，説明當前這個元素需要和後面的多少位調換順序
            auto target_pos=people.begin()+i+num_geq+1;
            people.insert((target_pos),people.at(i));
            people.erase(people.begin()+i);
        }

        return people;
    }
};

在讨论区有人给出了代码上更简单的解法，在这里也mark一下 ( from leetcode user tonygogogo )

vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
    sort(people.begin(), people.end(),[](pair<int,int> p1, pair<int,int> p2){
        return p1.first > p2.first || (p1.first == p2.first && p1.second < p2.second);
    });
    vector<pair<int,int>> sol;
    for (auto person : people){
        sol.insert(sol.begin() + person.second, person);
    }
    return sol;
}

ending

做过的所有贪心相关的leetcode题目在这个列表下面，供某日复习使用。

0. 理论#

1. 实践#

1.1 Non-overlapping Intervals - LeetCode 435 [link]#

1.2 Minimum Number of Arrows to Burst Balloons - LeetCode 452 [link]#

1.3 Partition Labels - LeetCode 763 [link]#

1.4 最小生成树#

1.4.1 Prim算法#

1.4.2 Kruskal 算法#

1.5 Best Time to Buy and Sell Stock II - LeetCode 122 link#

1.6 Queue Reconstruction by Height - LeetCode 406 link#

ending#

0. 理论

1. 实践

1.1 Non-overlapping Intervals - LeetCode 435 [link]

1.2 Minimum Number of Arrows to Burst Balloons - LeetCode 452 [link]

1.3 Partition Labels - LeetCode 763 [link]

1.4 最小生成树

1.4.1 Prim算法

1.4.2 Kruskal 算法

1.5 Best Time to Buy and Sell Stock II - LeetCode 122 link

1.6 Queue Reconstruction by Height - LeetCode 406 link

ending