贪心算法练习day.1

news/2024/5/18 15:57:58

理论基础

贪心算法是一种常见的解决优化问题的方法,其基本思想就是在问题的每个决策阶段,都选择当前看起来最优的选择,即贪心地做出局部的最优决策,以此得到全局的最优解,例如在十张面额不同的钞票,让我们去取5张,那如何拿到最多的钱呢?那我们每次取钞票时只需要取出面额最大的一张(局部最优),最后拿到的就是最多的钱(全局最优),这就是贪心的策略

贪心算法优点和局限性:

优点:操作直接,实现简单,效率高

局限性:有时候并不能找到最优解,即无法保证能找到最优解,可能找到较差的解

贪心算法主要适用于以下两种情况

1.可以保证找到最优解:在这种情况下贪心算法是最优选择,因为它比回溯算法,动态规划更加高效

2.可以找到近似最优解:贪心算法在这种情况下也可以使用,对于很多问题而言,找到最优解很难,那么能够高效的查找到次优解也很不错

贪心算法的解决流程:

1.对问题进行分析

2.确定贪心的策略

3.证明正确性

455.分发饼干

链接:. - 力扣(LeetCode)

题目描述:

相关标签

相关企业

假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。

对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

示例 1:

输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。
虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。
所以你应该输出1。

示例 2:

输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.

提示:

  • 1 <= g.length <= 3 * 104
  • 0 <= s.length <= 3 * 104
  • 1 <= g[i], s[j] <= 231 - 1

思路:

因为饼干不能分开,因此我们不能用大饼干去喂喂口小的孩子,会造成饼干的浪费,因此我们的局部最优应该是每次找到一个大饼干,尽量去喂胃口大的孩子,全局最优就是可以喂饱最多的孩子,投喂过程如下图所示

我们需要先对孩子和饼干进行排序,便于我们找到胃口最多的小孩已经最大的饼干,因为我们的局部最优是拿最大的饼干喂胃口最大的孩子,所以只有当我们投喂成功时,才能进行下一块饼干的投喂,即如图所示,大小为9的饼干喂不了胃口为10的孩子,我们只有把大小为9的饼干喂给大小为7的孩子,才能进行下一次饼干的投喂,即大小为5的饼干

代码如下:

int cmp(int *a, int *b)
{return *a - *b;
}int findContentChildren(int* g, int gSize, int* s, int sSize) {if(gSize == 0)return 0;qsort(g, gSize,sizeof(int), cmp);qsort(s, sSize,sizeof(int), cmp);int child = 0;int index = sSize - 1;for(int i = gSize - 1; i >= 0 ; --i){while( index >= 0 && s[index] >= g[i] ){child++;index--;break;}}return child;
}

376.摆动序列

链接:. - 力扣(LeetCode)

题目描述:

