代码随想录算法训练营第三十一天| 理论基础,455.分发饼干, 376. 摆动序列,53. 最大子序和

本文主要是介绍代码随想录算法训练营第三十一天| 理论基础,455.分发饼干, 376. 摆动序列,53. 最大子序和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 题目与题解

参考资料:贪心算法理论基础

455.分发饼干

题目链接:455.分发饼干

代码随想录题解:455.分发饼干

视频讲解:贪心算法,你想先喂哪个小孩?| LeetCode:455.分发饼干_哔哩哔哩_bilibili

解题思路:

        先对小孩胃口g和饼干分量s进行排序,然后对于小孩的胃口,从小到大分配饼干。如果当前饼干不能满足当前小孩胃口,就继续看下一个饼干是否能满足,否则已满足胃口的小孩数量加一,继续看下一个饼干能否满足下一个小孩的胃口。

class Solution {public int findContentChildren(int[] g, int[] s) {int max = 0;Arrays.sort(g);Arrays.sort(s);int i = 0, j = 0;while (i < g.length && j < s.length) {if (s[j] >= g[i]) {max++;i++;j++;} else {j++;}}return max;}
}

看完代码随想录之后的想法 

        这里的局部最优就是大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个,全局最优就是喂饱尽可能多的小孩。也可以换一个思路,小饼干先喂饱小胃口,也就是我写的思路。

class Solution {// 思路2:优先考虑胃口,先喂饱大胃口public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count = 0;int start = s.length - 1;// 遍历胃口for (int index = g.length - 1; index >= 0; index--) {if(start >= 0 && g[index] <= s[start]) {start--;count++;}}return count;}
}

遇到的困难

        说实话感觉写的时候是瞎写的竟然也能过,非常迷茫。。贪心确实没什么套路。

376. 摆动序列

题目链接:376. 摆动序列

代码随想录题解:376. 摆动序列

视频讲解:贪心算法,寻找摆动有细节!| LeetCode:376.摆动序列_哔哩哔哩_bilibili

解题思路:

        有些复杂,写不对,看答案

看完代码随想录之后的想法 

        这题的本质是求有多少个波峰和波谷,峰谷之间的元素都可以忽略。所以只要当前元素跟前后元素之差一正一负,说明该元素就是波峰或者波谷元素,统计即可。        

但本题要考虑三种情况:

  1. 情况一:上下坡中有平坡
  2. 情况二:数组首尾两端
  3. 情况三:单调坡中有平坡
class Solution {public int wiggleMaxLength(int[] nums) {if (nums.length <= 1) {return nums.length;}//当前差值int curDiff = 0;//上一个差值int preDiff = 0;int count = 1;for (int i = 1; i < nums.length; i++) {//得到当前差值curDiff = nums[i] - nums[i - 1];//如果当前差值和上一个差值为一正一负//等于0的情况表示初始时的preDiffif ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {count++;preDiff = curDiff;}}return count;}
}

遇到的困难

        要把这道题抽象成波峰波谷的计算就很难了,实在是写不出来,就看看吧。

53. 最大子序和

题目链接:53. 最大子序和

代码随想录题解:53. 最大子序和

视频讲解:贪心算法的巧妙需要慢慢体会!LeetCode:53. 最大子序和_哔哩哔哩_bilibili

解题思路:

        无

看完代码随想录之后的想法 

        局部最优:当前“连续和”为负数的时候立刻放弃,从下一个元素重新计算“连续和”,因为负数加上下一个元素 “连续和”只会越来越小。

        全局最优:选取最大“连续和”

计算过程中sum会不断更新,所以要用result实时记录最大的序列和,最后输出result即可。这样写,即使所有的sum都小于0,最后得到的也一定是数组中最大的数,即最靠近0的负数。

class Solution {public int maxSubArray(int[] nums) {int sum = 0;int result = Integer.MIN_VALUE;for (int i = 0; i < nums.length; i++) {sum += nums[i];if (sum > result) result = sum;if (sum <= 0) sum = 0;}return result;}
}

遇到的困难

        真的想不到,摆了

今日收获

        贪心很难,一是难在想到题目要用贪心算法,二是难在不知道如何找局部最优以获得全局最优。暂时只能靠记了。

这篇关于代码随想录算法训练营第三十一天| 理论基础,455.分发饼干, 376. 摆动序列,53. 最大子序和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/878662

相关文章

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Java中&和&&以及|和||的区别、应用场景和代码示例

《Java中&和&&以及|和||的区别、应用场景和代码示例》:本文主要介绍Java中的逻辑运算符&、&&、|和||的区别,包括它们在布尔和整数类型上的应用,文中通过代码介绍的非常详细,需要的朋友可... 目录前言1. & 和 &&代码示例2. | 和 ||代码示例3. 为什么要使用 & 和 | 而不是总是使

Java强制转化示例代码详解

《Java强制转化示例代码详解》:本文主要介绍Java编程语言中的类型转换,包括基本类型之间的强制类型转换和引用类型的强制类型转换,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录引入基本类型强制转换1.数字之间2.数字字符之间引入引用类型的强制转换总结引入在Java编程语言中,类型转换(无论

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque