leetcode刷题-贪心算法专题

2023-03-08 19:05:48

目录

贪心专题

cppreferences

L455

分配问题
题目链接
贪心算法：优先给需求低的分配最小尺寸的饼干

题解

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

        int child=0,cookie=0;

        while(child<g.size()&&cookie<s.size()){
            if(s[cookie]>=g[child]){
                child++;
            }
            cookie++;
        }
        
        return child;

    }
};

sort

  1. 定义
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

头文件<algorithm>

  1. 排序

排序方法函数comp可以自定义，默认从小到大排序

举例：

#include<iostream>
#include<algorithm>
using namespace std;
bool cmp(int a,int b);
main(){
　　//sort函数第三个参数自己定义，实现从大到小
　　int a[]={45,12,34,77,90,11,2,4,5,55};
　　sort(a,a+10,cmp);
　　for(int i=0;i<10;i++)
　　　　cout<<a[i]<<" ";
}
//自定义函数
bool cmp(int a,int b){
　　return a>b;
}

元素自身包含了比较关系，如int，double等基础类型，可以直接进行比较greater<int>() 递减， less<int>() 递增（缺省）

main(){
    int s[]={34,56,11,23,45};
    vector<int>arr(s,s+5);
    sort(arr.begin(),arr.end(),greater<int>());
    for(int i=0;i<arr.size();i++)
        cout<<arr[i]<<" ";
}
  1. 类注意重载比较符号（有需要的话）

L135

candy
题目链接

证明贪心算法的正确性

链接

题解

这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一
侧的大小关系。
可以看官方表述，将题目分解为一个新的规则：满足左、右规则。
先一次性给每个人都分一颗（题目要求至少一颗）
再分别左右两次遍历

class Solution {
public:
    int candy(vector<int>& ratings) {
        //只有一个人则直接返回
        int size=ratings.size();
        if(size<=1)
            return size;
        
        //糖果分配数组，初始值都为1
        vector<int> number (size,1);
        
        //从左遍历
        for(int i=0;i<size;i++){
            if(i+1<size&&ratings[i]<ratings[i+1])
                number[i+1]=number[i]+1;          
        }

        //从右遍历
        for(int i=size-1;i>=0;i--){
            if(i-1>=0&&ratings[i-1]>ratings[i]){
                if(number[i-1]<=number[i])
                    number[i-1]=number[i]+1;
            }
        }

        return accumulate(number.begin(),number.end(),0);
    }
};

vector初始化

  • 最基本的vector构造
vector<int> Array;
  • 带参数的构造函数初始化
vector<int> Array(10);//size=10
vector<int> Array(10,1);//size=10 全部初始化为1
  • 通过数组地址初始化
int a[5]={1,2,3,4,5};
vector<int>b(a,a+5);
  • 通过同类型的vector初始化-复制/赋值构造函数
vector<int>a(6,6);
vector<int>b(a);    //需要有对于的构造函数
  • 二维vector初始化大小
vector< vector<int> > newOne (r,vector<int>(c,0));

//通过resize控制大小
vector<vector<int>> newOne;
newOne.resize(r);   //r行
for(int i=0;i<r;i++){
    res[i].resize(c);   //r列
}

vector的insert方法

b.insert(b.begin(),a,a+6);
b.insert(b.begin(),6,6);

accumulate函数

  • 头文件<numeric>

前两个参数是定义序列的输入迭代器，第三个参数是和的初值；第三个参数的类型决定了返回值的类型。

优化

目前时间复杂度$O(N)$,空间复杂度$O(N)$
这里把最终每个人的糖果数目记录起来了，可以考虑在算法过程中使用变量记录信息。即官方题解二：常数空间遍历

依据前面总结的规律，我们可以提出本题的解法。我们从左到右枚举每一个同学，记前一个同学分得的糖果数量为 pre：

  • 如果当前同学比上一个同学评分高，说明我们就在最近的递增序列中，直接分配给该同学 pre+1 个糖果即可。

  • 否则我们就在一个递减序列中，我们直接分配给当前同学一个糖果，并把该同学所在的递减序列中其他的同学都再多分配一个糖果，以保证糖果数量还是满足条件。

