算法(蓝桥杯)贪心算法5——删数问题的解题思路

问题描述

给定一个高精度的正整数 n(n≤1000 位),需要删除其中任意 s 个数字,使得剩下的数字按原左右顺序组成一个新的正整数,并且这个新的正整数最小。例如,对于数字 153748,删除 2 个数字后,最小的数是 1348。


解题思路

1. 贪心算法

要解决这个问题,我们可以使用贪心算法。贪心算法在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的。

2. 维护单调递增栈

我们可以通过维护一个单调递增的栈来实现这个目标。具体步骤如下:

2.1 初始化栈

创建一个空栈 stack,用于存储最终结果中的数字。

2.2 遍历每个数字

遍历输入的高精度正整数 n 的每一位数字 num

2.3 维护单调递增栈
  • 弹出条件:当栈不为空(stack),且还需要删除数字(s > 0),且栈顶元素大于当前数字(stack[-1] > num)时,弹出栈顶元素,并减少 s 的值。这样做的目的是尽可能地让结果数的高位更小,从而使得整个数更小。

  • 入栈操作:将当前数字 num 入栈。这一步是为了保留当前数字,以便后续继续判断。

2.4 处理剩余的删除操作

遍历结束后,如果 s 还大于0,说明原数是单调递增的。在这种情况下,直接去掉末尾的 s 个数字即可。因为从末尾去掉数字对结果数的影响最小。

2.5 拼接结果并处理前导0
  • 拼接结果:将栈中的数字拼接成一个字符串。

  • 处理前导0:使用 lstrip('0') 去掉前导0。如果去掉前导0后字符串为空(即原数删除后只剩下0),则返回 '0'

3. 示例解释

n = "153748"s = 2 为例,详细说明每一步的操作:

  1. 初始化栈stack = []

  2. 遍历每一位数字

    • num = '1':栈为空,直接入栈。stack = ['1']

    • num = '5':栈顶元素 '1' 小于 '5',直接入栈。stack = ['1', '5']

    • num = '3':栈顶元素 '5' 大于 '3',弹出 '5's 减1。stack = ['1']。然后 '3' 入栈。stack = ['1', '3']

    • num = '7':栈顶元素 '3' 小于 '7',直接入栈。stack = ['1', '3', '7']

    • num = '4':栈顶元素 '7' 大于 '4',弹出 '7's 减1。stack = ['1', '3']。然后 '4' 入栈。stack = ['1', '3', '4']

    • num = '8':栈顶元素 '4' 小于 '8',直接入栈。stack = ['1', '3', '4', '8']

  3. 遍历结束后s 为0,不需要再处理。

  4. 拼接结果并处理前导0''.join(stack).lstrip('0'),结果为 '1348'

最终结果为 '1348',这是删除2个数字后得到的最小数。

4. 代码实现

def min_number_after_delete(n, s):"""删除s个数字后得到的最小数:param n: 原始高精度正整数,字符串形式:param s: 需要删除的数字个数:return: 删除s个数字后得到的最小数,字符串形式"""stack = []# 遍历每个数字for num in n:# 当栈不为空且s大于0且栈顶元素大于当前数字时,弹出栈顶元素while stack and s > 0 and stack[-1] > num:stack.pop()s -= 1# 当前数字入栈stack.append(num)# 如果s还大于0,说明原数是单调递增的,直接去掉末尾的s个数字即可if s > 0:stack = stack[:-s]# 将栈中的数字拼接成字符串,并去掉前导0return ''.join(stack).lstrip('0') or '0'# 示例
n = "153748"
s = 2
print(min_number_after_delete(n, s))  # 输出:1348n = "1087"
s = 1
print(min_number_after_delete(n, s))  # 输出:87

5. 总结

通过维护一个单调递增的栈,我们可以有效地找到删除 s 个数字后得到的最小数。这种方法的时间复杂度为 O(n),其中 n 是输入数字的长度,因为每个数字最多只会被入栈和出栈一次。希望这个解释能帮助你更好地理解这个问题的解法。如果有任何疑问,欢迎继续提问。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/4328.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

