算法刷题Day31 | 455.分发饼干、376. 摆动序列、53. 最大子数组和

2024-04-12 11:28

本文主要是介绍算法刷题Day31 | 455.分发饼干、376. 摆动序列、53. 最大子数组和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 0 引言
  • 1 分发饼干
    • 1.1 我的解题
    • 1.2 更好的解题
  • 2 摆动序列
    • 2.1 我的解题
    • 2.2 我的错误原因(GPT分析)
    • 2.3 改进
  • 3 最大子数组和
    • 3.1 我的解题

请添加图片描述

  • 🙋‍♂️ 作者:海码007
  • 📜 专栏:算法专栏
  • 💥 标题:算法刷题Day31 | 455.分发饼干、376. 摆动序列、53. 最大子序和
  • ❣️ 寄语:书到用时方恨少,事非经过不知难!

0 引言

贪心算法一般分为如下四步:

  1. 将问题分解为若干子问题
  2. 找出适合的贪心策略
  3. 求解每一个子问题的最优解
  4. 将局部最优解堆叠成全局最优解

这个四步其实过于理论化了,我们平时在做贪心类的题目 很难去按照这四步去思考,真是有点“鸡肋”。
做题的时候,只要想清楚 局部最优 是什么,如果推导出全局最优,其实就够了。

1 分发饼干

  • 🎈 文档讲解
  • 🎈 视频讲解
  • 🎈 做题状态:

1.1 我的解题

我的想法,遍历饼干,然后再从大到小遍历孩子的胃口。找到刚好匹配的数就结果加一,然后把这个胃口数据移除。

#include <algorithm>class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {int count = 0;// 先将数组排序sort(g.begin(), g.end());sort(s.begin(), s.begin());// 初步思考,使用两层循环遍历,先遍历饼干,再遍历胃口for (int i = 0; i < s.size(); i++){for (int j = g.size()-1; j >= 0; j--){if (s[i] < g[j]){continue;}else{count++;g.erase(g.begin() + j);break;}}}return count;}
};

1.2 更好的解题

只用了一个循环模拟了胃口和饼干的同时遍历。
先遍历大饼干,先满足胃口大的小孩。

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int index = s.size() - 1; // 饼干数组的下标int result = 0;for (int i = g.size() - 1; i >= 0; i--) { // 遍历胃口if (index >= 0 && s[index] >= g[i]) { // 遍历饼干result++;index--;}}return result;}
};

2 摆动序列

  • 🎈 文档讲解
  • 🎈 视频讲解
  • 🎈 做题状态:

2.1 我的解题

其实本题只需要画图搞清楚一个条件即可,一定要取极大值作为转折点。这样摆动的序列才是最长的。然后本题还有个比较麻烦的地方是平坡,也就是相邻点的值相等。这样也不好判断。为了便于理解,可以先遍历一遍数组将相同的点去除,然后再求解。这样就简单很多。
当然也可以通过条件判断的方式不记录平坡,然后判断非平坡情况下是否为满足条件。

本题难点:
是求的子序列,子序列的话是可以从原始序列中删除元素的。所以比较难判断。

下面是我的错误代码。

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if (nums.size() == 1) return 1;if (nums.size() == 2 && nums[0] != nums[1]) return 2;int count = 2;int maxCount = count;// 此时数组个数大于等于3for (int i = 2; i < nums.size(); i++){int diff1 = nums[i] - nums[i-1];int diff2 = nums[i-1] - nums[i-2];// cout << "diff1 = " << diff1 << endl;// cout << "diff2 = " << diff2 << endl;if ((diff > 0 && prevDiff < 0) || (diff < 0 && prevDiff > 0)){if (diff1 != 0 && diff2 != 0){count++;}}else{// 如果不满足则count重置为2,同时将不满足的数给删除//count = 2;nums.erase(nums.begin() + i - 1);i--;}maxCount = max(maxCount, count);cout << "count = " << count << endl;}return maxCount;}
};

2.2 我的错误原因(GPT分析)

您的代码试图解决的问题是寻找给定数组中最长的摆动子序列的长度。摆动序列被定义为序列中的数字交替大于和小于其前一个数字。您的实现逻辑有几个关键的缺陷和改进点:

  1. 数组修改: 您尝试通过删除不符合摆动序列条件的元素来维护摆动序列,这不仅改变了原数组,而且并不是解决这个问题的有效方法。在寻找最长摆动序列时,我们并不需要修改原数组,而是应该寻找一种方式来识别摆动序列的长度而不实际改变数组内容。

  2. 摆动序列的识别: 您的逻辑试图通过比较当前元素与前两个元素的差来确定是否构成摆动。虽然这种思路基本正确,但其实现方式过于复杂,且erase操作导致时间复杂度增加。此外,您的条件检查(diff1 == abs(diff1) && diff2 == -abs(diff2) || diff2 == abs(diff2) && diff1 == -abs(diff1))可以简化为检查diff1diff2的符号是否相反。

  3. 初始化问题: 初始的count设置为2是基于至少存在一对不同的元素。如果数组开始就有连续相等的元素,这种初始化是不准确的。

为了改进您的代码,可以采取以下策略:

  • 初始化时考虑特殊情况: 首先处理只有一个元素或所有元素都相等的情况。
  • 使用状态变量: 记录最后一次摆动是上升还是下降,而不是每次都检查三个元素。
  • 避免修改原数组: 直接通过遍历原数组来判断每一步是否构成摆动,不需要修改原数组。

下面是一个改进后的实现示例:

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int n = nums.size();if (n < 2) return n;// 初始化计数器和方向int count = 1; // 至少有一个元素,所以从1开始计数int prevDiff = 0;for (int i = 1; i < n; ++i) {int diff = nums[i] - nums[i-1];if ((diff > 0 && prevDiff <= 0) || (diff < 0 && prevDiff >= 0)) {// 发现摆动,增加计数并更新prevDiffcount++;prevDiff = diff;}}return count;}
};

这个实现不修改原数组,通过遍历数组一次,比较相邻元素之差来判断摆动,并且只在摆动方向发生变化时增加计数器。这种方式更为简洁且效率更高。

2.3 改进

不能将峰值删除,相当于求极值点有几个。看了视频发现有平坡的情况需要很多特殊讨论,那么可不可以直接把数据的平坡给去除呢?然后再来做题。使用遍历把相邻相同的数据给去除。

3 最大子数组和

  • 🎈 文档讲解
  • 🎈 视频讲解
  • 🎈 做题状态:

3.1 我的解题

首先明确思路:
最大和的子数组,然后每次移动记录数组和,如果遇到sum小于0,则可以直接将sum置为0,然后从后面遇到的第一个正数开始记录。

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = nums[0];int sum = 0;for (int i = 0; i < nums.size(); i++){sum += nums[i];result = max(result, sum);if (sum <= 0){sum = 0;}}return result;}
};

这篇关于算法刷题Day31 | 455.分发饼干、376. 摆动序列、53. 最大子数组和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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

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

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

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

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

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::