我们无需显式地额外分配糖果，只需要记录当前的递减序列长度，即可知道需要额外分配的糖果数量。

  • 同时注意当当前的递减序列长度和上一个递增序列等长时，需要把最近的递增序列的最后一个同学也并进递减序列中。

举例：
ranking 1 2 4 3 2 1 这里递增序列124长度等于递减序列321
则分配： 1 2 4 3 2 1

这样，我们只要记录当前递减序列的长度 dec，最近的递增序列的长度 inc 和前一个同学分得的糖果数量 pre 即可。

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        int ret = 1;
        int inc = 1, dec = 0, pre = 1;
        for (int i = 1; i < n; i++) {
            if (ratings[i] >= ratings[i - 1]) {
                dec = 0;
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                ret += pre;
                inc = pre;
            } else {
                dec++;
                if (dec == inc) {
                    dec++;
                }
                ret += dec; //dec等于给所有递减序列所有人应该增加的糖果数量
                pre = 1;
            }
        }
        return ret;
    }
};

其实这里代码逻辑跟题解稍微有些不一样，但是达到的结果是一样的

空间复杂度降到$O(1)$

L435

无重叠区间问题

题目链接

主要基于官方题解

题解-动态规划

题目的要求等价于「选出最多数量的区间，使得它们互不重叠」。
等价转换的思想
所有的区间按照左端/右端进行排序，状态转移方程：
$f_i=max_{j<i \ and \ rj <= li }(f_j)+1$
$f_i$表示以区间i为最后一个区间，可以选出的区间数量的最大值

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.empty())
            return 0;
        
        sort(intervals.begin(),intervals.end(),[](vector<int> &u,vector<int>&v){
            return u[0]<v[0];
        });

        int n=intervals.size();
        vector<int>f(n,1);  //动态规划中记录信息
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                if(intervals[j][1]<=intervals[i][0]){
                    f[i]=max(f[i],f[j]+1);
                }
            }
        }

        return n-*max_element(f.begin(),f.end());
    }
};

Lambda表达式

C++ 11 中的 Lambda 表达式用于定义并创建匿名的函数对象，以简化编程工作。
Lambda 的语法形式如下：

[函数对象参数] (操作符重载函数参数) mutable 或 exception 声明 -> 返回值类型 {函数体}

  • [函数对象参数]

标识一个 Lambda 表达式的开始，这部分必须存在，不能省略。
函数对象参数是传递给编译器自动生成的函数对象类的构造
函数的。

  1. 空。没有任何函数对象参数
  2. = 函数体内可以使用 Lambda 所在范围内所有可见的局部变量（包括 Lambda 所在类的 this），并且是值传递方式
  3. &。函数体内可以使用 Lambda 所在范围内所有可见的局部变量（包括 Lambda 所在类的 this），并且是引用传递方式
  4. this。函数体内可以使用 Lambda 所在类中的成员变量。
  5. a。将 a 按值进行传递。按值进行传递时，函数体内不能修改传递进来的 a 的拷贝，因为默认情况下函数是 const 的，要修改传递进来的拷贝，可以添加 mutable 修饰符。
  6. &a。将 a 按引用进行传递。
  7. a，&b。将 a 按值传递，b 按引用进行传递。
  8. =，&a，&b。除 a 和 b 按引用进行传递外，其他参数都按值进行传递。
  9. &，a，b。除 a 和 b 按值进行传递外，其他参数都按引用进行传递。
  • (操作符重载函数参数)

不太清楚。没有参数时可以省略

  • mutable 或 exception声明

可以省略
mutable：按值进行传递时，加上mutable修饰符可以进行修改传递进来的拷贝
exception：用于声明指定函数抛出的异常（没有了解）

*max_element

输出集合中最大元素

同理min_element 输出集合最小元素

头文件algorithm

题解-贪心算法


class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if (intervals.empty()) {
            return 0;
        }
        
        sort(intervals.begin(), intervals.end(), [](const auto& u, const auto& v) {
            return u[1] < v[1];
        });

        int n = intervals.size();
        int right = intervals[0][1];
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            if (intervals[i][0] >= right) {
                ++ans;
                right = intervals[i][1];
            }
        }
        return n - ans;
    }
};

时间复杂度：O(nlogn)，其中 n 是区间的数量。我们需要 O(nlogn) 的时间对所有的区间按照右端点进行升序排序。

