算法刷题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

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

uva 10131 最长子序列

题意: 给大象的体重和智商,求体重按从大到小,智商从高到低的最长子序列,并输出路径。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vect