蓝桥杯训练—矩形面积交

文章目录 一、题目二、示例三、解析四、代码 一、题目 平面上有两个矩形,它们的边平行于直角坐标系的X轴或Y轴,对于每个矩形,我们给出它的一对相对顶点的坐标,请你编程写出两个矩形的交的面积 输入格式: 输入包含两行…

GraphRAG: Auto Prompt Tuning 实践

GraphRAG 的 Auto Prompt Tuning 功能是一个强大的工具,用于优化知识图谱的生成过程。以下是对该功能的详细介绍和分析: 自动提示调优(Auto Prompt Tuning) 1. 概念 GraphRAG 的自动提示调优功能旨在为特定领域的知识图谱生成创…

【设计模式】 单例模式(单例模式哪几种实现,如何保证线程安全,反射破坏单例模式)

单例模式 作用:单例模式的核心是保证一个类只有一个实例,并且提供一个访问实例的全局访问点。 实现方式优缺点饿汉式线程安全,调用效率高 ,但是不能延迟加载懒汉式线程安全,调用效率不高,能延迟加载双重检…

IJCAI-2024 | 具身导航的花样Prompts!VLN-MP:利用多模态Prompts增强视觉语言导航能力

作者: Haodong Hong1,2 , Sen Wang1∗ , Zi Huang1 , Qi Wu3 and Jiajun Liu2,1 单位:昆士兰大学,澳大利亚科学与工业研究组织,阿德莱德大学 论文标题:Why Only Text: Empowering Vision-and-Language Navigation wi…

【蓝桥杯选拔赛真题62】C++求和 第十四届蓝桥杯青少年创意编程大赛 算法思维 C++编程选拔赛真题解

目录 C++求和 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、运行结果 五、考点分析 七、推荐资料 C++求和 第十四届蓝桥杯青少年创意编程大赛C++选拔赛真题 一、题目要求 1、编程实现 给定一个正整数N(1<N<10^6),求出N左右相邻两个…

智能创造的幕后推手:AIGC浪潮下看AI训练师如何塑造智能未来

文章目录 一、AIGC时代的算法与模型训练概览二、算法与模型训练的关键环节三、AI训练师的角色与职责四、AI训练师的专业技能与素养五、AIGC算法与模型训练的未来展望《AI训练师手册&#xff1a;算法与模型训练从入门到精通》亮点内容简介作者简介谷建阳 目录 《AI智能化办公&am…

Cloud Foundry,K8S,Mesos Marathon弹性扩缩容特性对比

一、Cloud Foundry 使用Scaling an Application Using App Autoscaler插件&#xff0c;基于资源使用情况触发简单扩缩容 CPU、内存、Http带宽、延时等 监控这些资源的使用情况决定扩缩容策略&#xff1a;实例是增加还是减少 Instance Limits 限制实例数量范围&#xff0c;定义…

ComfyUI 矩阵测试指南:用三种方法,速优项目效果

在ComfyUI中&#xff0c;矩阵测试也叫xyz图表测试&#xff0c;作用是通过控制变量的方式来对Lora模型以及各种参数开展测试&#xff0c;并进行有效区分。其中测试方法有很多种&#xff0c;可以通过借助插件也可以自行搭建工作流实现&#xff0c;下面介绍3种方式&#xff1a; 1…

什么宠物最好养?

在忙碌的生活中&#xff0c;想要拥有一份陪伴&#xff0c;却又担心没时间打理&#xff1f;别怕&#xff0c;今天就来给大家揭秘&#xff0c;什么宠物最好养&#xff0c;让你轻松开启养宠生活&#xff0c;即使再忙也能享受毛孩子带来的快乐&#xff01; 一、仓鼠&#xff1a;萌…

mfc操作json示例

首先下载cJSON,加入项目; 构建工程,如果出现, fatal error C1010: unexpected end of file while looking for precompiled head 在cJSON.c文件的头部加入#include "stdafx.h"; 看情况,可能是加到.h或者是.cpp文件的头部,它如果有包含头文件, #include &…

将IDLE里面python环境pyqt5配置的vscode

