代码随想录算法训练营第23期day31|贪心算法理论基础、455.分发饼干、376. 摆动序列、53. 最大子序和
目录
一、贪心算法理论基础
二、(leetcode 455)分发饼干
三、(leetcode 376)摆动序列
四、(leetcode 53)最大子序和
一、贪心算法理论基础
1.什么是贪心
贪心的本质是选择每一阶段的局部最优,从而达到全局最优。
2.贪心一般解题步骤
贪心算法一般分为如下四步:
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
这个四步其实过于理论化了,我们平时在做贪心类的题目,做题的时候,只要想清楚局部最优是什么,如果推导出全局最优,其实就够了。
二、(leetcode 455)分发饼干
力扣题目链接
状态:已AC
解题思路是从胃口小的先开始满足
class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {// 贪心的思想,想要满足最多的孩子,就要先从胃口小的孩子开始sort(g.begin(), g.end());sort(s.begin(), s.end());int index = 0;for(int i = 0; i < s.size(); ++i){if(index < g.size() && g[index] <= s[i]){index++;}}return index;}
};
三、(leetcode 376)摆动序列
力扣题目链接
状态:没有思路。
这道题如果是在没有做过的情况下遇到,首先想到的方法(常规解法)应该是动态规划:
设 dp 状态dp[i][0],表示考虑前 i 个数,第 i 个数作为山峰的摆动子序列的最长长度
设 dp 状态dp[i][1],表示考虑前 i 个数,第 i 个数作为山谷的摆动子序列的最长长度
动态规划的初始状态:dp[0][0] = dp[0][1] = 1,转移方程:
dp[i][0] = max(dp[i][0], dp[j][1] + 1),其中0 < j < i且nums[j] < nums[i],表示将 nums[i]接到前面某个山谷后面,作为山峰。
dp[i][1] = max(dp[i][1], dp[j][0] + 1),其中0 < j < i且nums[j] > nums[i],表示将 nums[i]接到前面某个山峰后面,作为山谷。
class Solution {
public:int dp[1005][2];int wiggleMaxLength(vector<int>& nums) {memset(dp, 0, sizeof dp);dp[0][0] = dp[0][1] = 1;for (int i = 1; i < nums.size(); ++i) {dp[i][0] = dp[i][1] = 1;for (int j = 0; j < i; ++j) {if (nums[j] > nums[i]) dp[i][1] = max(dp[i][1], dp[j][0] + 1);}for (int j = 0; j < i; ++j) {if (nums[j] < nums[i]) dp[i][0] = max(dp[i][0], dp[j][1] + 1);}}return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);}
};
这道题还有优化的空间,就是使用贪心算法,使用贪心算法要考虑三种情况
- 情况一:上下坡中有平坡
- 情况二:数组首尾两端
- 情况三:单调坡中有平坡
class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if(nums.size() <= 1) return nums.size();int curDiff = 0;int preDiff = 0;int res = 1;for(int i = 0; i < nums.size()-1; ++i){curDiff = nums[i+1] - nums[i];if((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff <0)){res++;preDiff = curDiff;}}return res;}
};
四、(leetcode 53)最大子序和
力扣题目链接
状态:暴力解法超时。
局部最优:当前“连续和”为负数的时候立刻放弃,从下一个元素重新计算“连续和”,因为负数加上下一个元素 “连续和”只会越来越小。全局最优:选取最大“连续和”
局部最优的情况下,并记录最大的“连续和”,可以推出全局最优。
class Solution {
public:int maxSubArray(vector<int>& nums) {int res = INT_MIN;int count = 0;int len = nums.size();for(int i = 0; i < len; ++i){count += nums[i];if(count > res){res = count;}if(count <= 0) count = 0;}return res;}
};相关文章:
代码随想录算法训练营第23期day31|贪心算法理论基础、455.分发饼干、376. 摆动序列、53. 最大子序和
目录 一、贪心算法理论基础 二、(leetcode 455)分发饼干 三、(leetcode 376)摆动序列 四、(leetcode 53)最大子序和 一、贪心算法理论基础 1.什么是贪心 贪心的本质是选择每一阶段的局部最优…...
mdadm命令详解及实验过程
mdadm命令详解及实验过程 ⼀.概念 mdadm是multiple devices admin的简称,它是Linux下的⼀款标准的软件 RAID 管理⼯具,作者是Neil Brown ⼆.特点 mdadm能够诊断、监控和收集详细的阵列信息 mdadm是⼀个单独集成化的程序⽽不是⼀些分散程序的集合&#…...
推荐几个程序员必逛的个人技术博客网站
1、美团技术团队 地 址: 美团技术团队简 介:美团技术团队的博客,干货满满。推荐指数:⭐⭐⭐⭐⭐ 2、阮一峰的网络日志 地 址: 阮一峰的个人网站 - Ruan YiFengs Personal Website简 介:大神阮一峰,博客风格真正…...
Python桌面应用之XX学院水卡报表查询系统(Tkinter+cx_Oracle)
一、功能样式 Python桌面应用之XX学院水卡报表查询系统功能: 连接Oracle数据库,查询XX学院水卡操作总明细报表,汇总数据报表,个人明细报表,进行预览并且支持导出报表 1.总明细报表样式 2.汇总明细样式 3.个人明细…...
ubuntu 中使用Qt连接MMSQl,报错libqsqlodbc.so: undefined symbol: SQLAllocHandle
Qt4.8.7的源码编译出来的libqsqlodbc.so,在使用时报错libqsqlodbc.so: undefined symbol: SQLAllocHandle,需要在编译libqsqlodbc.so 的项目pro文件加上LIBS -L/usr/local/lib -lodbc。 这里的路径根据自己的实际情况填写。 编辑: 使用uni…...
笔试,猴子吃香蕉,多线程写法
package demo;import java.util.concurrent.CountDownLatch;/*** description: 猴子吃香蕉* author: wxm* create: 2023-10-23 14:01**/ public class Main {public static void main(String[] args) throws InterruptedException {Monkey[] m new Monkey[3];Resource r new …...
安装docker ,更换docker版本
docker dockerd & containerd Dockerd(Docker 守护进程)在其底层使用 Containerd 来管理容器。Containerd 是一个开源的容器运行时管理器,由 Docker 公司于2017年开发并开源,它负责实际的容器生命周期管理。 以下是 Docker 守…...
英语小作文写作模板及步骤(1)
...
编写hello驱动程序
hello的驱动编写 编写驱动程序的步骤 1.确定主设备号,也可以让内核分配 2.定义自己的 file_operations 结构体 3.实现对应的 drv_open/drv_read/drv_write 等函数,填入 file_operations 结构 体 4.把 file_operations 结构体告诉内核:regist…...
ZYNQ中断例程
GPIO 中断系统初始化流程: 第一步:初始化 cpu 的异常处理功能 第二步:初始化中断控制器 第三步:向 CPU 注册异常处理回调函数; 第四步:将中断控制器中的对应中断 ID 的中断与中断控制器相连接 第五步:设置 …...
常用linux命令 linux_cmd_sheet
查看文件大小 ls -al 显示每个文件的kb大小 查看系统日志 dmesg -T | tail 在 top 命令中,RES 和 VIRT(或者 total-vm)是用来表示进程内存使用的两个不同指标,它们之间有以下区别: RES(Resident Set Size…...
【proteus】8086 写一个汇编程序并调试
参考书籍:微机原理与接口技术——基于8086和Proteus仿真(第3版)p103-105,p119-122. 参考程序是p70,例4-1 在上一篇的基础上: 创建项目和汇编文件 写一个汇编程序并编译 双击8086的元件图: …...
大数据之LibrA数据库常见术语(四)
Failover 指当某个节点出现故障时,自动切换到备节点上的过程。反之,从备节点上切换回来的过程称为Failback。 Freeze 在事务ID耗尽时由AutoVacuum Worker进程自动执行的操作。FusionInsight LibrA会把事务ID记在行头,在一个事务取得一行时&…...
Docker基础知识
文章目录 Docker Docker 一次构建,处处运行,类似于JVM 虚拟机是软件硬件(需要Hypervisors实现硬件资源虚拟化): 资源占用大启动慢(虚拟机是分钟级,Docker是秒级)冗余步骤多 sha2…...
swoole 是什么?
Swoole是一个为PHP用C和C编写的基于事件的高性能异步& 协程并行网络通信引擎; 使 PHP 开发人员可以编写高性能的协程 TCP、UDP、Unix Socket、HTTP,WebSocket 服务。Swoole 可以广泛应用于互联网、移动通信、企业软件、云计算、网络游戏、物联网(IO…...
我想要一个勋章
目录 一、背景二、过程三、总结 一、背景 十年前结缘,也许是冥冥中自有天注定,注定要给自己多加一个今天的节日。 二、过程 一个勋章,一个有意义的标志。 一个勋章,一个时间轮上的帧。 一个勋章,一个二进制的节点。…...
微信小程序设计之主体文件app-json-pages
一、新建一个项目 首先,下载微信小程序开发工具,具体下载方式可以参考文章《微信小程序开发者工具下载》。 然后,注册小程序账号,具体注册方法,可以参考文章《微信小程序个人账号申请和配置详细教程》。 在得到了测…...
C语言-面试题实现有序序列合并
要求: a.输入两个升序排列的序列,将两个序列合并为一个有序序列并输出。 数据范围: 1≤n,m≤1000 1≤n,m≤1000 , 序列中的值满足 0≤val≤30000 输入描述: 1.输入包含三行, 2.第一行包含两个正整数n, m&am…...
Android12 启动页适配
印象中,在2022年末接到了一个针对Android12启动页适配的需求,当时也使用了一些适配方案,也写了一个Demo,但是最终没有付诸适配行动;当然并不是适配失败,而是根据官方适配方案适配后太丑了… 1024纪念文章&a…...
【微服务保护】初识 Sentinel —— 探索微服务雪崩问题的解决方案,Sentinel 的安装部署以及将 Sentinel 集成到微服务项目
文章目录 前言一、雪崩问题及其解决方案1.1 什么是雪崩问题1.2 雪崩问题的原因1.3 解决雪崩问题的方法1.4 总结 二、初识 Sentinel 框架2.1 什么是 Sentinel2.2 Sentinel 和 Hystrix 的对比 三、Sentinel 的安装部署四、集成 Sentinel 到微服务 前言 微服务架构在现代软件开发…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
