【算法合集】学习算法第六天（贪心篇）

﹏ヽ暗。殇╰゛Y 2024-05-23 18:59 49阅读 0赞

> ✅?个人主页：[程序猿追][Link 1]
> 
> ✅?系列专栏：[算法合集][Link 2]
> 
> ✅?作者简介：大家好，我是程序猿追，全栈领域新星创作者，算法爱好者，常在作者周榜排名前30，某不知名的 ACMer
> 
> ✅?推荐一款刷题面试找工作三不误的网站——[牛客网][Link 3]
> 
> ✅?个人名言：不积跬步无以至千里，趁年轻，使劲拼，给未来的自己一个交代！

## 分糖果问题 ##

> **描述**
> 
> 一群孩子做游戏，现在请你根据游戏得分来发糖果，要求如下：
> 
> 1. 每个孩子不管得分多少，起码分到一个糖果。
> 
> 2. 任意两个相邻的孩子之间，得分较多的孩子必须拿多一些糖果。(若相同则无此限制)
> 
> 给定一个数组 arrarr 代表得分数组，请返回最少需要多少糖果。
> 
> 要求: 时间复杂度为 O(n) 空间复杂度为 O(n)
> 
> 数据范围：1≤n≤100000 ，1≤ai≤1000
> 
> **示例1**
> 
> 输入：
> 
> \[1,1,2\]
> 
> 返回值：
> 
> 4
> 
> 说明：
> 
> 最优分配方案为1,1,2
> 
> **示例2**
> 
> 输入：
> 
> \[1,1,1\]
> 
> 返回值：
> 
> 3
> 
> 说明：
> 
> 最优分配方案是1,1,1

### 题解代码 ###

import java.util.*;
    public class Solution {
        public int candy (int[] arr) {
            int n=arr.length;
            if(n<=1)
                return n;
            int[] nums = new int[n];
            for(int i=0; i<n; i++){
                nums[i] = 1;
            }
            //从左到右遍历 fast-template
            for(int i = 1; i < arr.length; i++){
                //如果右边在递增，每次增加一个
                if(arr[i] > arr[i - 1])
                    nums[i] = nums[i - 1] + 1;
            }
            //记录总糖果数
            int res = nums[arr.length - 1];
            //从右到左遍历
            for(int i = arr.length - 2; i >= 0; i--){
                 //如果左边更大但是糖果数更小
                if(arr[i] > arr[i + 1] && nums[i] <= nums[i + 1])
                    nums[i] = nums[i + 1] + 1;
                    //累加和
                res += nums[i];
            }
            return res;}
    }

## 主持人调度（二） ##

> **描述**
> 
> 有 n 个活动即将举办，每个活动都有开始时间与活动的结束时间，第 i 个活动的开始时间是 starti ,第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。  
>   
> 一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第 i 个活动，那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动，最少需要多少名主持人。  
> ![902eb55e5c7a4bea82451ce2b53e334e.png][]
> 
> **示例1**
> 
> 输入：
> 
> 2,\[\[1,2\],\[2,3\]\]
> 
> 返回值：
> 
> 1
> 
> 说明：
> 
> 只需要一个主持人就能成功举办这两个活动
> 
> **示例2**
> 
> 输入：
> 
> 2,\[\[1,3\],\[2,4\]\]
> 
> 返回值：
> 
> 2
> 
> 说明：需要两个主持人才能成功举办这两个活动
> 
> **备注：**
> 
> 1≤n≤105
> 
> start\_i,end\_istarti,endi在int范围内

### 题解代码 ###

import java.util.*;
    public class Solution {
        public int minmumNumberOfHost (int n, int[][] startEnd) {
            int[] start = new int[n];
            int[] end = new int[n];
            //分别得到活动起始时间 fast-template
            for(int i = 0; i < n; i++){
                start[i] = startEnd[i][0];
                end[i] = startEnd[i][1];
            }
            //单独排序
            Arrays.sort(start, 0, start.length);
            Arrays.sort(end, 0, end.length);
            int res = 0;
            int j = 0;
            for(int i = 0; i < n; i++){
                //新开始的节目大于上一轮结束的时间，主持人不变
                if(start[i] >= end[j])
                    j++;
                else
                    //主持人增加
                    res++;
            }
            return res;}
    }

> 算法对程序员来说及其重要，语言和开发平台不断变化，但是万变不离其宗的是那些算法和理论，依稀记得我那个玩的很好的一个学长（在大二就拿到了 offer），他告诉我想找一个好的工作，那刷题一定是必不可少的
> 
> 现在算法刷题平台还是蛮多的，给大家介绍一个我认为与大厂关联最深的平台——[牛客网][Link 3]

[Link 1]: https://blog.csdn.net/aasd23?spm=1000.2115.3001.5343
[Link 2]: https://blog.csdn.net/aasd23/category_11805404.html?spm=1001.2014.3001.5482
[Link 3]: https://www.nowcoder.com/link/pc_csdncpt_cxyz_sf
[902eb55e5c7a4bea82451ce2b53e334e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/23/be0ef533121a4b90bbf634f503d67815.png