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

【算法日志】贪心算法刷题:单调递增数列,贪心算法总结(day32)

代码随想录刷题60Day


目录

前言

单调递增数列

贪心算法总结 


前言

今天是贪心算法刷题的最后一天,今天本来是打算刷两道题,其中的一道hard题做了好久都没有做出来(主要思路错了)。然后再总结一下。


单调递增数列

   int monotoneIncreasingDigits(int n) {if (n < 10)return n;vector<int> num;int result = 0;int j = num.size() - 2, k;while (n){num.push_back(n % 10);n /= 10;}for (j = num.size() - 2,k = j + 1; j >= 0; --j){if (num[j] < num[k]){--num[k];break;}else if (num[j] > num[k])k = j;}if (j < 0) k = 0;for (int i = num.size() - 1; i >= 0; --i){if (i >= k)result = result * 10 + num[i];elseresult = result * 10 + 9;}return result;}

未解决题

贪心算法总结 

贪心算法是一种常见的算法设计技术,用于在每个步骤中做出局部最优选择,以期望达到全局最优解。下面是对贪心算法的总结:

1. 基本思想:贪心算法每次都选择当前最优的解决方案,而不考虑未来的后果。它通过贪心选择策略,在每个步骤上做出局部最优选择,以期望达到全局最优解。

2. 常规步骤:

   · 确定问题的最优子结构。
   · 构建贪心选择策略,即每一步选择局部最优解。
   · 证明贪心选择的正确性。
   · 设计递归算法或迭代算法实现贪心选择策略。
   · 分析算法的时间复杂度和空间复杂度。

3. 优点:

   · 算法简单易实现。
   · 在某些问题上能够快速得到近似最优解。
   · 时间复杂度较低,通常为线性或近似线性时间。

4. 缺点:

   · 贪心选择策略可能会导致无法达到全局最优解。
   · 对于某些问题,贪心算法不一定能给出正确的解决方案。
   · 需要证明贪心选择的正确性,有时需要较高的数学推理能力。

总的来说,贪心算法是一种简单而有效的算法设计技术,适用于满足贪心选择性质和最优子结构性质的问题。它通过每一步的局部最优选择,期望达到全局最优解。然而,贪心算法并不适用于所有问题,有时需要综合考虑其他算法技术或进行适当的修改。


相关文章:

【算法日志】贪心算法刷题:单调递增数列,贪心算法总结(day32)

代码随想录刷题60Day 目录 前言 单调递增数列 贪心算法总结 前言 今天是贪心算法刷题的最后一天&#xff0c;今天本来是打算刷两道题&#xff0c;其中的一道hard题做了好久都没有做出来(主要思路错了)。然后再总结一下。 单调递增数列 int monotoneIncreasingDigits(int n…...

MATLAB算法实战应用案例精讲-【深度学习】模型压缩

目录 模型压缩概述 1. 为什么需要模型压缩 2. 模型压缩的基本方法 Patient-KD 1. Patient-KD 简介...

Matlab使用

Matlab使用 界面介绍 新建脚本&#xff1a;实际上就是新建一个新建后缀为.m的文件 新建编辑器&#xff1a;ctrlN 打开&#xff1a;打开最近文件&#xff0c;以找到最近写过的文件 点击路径&#xff0c;切换当前文件夹 预设&#xff1a;定制习惯用的界面 常见简单指令 ;…...

BladeX多数据源配置

启用多租户数据库隔离&#xff0c;会默认关闭mybatis-plus多数据源插件的启动&#xff0c;从而使用自定义的数据源识别 若不需要租户数据库隔离只需要字段隔离&#xff0c;而又需要用到多数据源的情况&#xff0c;需要前往LauncherService单独配置 数据源切换失败 详情请看说明…...

go里面关于超时的设计

设想一下你在接收源源不断的数据&#xff0c;如果有700ms没有收到&#xff0c;则认为是一个超时&#xff0c;需要做出处理。 逻辑上可以设计一个grouting,里面放一个通道&#xff0c;每收到一条数据进行相应处理。通道中夹杂一个timer定时器的处理&#xff0c;若通道在700ms内…...

Qt下使用ModbusTcp通信协议进行PLC线圈/保持寄存器的读写(32位有符号数)

文章目录 前言一、引入Modbus模块二、Modbus设备的连接三、各寄存器数据的读取四、各寄存器数据的写入五、示例完整代码总结 前言 本文主要讲述了使用Qt的Modbus模块来进行ModbusTcp的通信&#xff0c;实现对PLC的线圈寄存器和保持寄存器的读写&#xff0c;基于TCP/IP的Modbus…...

ElasticSearch学习2

1、索引的操作 1、创建索引 对ES的操作其实就是发送一个restful请求&#xff0c;kibana中在DevTools中进行ES操作 创建索引时需要注意ES的版本&#xff0c;不同版本的ES创建索引的语句略有差别&#xff0c;会导致失败 如下创建一个名为people的索引&#xff0c;settings&…...

3D角色展示

先看效果&#xff1a; 再看代码&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>3D卡片悬停</title><style>font-face {font-family: "Exoct";src: url("htt…...