如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

  • 例如, [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ,因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

  • 相反,[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。

给你一个整数数组 nums ,返回 nums 中作为 摆动序列 最长子序列的长度

示例 1:

输入:nums = [1,7,4,9,2,5]
输出:6
解释:整个序列均为摆动序列,各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2:

输入:nums = [1,17,5,10,13,15,10,5,16,8]
输出:7
解释:这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ,各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

示例 3:

输入:nums = [1,2,3,4,5,6,7,8,9]
输出:2

提示:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

思路:

我们可以根据题目进行分析,如下图所示,有三种情况,以第一种为例,上下坡

红色所标注的就是摆动,蓝色所标注的摆动的最长子序列,即为7,根据图形我们可以看出,我们的每一个峰值都是一个摆动序列,因此我们可以将不是峰值的数值进行删除,即删除单调坡上的元素,即其中蓝色X表示标注的元素,这就是局部最优,剩下的数组元素的个数就是我们摆动的序列的最长子序列,这就是全局最优

注意:因为题目要求返回的是摆动序列的最长子序列的长度,因此我们不需要实际进行删除的操作,只需要在遇到摆动时将其记录就可以

第二种情况,上下坡带有平坡

第三种情况,单调坡有平坡

代码如下:

int wiggleMaxLength(int* nums, int numsSize){// 如果数组只有一个元素,则返回1,因为一个元素本身就构成了一个摆动序列if(numsSize == 1)return 1;// 如果数组只有两个元素且两个元素不相等,则返回2,因为两个不相等的元素构成了一个摆动序列if(numsSize == 2 && nums[0] != nums[1])return 2;int cur = 0, pre = 0;int result = 1;// 遍历数组,计算相邻元素之间的差值,根据差值的符号确定摆动序列for(int i = 0; i < numsSize - 1; i++){// 当前元素与下一个元素的差值cur = nums[i + 1] - nums[i];// 如果前一个差值为非负数且当前差值为负数,或者前一个差值为非正数且当前差值为正数,// 则说明出现了摆动,摆动序列长度加一,并更新前一个差值if((pre >= 0 && cur < 0) || (pre <= 0 && cur > 0)){result++;pre = cur;}}return result;
}

53.最大子数组和

链接:. - 力扣(LeetCode)

题目描述:

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

子数组

是数组中的一个连续部分。

示例 1:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

示例 2:

输入:nums = [1]
输出:1

示例 3:

输入:nums = [5,4,-1,7,8]
输出:23

提示:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

贪心思路:

我们在遍历数组时,需要一个变量不断去累加数组元素,如果当前的连续和是负数,,继续不断的相加只能让连续和变小,此时不如将我们新的数组元素作为连续和新的开始,因此我们就得出我们的局部最优,当求得连续和为负数,则直接抛弃它,并选择数组的下一个元素作为新的连续和起点,当我们得到连续和是正数,则进行保留,因为无论这个整数是大还是小,对数组后面的元素都只有增大的作用(遇到正数增大,遇到负数抵消部分影响),并且将这个值再进行记录,大致过程就如下所示

连续和为负数,则抛弃,连续和为正数,则进行最大连续和记录,一直遍历到数组为空

代码实现:

int maxSubArray(int* nums, int numsSize) {int result = INT_MIN;int sum = 0;for(int i = 0; i < numsSize ;i++){sum += nums[i];result = sum > result ? sum : result;sum = sum < 0 ? 0 : sum;}return result;
}


http://www.mrgr.cn/p/04147633

相关文章

解决方案 SHUTDOWN_STATE xmlrpclib.py line: 794 ERROR: supervisor shutting down

Supervisor操作命令 重新加载 Supervisor 配置&#xff1a; sudo supervisorctl reread sudo supervisorctl update sudo supervisorctl restart all这将重新读取 Supervisor 的配置文件&#xff0c;更新进程组&#xff0c;然后重启所有进程。 查看 Supervisor 日志&#xff1…

踏上R语言之旅:解锁数据世界的神秘密码(二)

R语言学习 文章目录 R语言学习1.数据的R语言表示2.多元数据的R语言调用3.多元数据的简单R语言分析4.多元数据的直观表示及R使用 总结 1.数据的R语言表示 数据框&#xff08;data frame) R语言中用函数data.frame()生成数据框&#xff0c;其句法是&#xff1a; data.frame(data…

防反接、防过压、缓启动电路相关

一、防反接电路 电源正确接入时 电流从 VIN 端流向负载&#xff0c;经由 Q3(NMOS) 通向地&#xff08;GND&#xff09;。在上电瞬间&#xff0c;由于 MOS 管的体二极管效应&#xff0c;地回路通过体二极管接通。接下来&#xff0c;由于 Vgs(门源电压)大于 Vgsth(门限电压)&…

Flutter 的 showDialog 和 showCupertinoDialog 有什么区别?

我将我的 App 里用的 Flutter 升级到了 3.19&#xff0c;没想到&#xff0c;以前我用 showDialog 和 AlertDialog 组合创建的二次确认框&#xff0c;变得无敌难看了&#xff0c;大幅度增加了整个框的圆角和里面默认按钮的圆角。不得已&#xff0c;我必须修改一下&#xff0c;以…

ROM修改进阶教程------安卓7_____安卓13去除签名验证操作步骤解析

同类博文: 安卓玩机搞机技巧综合资源-----修改rom 制作rom 解包rom的一些问题解析【二十一】_qcn改区域锁-CSDN博客 安卓系列机型rom修改。如果你删减了系统相关的app。那么严重会导致开机系统卡米 定屏等问题。这类一般都是系统签名验证导致的。而破解签名验证一般都是修改…

通用目标近似程序的神经加速

通用目标近似程序的神经加速 参考文献链接 https://homes.cs.washington.edu/~luisceze/publications/micro12-web.pdf人工智能芯片与自动驾驶

软文发稿对于企业的重要性

随着社会的发展和科技的进步&#xff0c;软文发稿已成为企业和个人推广和传播信息的一种非常重要的方式。它以隐性的广告形式&#xff0c;通过内容发布&#xff0c;为品牌广告和产品推广铺设了一条隐形高速公路。下面我们就详细解析一下软文发稿的优点和好处。 软文发稿帮助增…

深入探索:Facebook如何重塑社交互动

在当代社会中&#xff0c;社交互动已成为日常生活的核心组成部分。而在众多的社交媒体平台中&#xff0c;Facebook凭借其卓越的用户基础和创新的功能&#xff0c;已经成为了全球最大的社交媒体平台。本文将深入探讨Facebook如何通过其独特的特性和功能&#xff0c;重塑了人们的…

Linux进程详解二:创建、状态、进程排队

文章目录 进程创建进程状态进程排队 进程创建 pid_t fork(void) 创建一个子进程成功将子进程的pid返回给父进程&#xff0c;0返回给新创建的子进程 fork之后有两个执行分支&#xff08;父和子&#xff09;&#xff0c;fork之后代码共享 bash -> 父 -> 子 创建一个进…

mmcv bug记录

图像分类任务要用到mmcv框架&#xff0c;记录遇到的问题 1. Can‘t import build_from_cfg from mmcv. 解决命令&#xff1a;pip install openmim && mim install mmcv-full 2. python分布式训练 解决方案&#xff1a; 租用多张A40卡&#xff0c;执行下述命令&…

Keil MDK6 使用标准库出现 error: no member named IP in NVIC_Type 原因和解决

出现错误: error: no member named IP in NVIC_Type131 | NVIC->IP[NVIC_InitStruct->NVIC_IRQChannel] = tmppriority;| ~~~~ ^时间:2024-4-24 3:05 编辑器: vscode 扩展:Keil Studio Pack (MDK v6)packs:- pack: Keil::STM32F1xx_DFP@2.4.1- pack: ARM::CM…

Git 核心概念与实操

这里写目录标题 1 版本回退2 工作区、暂存区、本地仓库、远程仓库 1 版本回退 原文链接&#xff1a;https://www.liaoxuefeng.com/wiki/896043488029600/897013573512192 首先 git log 查看提交记录 在Git中&#xff0c;用 HEAD 表示当前版本 上一个版本就是 HEAD^ &#xff…

7.2K star!一个完全免费,可以本地部署的 AI 搜索聚合器。新手可尝试

原文链接&#xff1a;7.2K star&#xff01;一个完全免费&#xff0c;可以本地部署的 AI 搜索聚合器。新手可尝试 ChatGPT 刚上线的时候我用的很少&#xff0c;还是习惯用 Google。主要还是因为不信任&#xff0c;怕它对我胡说八道。 慢慢的&#xff0c;也没有一个明确的时间…

js some对比forEach

some&#xff1a;return true可以停止循环 forEach&#xff1a;return true无法停止循环 <!DOCTYPE html> <html ng-app"my_app"><head><script type"text/javascript">const array [10, 20, 30];const targetValue 10;// 检测…

多项式和Bezier曲线拟合

目录 1. 多项式拟合2. Bezier曲线拟合3. 源码地址 1. 多项式拟合 在曲线拟合中&#xff0c;多项式拟合方法的性能受到三个主要因素的影响&#xff1a;采样点个数、多项式阶数和正则项。 采样点个数 N N N&#xff1a;从Figure 1中可以看出较少的采样点个数可能导致过拟合&…

MySQL从入门到高级 --- 2.DDL基本操作

文章目录 第二章&#xff1a;2.基本操作 - DDL2.1 数据库的常用操作创建数据库选择要操作的数据库删除数据库修改数据库编码 2.2 表结构的常用操作创建表格式查看当前数据库的所有表名称查看指定某个表的创建语句查看表结构删除表 2.3 修改表结构添加列修改列名和类型删除列修改…

Docker 基本认识

一 国内&#xff1a; 中国电信天翼云 提供包括云主机在内的全方位云计算服务&#xff0c;侧重于安全合规和企业级服务。 利用电信的网络优势&#xff0c;提供稳定可靠的基础设施服务。 中国联通沃云 提供包括云主机在内的多项云计算服务&#xff0c;适合不同行业和场景。 …

k8s学习(三十六)centos下离线部署kubernetes1.30(单主节点)

文章目录 服务器准备工作一、升级操作系统内核1 查看操作系统和内核版本2 下载内核离线升级包3 升级内核4 确认内核版本 二、修改主机名/hosts文件1 修改主机名2 修改hosts文件 三、关闭防火墙四、关闭SELINUX配置五、时间同步1 下载NTP2 卸载3 安装4 配置4.1 主节点配置4.2 从…

使用Jest测试框架测试JS项目

前言 JavaScript的测试框架有很多&#xff0c;这里主要记录一些自己在初次使用jest时遇到的一些问题。详细使用文档可以参照官方说明文档。 简介 Jest 是一款优雅、简洁的 JavaScript 测试框架。 Jest 支持 Babel、TypeScript、Node、React、Angular、Vue 等诸多框架&#…

Jenkins打包app并通过openssh上传到服务器

目录 1、下载安装openssh 2、配置openssh根目录 3、安装Jenkins Build Steps配置 Post-build Actions配置 4、运行 1、下载安装openssh 网上很多教程&#xff0c;包括开端口的&#xff0c;可以搜下 2、配置openssh根目录 进入C:\ProgramData\ssh打开文件sshd_config&am…