当前位置: 首页 > news >正文

代码随想录-算法训练营day31【贪心算法01:理论基础、分发饼干、摆动序列、最大子序和】

代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客

第八章 贪心算法 part01● 理论基础 
● 455.分发饼干 
● 376. 摆动序列 
● 53. 最大子序和 贪心算法其实就是没有什么规律可言,所以大家了解贪心算法 就了解它没有规律的本质就够了。 不用花心思去研究其规律, 没有思路就立刻看题解。基本贪心的题目 有两个极端,要不就是特简单,要不就是死活想不出来。  学完贪心之后再去看动态规划,就会了解贪心和动规的区别。详细布置 理论基础 https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html  455.分发饼干  https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html  376. 摆动序列  https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html  53. 最大子序和  https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html  往日任务
● day 1 任务以及具体安排:https://docs.qq.com/doc/DUG9UR2ZUc3BjRUdY  
● day 2 任务以及具体安排:https://docs.qq.com/doc/DUGRwWXNOVEpyaVpG  
● day 3 任务以及具体安排:https://docs.qq.com/doc/DUGdqYWNYeGhlaVR6 
● day 4 任务以及具体安排:https://docs.qq.com/doc/DUFNjYUxYRHRVWklp 
● day 5 周日休息
● day 6 任务以及具体安排:https://docs.qq.com/doc/DUEtFSGdreWRuR2p4 
● day 7 任务以及具体安排:https://docs.qq.com/doc/DUElCb1NyTVpXa0Jj 
● day 8 任务以及具体安排:https://docs.qq.com/doc/DUGdsY2JFaFhDRVZH 
● day 9 任务以及具体安排:https://docs.qq.com/doc/DUHVXSnZNaXpVUHN4 
● day 10 任务以及具体安排:https://docs.qq.com/doc/DUElqeHh3cndDbW1Q 
●day 11 任务以及具体安排:https://docs.qq.com/doc/DUHh6UE5hUUZOZUd0 
●day 12 周日休息 
●day 13 任务以及具体安排:https://docs.qq.com/doc/DUHNpa3F4b2dMUWJ3 
●day 14 任务以及具体安排:https://docs.qq.com/doc/DUHRtdXZZSWFkeGdE 
●day 15 任务以及具体安排:https://docs.qq.com/doc/DUHN0ZVJuRmVYeWNv 
●day 16 任务以及具体安排:https://docs.qq.com/doc/DUHBQRm1aSWR4T2NK 
●day 17 任务以及具体安排:https://docs.qq.com/doc/DUFpXY3hBZkpabWFY 
●day 18 任务以及具体安排:https://docs.qq.com/doc/DUFFiVHl3YVlReVlr 
●day 19 周日休息
●day 20 任务以及具体安排:https://docs.qq.com/doc/DUGFRU2V6Z1F4alBH  
●day 21 任务以及具体安排:https://docs.qq.com/doc/DUHl2SGNvZmxqZm1X 
●day 22 任务以及具体安排:https://docs.qq.com/doc/DUHplVUp5YnN1bnBL  
●day 23 任务以及具体安排:https://docs.qq.com/doc/DUFBUQmxpQU1pa29C 
●day 24 任务以及具体安排:https://docs.qq.com/doc/DUEhsb0pUUm1WT2NP  
●day 25 任务以及具体安排:https://docs.qq.com/doc/DUExTYXVzU1BiU2Zl 
●day 26 休息 
●day 27 任务以及具体安排:https://docs.qq.com/doc/DUElpbnNUR3hIbXlY 
●day 28 任务以及具体安排:https://docs.qq.com/doc/DUG1yVHdlWEdNYlhZ  
●day 29 任务以及具体安排:https://docs.qq.com/doc/DUHZYbWhwSHRCRmp3 
●day 30 任务以及具体安排:https://docs.qq.com/doc/DUEdTVVhxbnJiY3BR

目录

理论基础

0455_分发饼干

0376_摆动序列

0053_最大子序和


理论基础

贪心的本质是选择每一阶段的局部最优,从而达到全局最优。

0455_分发饼干

package com.question.solve.leetcode.programmerCarl2._09_greedyAlgorithms;import java.util.Arrays;public class _0455_分发饼干 {
}class Solution0455 {//思路1:优先考虑饼干,小饼干先喂饱小胃口public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int start = 0;int count = 0;for (int i = 0; i < s.length && start < g.length; i++) {if (s[i] >= g[start]) {start++;count++;}}return count;}
}class Solution0455_2 {//思路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;}
}

0376_摆动序列

package com.question.solve.leetcode.programmerCarl2._09_greedyAlgorithms;public class _0376_摆动序列 {
}class Solution0376 {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;}
}class Solution0376_2 {//DPpublic int wiggleMaxLength(int[] nums) {// 0 i 作为波峰的最大长度// 1 i 作为波谷的最大长度int dp[][] = new int[nums.length][2];dp[0][0] = dp[0][1] = 1;for (int i = 1; i < nums.length; i++) {//i 自己可以成为波峰或者波谷dp[i][0] = dp[i][1] = 1;for (int j = 0; j < i; j++) {if (nums[j] > nums[i]) {// i 是波谷dp[i][1] = Math.max(dp[i][1], dp[j][0] + 1);}if (nums[j] < nums[i]) {// i 是波峰dp[i][0] = Math.max(dp[i][0], dp[j][1] + 1);}}}return Math.max(dp[nums.length - 1][0], dp[nums.length - 1][1]);}
}