前端面试:【Angular】打造强大Web应用的全栈框架

嗨&#xff0c;亲爱的Angular探险家&#xff01;在前端开发的旅程中&#xff0c;有一个全栈框架&#xff0c;那就是Angular。Angular提供了模块化、组件化、依赖注入、路由和RxJS等特性&#xff0c;助力你构建强大、可扩展的Web应用。 1. 什么是Angular&#xff1f; Angular是…...

数据结构:栈和队列

文章目录 一、栈1.栈的概念及结构1.栈的概念及结构2.栈的实现 2.栈的顺序表实现1.栈的结构体和实现的功能函数2.栈的初始化&#xff0c;入栈和出栈操作3.栈的其他操作 3.栈的链表实现1.栈的结构体和实现的功能函数2.栈功能函数的实现 二、队列1.队列的概念及结构1.队列的概念及…...

SpringCloud Gateway服务网关的介绍与使用

目录 1、网关介绍2、SpringCloudGateway工作原理3、三大组件3.1 、Route&#xff08;路由&#xff09;3.2、断言 Predicate3.3、过滤器 filter 4、Gateway整合nacos的使用4.1 、引入依赖4.2、 编写基础类和启动类4.3、 编写基础配置和路由规则4.4 、测试结果 1、网关介绍 客户…...

深入解析:如何打造高效的直播视频美颜SDK

在当今数字化时代&#xff0c;视频直播已经成为人们交流、娱乐和信息传递的重要方式。然而&#xff0c;许多人在直播时都希望能够呈现出最佳的外观&#xff0c;这就需要高效的直播视频美颜技术。本文将深入解析如何打造高效的直播视频美颜SDK&#xff0c;以实现令人满意的视觉效…...

每日一博 - MPP(Massively Parallel Processing,大规模并行处理)架构

文章目录 概述优点缺点小结 概述 MPP&#xff08;Massively Parallel Processing&#xff0c;大规模并行处理&#xff09;架构是一种常见的数据库系统架构&#xff0c;主要用于提高数据处理性能。它通过将多个单机数据库节点组成一个集群&#xff0c;实现数据的并行处理。 在 …...

ssh框架原理及流程

1.hibernate工作原理&#xff1a; 读取并解析配置文件读取并解析映射信息&#xff0c;创建sessionFactory打开session创建事务transaction持久化操作提交事务关闭session关闭sessionFactory 为什么使用&#xff1a; 对JDBC访问数据库的代码做了封装&#xff0c;大大简化了数据…...

eslint 配置和用法

在一个使用Webpack的项目中配置ESLint&#xff0c;你可以按照以下步骤操作&#xff1a; 首先&#xff0c;你需要在你的项目中安装ESLint和对应的Webpack loader。你可以使用npm或者yarn来安装。在你的项目根目录下打开终端&#xff0c;然后运行以下命令&#xff1a; 使用npm&…...

字符设备驱动实例(PWM和RTC)

目录 五、PWM 六、RTC 五、PWM PWM(Pulse Width Modulation&#xff0c;脉宽调制器)&#xff0c;顾名思义就是一个输出脉冲宽度可以调整的硬件器件&#xff0c;其实它不仅脉冲宽度可调&#xff0c;频率也可以调整。它的核心部件是一个硬件定时器&#xff0c;其工作原理可以用…...

Ribbon 源码分析

Ribbon 源码分析 Ribbon Debug 分析 断点 LoadBalancerInterceptor LoadBalancerInterceptor 实现了 ClientHttpRequestInterceptor 接口&#xff0c;重写了其中的 intercept 方法&#xff0c;用来拦截请求&#xff1b; 获取原始的 uri 和 服务名&#xff0c;调用 LoadBalanc…...

【1-3章】Spark编程基础(Python版)

课程资源&#xff1a;&#xff08;林子雨&#xff09;Spark编程基础(Python版)_哔哩哔哩_bilibili 第1章 大数据技术概述&#xff08;8节&#xff09; 第三次信息化浪潮&#xff1a;以物联网、云计算、大数据为标志 &#xff08;一&#xff09;大数据 大数据时代到来的原因…...

宇宙原理:黑洞基础。

宇宙原理&#xff1a;黑洞基础TOC 黑洞的数理基础&#xff1a;一个由满数组成的数盘&#xff0c;经过自然演进&#xff0c;将会逐步稀疏化、最终会向纯数方案发展&#xff1b;纯数方案虽然只有{2}、无数&#xff08;虚拟&#xff09;、{0,1,2,3}&#xff08;虚拟&#xff09;、…...

分类预测 | MATLAB实现SCNGO-CNN-LSTM-Attention数据分类预测

分类预测 | MATLAB实现SCNGO-CNN-LSTM-Attention数据分类预测 目录 分类预测 | MATLAB实现SCNGO-CNN-LSTM-Attention数据分类预测分类效果基本描述程序设计参考资料 分类效果 基本描述 1.SCNGO-CNN-LSTM-Attention数据分类预测程序&#xff0c;改进算法&#xff0c;融合正余弦和…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...