空间复杂度：O(logn)，即为排序需要使用的栈空间。

L605 种花问题 EASY

尽量间隔种满

我的拙劣题解（但是双百分90+了。。）
遍历按照规则间隔种满，但是太多if-else

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {  
        int max=0;
        int length = flowerbed.size();

        if(length==1){
            if(flowerbed[0]==1&&n>0)
                return false;
            if(flowerbed[0]==0&&n<=1)
                return true;
        }

        for(int i=0;i<length;i++){
            if(flowerbed[i]==1)
                continue;
            else if(i==0){
                if(flowerbed[1]==0){
                    max++;
                    flowerbed[i]=1;
                }
            }else if(i==length-1){
                if(flowerbed[length-2]==0){
                    max++;
                    flowerbed[i]=1;
                }
            }else if(flowerbed[i-1]==0&&flowerbed[i+1]==0){
                max++;
                flowerbed[i]=1;
            }
        }

        if(n<=max)
            return true;
        else 
            return false;

    }
};

评论区的简化版本
利用了题目的规则简化了代码写法：因为如果遇到1,那么下一格子一定是0，选择连跳两格来进行遍历

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        // 每次跳两格
         for (int i = 0; i < flowerbed.size(); i += 2) {
             // 如果当前为空地
            if (flowerbed[i] == 0) {
                // 如果是最后一格或者下一格为空
                if (i == flowerbed.size() - 1 || flowerbed[i + 1] == 0) {
                    n--;
                } else {
                    i++;
                }
            }
        }
        return n <= 0;
    }
};

L452 用最少数量的箭引爆气球 MID

相似于L435
本题只是也要排除紧挨着的区间


class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        if (points.empty()) {
            return 0;
        }
        
        sort(points.begin(), points.end(), [](const auto& u, const auto& v) {
            return u[1] < v[1];
        });

        int n = points.size();
        int right = points[0][1];
        int ans = 1;
        for (int i = 1; i < n; ++i) {
            if (points[i][0] > right) {
                ++ans;
                right = points[i][1];
            }
        }
        return ans;
    }
};

L763 划分字母区间 MID

两次遍历
第一次记录字母的最后一次出现，即我们为了满足条件可能的end
再一次遍历来确定区间

class Solution {
public:
    vector<int> partitionLabels(string S) {
        vector<int> Res;       
        int end=0;
        int start=0;

        int Record[26]{0};
        for(int i=0;i<S.size();i++){
            Record[S[i]-'a']=i;
        }

        for(int i=start;i<S.size();i++){
            end = max(end,Record[S[i]-'a']);
            if(i==end){
                Res.push_back(end-start+1);
                start=end+1;
            }
        }

        return Res;
    }
};

L122 买卖股票的最佳时机 II EASY

递增的差距即收益

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

        int profit=0;
        for(int i=1;i<prices.size();i++){
            if(prices[i]>prices[i-1])
                profit+=(prices[i]-prices[i-1]);
        }

        return profit;
    }
};

L406 根据身高重建队列 MID

我是傻逼

    /**
     * 解题思路：先排序再插入
     * 1.排序规则：按照先H高度降序，K个数升序排序
     * 2.遍历排序后的数组，根据K插入到K的位置上
     *
     * 核心思想：高个子先站好位，矮个子插入到K位置上，前面肯定有K个高个子，矮个子再插到前面也满足K的要求
     *
     * @param people
     * @return
     */
    public int[][] reconstructQueue(int[][] people) {
        // [7,0], [7,1], [6,1], [5,0], [5,2], [4,4]
        // 再一个一个插入。
        // [7,0]
        // [7,0], [7,1]
        // [7,0], [6,1], [7,1]
        // [5,0], [7,0], [6,1], [7,1]
        // [5,0], [7,0], [5,2], [6,1], [7,1]
        // [5,0], [7,0], [5,2], [6,1], [4,4], [7,1]
        Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);

        LinkedList<int[]> list = new LinkedList<>();
        for (int[] i : people) {
            list.add(i[1], i);
        }

        return list.toArray(new int[list.size()][2]);
    }
上一篇：leetcode-56合并区间(排序)


下一篇：合并区间