0053_最大子序和

package com.question.solve.leetcode.programmerCarl2._09_greedyAlgorithms;public class _0053_最大子序和 {
}class Solution0053 {public int maxSubArray(int[] nums) {if (nums.length == 1) {return nums[0];}int sum = Integer.MIN_VALUE;int count = 0;for (int i = 0; i < nums.length; i++) {count += nums[i];sum = Math.max(sum, count);//取区间累计的最大值(相当于不断确定最大子序终止位置)if (count <= 0) {count = 0;//相当于重置最大子序起始位置,因为遇到负数一定是拉低总和}}return sum;}
}class Solution0053_2 {//DP方法public int maxSubArray(int[] nums) {int ans = Integer.MIN_VALUE;int[] dp = new int[nums.length];dp[0] = nums[0];ans = dp[0];for (int i = 1; i < nums.length; i++) {dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);ans = Math.max(dp[i], ans);}return ans;}
}

相关文章:

代码随想录-算法训练营day31【贪心算法01:理论基础、分发饼干、摆动序列、最大子序和】

代码随想录-035期-算法训练营【博客笔记汇总表】-CSDN博客 第八章 贪心算法 part01● 理论基础 ● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和 贪心算法其实就是没有什么规律可言&#xff0c;所以大家了解贪心算法 就了解它没有规律的本质就够了。 不用花心思去研究其…...

如何使用Transformer-TTS语音合成模型

1、技术原理及架构图 ​ Transformer-TTS主要通过将Transformer模型与Tacotron2系统结合来实现文本到语音的转换。在这种结构中&#xff0c;原始的Transformer模型在输入阶段和输出阶段进行了适当的修改&#xff0c;以更好地处理语音数据。具体来说&#xff0c;Transformer-TT…...

【Python】JSON数据的使用

一、JSON JSON是什么&#xff1a; JSON&#xff08;JavaScript Object Notation&#xff09;是一种轻量级的数据交换格式&#xff0c;它以易于理解和生成的文本格式来描述数据对象。JSON最初是由Douglas Crockford在2001年提出的&#xff0c;它的设计受到了JavaScript对象字面量…...

C语言头文件的引入使用<>和““有什么区别

在C语言中&#xff0c;引入头文件时使用<>和""有以下主要区别&#xff1a; 搜索路径不同&#xff1a; 当使用#include <filename.h>时&#xff0c;编译器会首先在系统目录中搜索头文件。这些系统目录通常包含了标准库的头文件&#xff0c;如stdio.h、std…...

Qt 类的设计思路详解

Qt 是一个跨平台的 C++ 应用程序开发框架,它提供了丰富的类库和工具,用于开发图形用户界面、网络应用、数据库集成和文件 I/O 等功能。Qt 的设计思路涉及到诸多方面,包括跨平台性、模块化、可扩展性、性能等。本文将从这些方面详细说明 Qt 类的设计思路。 1. 跨平台性 Qt 最…...

五一超级课堂---Llama3-Tutorial(Llama 3 超级课堂)---第一节 Llama 3 本地 Web Demo 部署

课程文档&#xff1a; https://github.com/SmartFlowAI/Llama3-Tutorial 课程视频&#xff1a; https://space.bilibili.com/3546636263360696/channel/collectiondetail?sid2892740&spm_id_from333.788.0.0 操作平台&#xff1a; https://studio.intern-ai.org.cn/consol…...

Redis20种使用场景

Redis20种使用场景 1缓存2抽奖3Set实现点赞/收藏功能4排行榜5PV统计&#xff08;incr自增计数&#xff09;6UV统计&#xff08;HeyperLogLog&#xff09;7去重&#xff08;BloomFiler&#xff09;8用户签到&#xff08;BitMap&#xff09;9GEO搜附近10简单限流11全局ID12简单分…...

vue3获取原始值

在 Vue 3 中&#xff0c;_rawValue 是 ref 内部的一个属性&#xff0c;它用来存储 ref 的原始值&#xff0c;也就是未经响应式处理的值。这个属性主要用于 Vue 的内部逻辑&#xff0c;以帮助区分 ref 的当前值 (value) 和原始输入值 (_rawValue)。对于大多数开发者来说&#xf…...

“感恩遇到你,郭护士!”佛山市一医院 护士回家途中救了位老奶奶

“感恩遇见你&#xff0c;我感谢郭护士关爱长者、热心助人的高尚行为……”看着信件上感谢的话语&#xff0c;郭琳玲的内心感动不已。而这一封亲笔手写的感谢信&#xff0c;是来自一位将近八十岁的老奶奶。 郭琳玲是佛山市第一人民医院创伤重症功能神经外科的一名护士。4月30日…...

Java面试常见问题

操作系统 1.Q: 在操作系统中&#xff0c;什么时候会发生用户态到内核态的切换 A: 操作系统中&#xff0c;用户态和内核态是两种不同的权限级别&#xff0c;他们对应着不同的执行环境和执行权限。用户态事指程序在一般的运行情况下的的级别&#xff0c;它具有别较低的权限级别&…...

概率论 科普

符号优先级 概率公式中一共有三种符号&#xff1a;分号 ; 、逗号 , 、竖线 | 。 ; 分号代表前后是两类东西&#xff0c;以概率P(x;θ)为例&#xff0c;分号前面是x样本&#xff0c;分号后边是模型参数。分号前的 表示的是这个式子用来预测分布的随机变量x&#xff0c;分号后的…...

全面解读快递查询API接口,帮你轻松查询快递物流信息

随着电子商务的快速发展&#xff0c;快递业务正变得越来越重要。无论是买家还是卖家&#xff0c;都希望能够及时了解自己的快递物流信息&#xff0c;以便更好地掌控商品的运输过程。而现在&#xff0c;通过快递查询API接口&#xff0c;我们可以实现快速、准确地查询几百家国内快…...

【图书推荐】《JSP+Servlet+Tomcat应用开发从零开始学(第3版)》

本书目的 系统讲解JSPServletTomcat开发技术&#xff0c;帮助读者用最短的时间掌握Java Web应用开发技能。 内容简介 本书全面系统地介绍JSPServletTomcat开发中涉及的相关技术要点和实战技巧。本书内容讲解循序渐进&#xff0c;结合丰富的示例使零基础的读者能够熟练掌握JSP…...

C++容器——set

set容器 是一个关联容器&#xff0c;按一定的顺序存储一组唯一的元素。 set容器中的元素会根据元素的值自动进行排序&#xff0c;并且不允许包含重复的元素&#xff0c;基于二叉树实现的。 特点&#xff1a; 唯一性&#xff1a; set容器中的元素是唯一的&#xff0c;即容器中…...

.NET WebService \ WCF \ WebAPI 部署总结 以及 window 服务 调试

一、webservice 部署只能部署IIS上&#xff0c; 比较简单&#xff0c;就不做说明了 二、 WCF 部署 1 部署到IIS 跟部署 webservice 部署方法一样的 wcf 部署2 部署到控制台 要以管理员运行vs&#xff0c;或者 管理员运行 控制台的exe 在控制器项目中 创建IUserInfoService 接口…...

Centos系统实用运维命令记录(持续更新)

本文记录Centos服务器常用的运维命令&#xff0c;备忘 查询当前内存占用最高(前10)的进程列表和占用比例&#xff0c;进程ID ps -eo pid,comm,%mem,cmd --sort-%mem | head -n 11注: 内存警报时定位问题时非常有用 查询占用某个端口号的进程id lsof -i :9000注: 后面的9000…...

大势模方在修模过程中,如何导入su单体模型?

答&#xff1a;在单体化界面右键即可显示导入入口&#xff0c;若仍不可行&#xff0c;需要换最新版dv 模方是一款针对实景三维模型的冗余碎片、水面残缺、道路不平、标牌破损、纹理拉伸模糊等共性问题研发的实景三维模型修复编辑软件。模方4.1新增自动单体化建模功能&#xff…...

uniapp百度地图聚合

// loadBMap.js ak 百度key export default function loadBMap(ak) {return new Promise((resolve, reject) > {//聚合API依赖基础库,因此先加载基础库再加载聚合APIasyncLoadBaiduJs(ak).then(() > {// 调用加载第三方组件js公共方法加载其他资源库// 加载聚合API// Ma…...

nginx的应用部署nginx

这里写目录标题 nginxnginx的优点什么是集群常见的集群什么是正向代理、反向代理、透明代理常见的代理技术正向代理反向代理透明代理 nginx部署 nginx nginx&#xff08;发音同enginex&#xff09;是一款轻量级的Web服务器/反向代理服务器及电子邮件&#xff08;IMAP/POP3&…...

Centos固定静态ip地址

这里我用的是Vmware虚拟机搭建的三台机器 进入 cd /etc/sysconfig/network-scripts然后使用 ip addr命令&#xff0c;查看自己虚拟机的以太网地址。 我这里是ens33 上面的第一个选项是本地环回地址&#xff0c;不用管它 然后查看刚刚进入的network-scripts目录下的文件 找到…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

关于nvm与node.js

1 安装nvm 安装过程中手动修改 nvm的安装路径&#xff0c; 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解&#xff0c;但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后&#xff0c;通常在该文件中会出现以下配置&…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

SpringTask-03.入门案例

一.入门案例 启动类&#xff1a; package com.sky;import lombok.extern.slf4j.Slf4j; import org.springframework.boot.SpringApplication; import org.springframework.boot.autoconfigure.SpringBootApplication; import org.springframework.cache.annotation.EnableCach…...