首先安装pyqt5全套&#xff1a;pip install pyqt5-tools 打开Vscode&#xff1a; 安装第三方扩展&#xff1a;PYQT Integration 成功配置designer.exe的路径【个人安装pyqt5的执行路径】&#xff0c;便可直接打开UI文件&#xff0c;进行编辑。 配置pyuic,如果下图填写方法使用…

郑州大学2022级大三期末复习总结(数据库,传感器,嵌入式,人工智能,移动终端开发,计算机英语)

本人是郑州大学2022级的一名大三学生&#xff0c;上学期期末苦于没有复习资料硬学了三周&#xff0c;所以想着将脑海里还残留着的各个课程的知识点&#xff0c;考点记录下来。这些资料不能保证你考高分&#xff0c;只能给你提供一些复习的方向和可能高频的知识点。 有些地方的…

基于ESP32+VUE+JAVA+Ngnix的一个小型固件编译系统

一、前提 开发ESP32固件时&#xff0c;使用本地环境输出固件时&#xff0c;存在多个开发多种开发平台的问题。会导致最终输出的固件不统一。更可能因为本地的开发环境差异导致固件无法追溯。 基于上述原因&#xff0c;开发了一个小型的固件编译系统。将该系统部署在一台ubutn…

Spring自定义BeanPostProcessor实现bean的代理Java动态代理知识

上文&#xff1a;https://blog.csdn.net/qq_26437925/article/details/145241149 中大致了解了spring aop的代理的实现&#xff0c;其实就是有个BeanPostProcessor代理了bean对象。顺便复习下java代理相关知识 目录 自定义BeanPostProcessor实现aopJava动态代理知识动态代理的几…

KubeSphere部署安装,接入KubeKey安装的k8s集群

KubeSphere安装接入KubeKey安装的k8s集群 文章目录 KubeSphere安装接入KubeKey安装的k8s集群 一.NFS安装配置1.服务器安装NFS服务2.下载并部署 NFS Subdir External Provisioner1).下载部署文件2).创建 NameSpace3).创建 RBAC 资源4).配置 deployment.yaml5).部署 Storage Clas…

redis性能优化参考——筑梦之路

基准性能测试 redis响应延迟耗时多长判定为慢&#xff1f; 比如机器硬件配置比较差&#xff0c;响应延迟10毫秒&#xff0c;就认为是慢&#xff0c;机器硬件配置比较高&#xff0c;响应延迟0.5毫秒&#xff0c;就认为是慢。这个没有固定的标准&#xff0c;只有了解了你的 Red…

财务RPA就是财务机器人吗?有什么作用

近年来&#xff0c;财务RPA&#xff08;机器人流程自动化&#xff09;逐渐成为财务领域的热门话题。很多人初次听到“财务RPA”时&#xff0c;可能会疑惑&#xff1a;财务RPA是不是财务机器人&#xff1f;它到底能做什么&#xff1f;带着这些问题&#xff0c;我们一起来探讨财务…

RabbitMQ---事务及消息分发

&#xff08;一&#xff09;事务 RabbitMQ是基于AMQP协议实现的&#xff0c;该协议实现了事务机制&#xff0c;所以RabbitMQ也支持事务机制&#xff0c;他的事务允许开发者确保消息的发送和接收时原子性的&#xff0c;要么全部成功&#xff0c;要么全部失败 我们设置事务有三步…

Django简介与虚拟环境安装Django

目录 1.Django简介 1.1 Django 的核心特点 1.2 Django 的核心组件 1.3 Django 的应用场景 1.4 总结 2.基础环境建立 2.1 创建虚拟环境 2.1.1 使用 virtualenv 创建虚拟环境 2.1.2 使用 venv 创建虚拟环境 2.2 激活虚拟环境 2.2.1 在 Windows 上 2.2.2 在 macOS 或 …

计算机毕业设计PySpark+Hadoop+Hive机票预测 飞机票航班数据分析可视化大屏 航班预测系统 机票爬虫 飞机票推荐系统 大数据毕业设计

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 作者简介&#xff1a;Java领…