N 位数删除 K 个数字,使剩下的数字最小

本贴最后更新于 1697 天前,其中的信息可能已经沧海桑田

题目描述:
给定一个十进制的正整数 number,该正整数有 N 位,选择从里面去掉 K 个数字,希望留下来的数字组成的正整数最小。

输入描述:
输入为两个数字,第一个数字是一个正整数 number, 1<=length(number)<=50000。第二个数字是希望去掉的数字数量 cnt, 并且 1<=cnt<=length(number)。

输出描述:
输出保留下来的结果。

示例:

输入
124682385 2

输出
1242385

思路:
删除 K 个,可以使用贪心算法,每次删除 1 个。
那么每次删除哪一个呢?
如果 N>=2 的话,我们可以将该整数写成 XabY 的形式,其中 X 和 Y 分别是前缀和后缀,并且其长度可以为 0。因为 a 和 b 相邻并且 a 在 b 左边,所以删除一个的话,剩下的数就变成了 XaY 或 XbY 了。分下面两种情况讨论:
(1)若 a!=b 的话,为了使剩下的数最小,我们倾向于删除 a 和 b 中较大的那个数
(2)若 a==b 的话,删除 a 和删除 b 是等价的,所以我们就跳过 a,去比较 b 和它的后继,这就转变成了问题(1)了。

综上所述:
如果要使的剩下的数字最小,可以每次从左向右扫描,找出连续的非严格递增串,删除该串的最后一个数字。
如果要使剩下的数字最大,可以每次从左向右扫描,找出连续的非严格递减串,删除该串的最后一个数字。

下面给出求剩下数字最小的 C++ 代码:

string deleteKNumbers(string &str, int k)
{
	string::iterator start;
	bool flag;
	for(int i = k; i > 0; --i)
	{
		flag = 0;
		for(start = str.begin(); start < str.end() - 1; ++start)
		{
			 // 每次删除第一个比下一个数字大的数
			if(*start > *(start + 1))
			{
				str.erase(start);
				flag = 1;
				break;
			}
		}
		//如果所有数字递增,则删除最后几个数字直接返回
		if(!flag) 
		{
			str.erase(str.end() - i, str.end());
			break;
		}
	}
	return str;
}
  • 算法
    388 引用 • 254 回帖 • 22 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • visus 1 评论

    如有一个整数数组 n(里面的整数不一样,没有 0,个数位 m,其中 m 大于 3),求得到全部不重复的 3 位数字,求有多少个。

    读不明白这题目
    ellenbboe
  • visus

    要用代数解决

  • visus

    不能用实数

  • visus

    没有人给答案,我日

  • visus

    比如[1,3,2,4],那么结果就是 24 种组合,例如 123,,124,132,134.....

    1 回复
  • ellenbboe

    这不是概率论吗-.-

    1 回复
  • visus

    给答案就完事了

    1 回复
  • ellenbboe
    A_{m}^{3}
  • visus

    不对呀,孩子,你概率论体育老师教的吗,还有题目的审题你确定好了嘛,一个两个问题,m 是知道的,但是是代数

  • visus

    一看你就没做过大赛的数学题

    1 回复
  • ellenbboe

    不是 m 个数里面取三个数进行排列吗

  • visus

    不是答案,你没写过这类程序

  • visus

    你写过就知道了,所以说写过和没有写过的都知道

请输入回帖内容 ...

推荐标签 标签

  • Love2D

    Love2D 是一个开源的, 跨平台的 2D 游戏引擎。使用纯 Lua 脚本来进行游戏开发。目前支持的平台有 Windows, Mac OS X, Linux, Android 和 iOS。

    14 引用 • 53 回帖 • 506 关注
  • CodeMirror
    1 引用 • 2 回帖 • 109 关注
  • 负能量

    上帝为你关上了一扇门,然后就去睡觉了....努力不一定能成功,但不努力一定很轻松 (° ー °〃)

    85 引用 • 1192 回帖 • 461 关注
  • Linux

    Linux 是一套免费使用和自由传播的类 Unix 操作系统,是一个基于 POSIX 和 Unix 的多用户、多任务、支持多线程和多 CPU 的操作系统。它能运行主要的 Unix 工具软件、应用程序和网络协议,并支持 32 位和 64 位硬件。Linux 继承了 Unix 以网络为核心的设计思想,是一个性能稳定的多用户网络操作系统。

    914 引用 • 930 回帖 • 1 关注
  • WiFiDog

    WiFiDog 是一套开源的无线热点认证管理工具,主要功能包括:位置相关的内容递送;用户认证和授权;集中式网络监控。

    1 引用 • 7 回帖 • 545 关注
  • Markdown

    Markdown 是一种轻量级标记语言,用户可使用纯文本编辑器来排版文档,最终通过 Markdown 引擎将文档转换为所需格式(比如 HTML、PDF 等)。

    163 引用 • 1446 回帖 • 1 关注
  • 服务

    提供一个服务绝不仅仅是简单的把硬件和软件累加在一起,它包括了服务的可靠性、服务的标准化、以及对服务的监控、维护、技术支持等。

    41 引用 • 24 回帖
  • ngrok

    ngrok 是一个反向代理,通过在公共的端点和本地运行的 Web 服务器之间建立一个安全的通道。

    7 引用 • 63 回帖 • 598 关注
  • 创业

    你比 99% 的人都优秀么?

    82 引用 • 1397 回帖
  • Wide

    Wide 是一款基于 Web 的 Go 语言 IDE。通过浏览器就可以进行 Go 开发,并有代码自动完成、查看表达式、编译反馈、Lint、实时结果输出等功能。

    欢迎访问我们运维的实例: https://wide.b3log.org

    30 引用 • 218 回帖 • 594 关注
  • C++

    C++ 是在 C 语言的基础上开发的一种通用编程语言,应用广泛。C++ 支持多种编程范式,面向对象编程、泛型编程和过程化编程。

    106 引用 • 152 回帖 • 2 关注
  • TGIF

    Thank God It's Friday! 感谢老天,总算到星期五啦!

    284 引用 • 4481 回帖 • 651 关注
  • DevOps

    DevOps(Development 和 Operations 的组合词)是一组过程、方法与系统的统称,用于促进开发(应用程序/软件工程)、技术运营和质量保障(QA)部门之间的沟通、协作与整合。

    37 引用 • 24 回帖 • 1 关注
  • Kafka

    Kafka 是一种高吞吐量的分布式发布订阅消息系统,它可以处理消费者规模的网站中的所有动作流数据。 这种动作(网页浏览,搜索和其他用户的行动)是现代系统中许多功能的基础。 这些数据通常是由于吞吐量的要求而通过处理日志和日志聚合来解决。

    35 引用 • 35 回帖
  • TensorFlow

    TensorFlow 是一个采用数据流图(data flow graphs),用于数值计算的开源软件库。节点(Nodes)在图中表示数学操作,图中的线(edges)则表示在节点间相互联系的多维数据数组,即张量(tensor)。

    20 引用 • 19 回帖 • 1 关注
  • H2

    H2 是一个开源的嵌入式数据库引擎,采用 Java 语言编写,不受平台的限制,同时 H2 提供了一个十分方便的 web 控制台用于操作和管理数据库内容。H2 还提供兼容模式,可以兼容一些主流的数据库,因此采用 H2 作为开发期的数据库非常方便。

    11 引用 • 54 回帖 • 638 关注
  • OpenShift

    红帽提供的 PaaS 云,支持多种编程语言,为开发人员提供了更为灵活的框架、存储选择。

    14 引用 • 20 回帖 • 596 关注
  • 正则表达式

    正则表达式(Regular Expression)使用单个字符串来描述、匹配一系列遵循某个句法规则的字符串。

    31 引用 • 94 回帖
  • 知乎

    知乎是网络问答社区,连接各行各业的用户。用户分享着彼此的知识、经验和见解,为中文互联网源源不断地提供多种多样的信息。

    10 引用 • 66 回帖
  • Hibernate

    Hibernate 是一个开放源代码的对象关系映射框架,它对 JDBC 进行了非常轻量级的对象封装,使得 Java 程序员可以随心所欲的使用对象编程思维来操纵数据库。

    39 引用 • 103 回帖 • 676 关注
  • 大数据

    大数据(big data)是指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合,是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产。

    89 引用 • 113 回帖
  • Hprose

    Hprose 是一款先进的轻量级、跨语言、跨平台、无侵入式、高性能动态远程对象调用引擎库。它不仅简单易用,而且功能强大。你无需专门学习,只需看上几眼,就能用它轻松构建分布式应用系统。

    9 引用 • 17 回帖 • 591 关注
  • Lute

    Lute 是一款结构化的 Markdown 引擎,支持 Go 和 JavaScript。

    25 引用 • 191 回帖 • 16 关注
  • Sandbox

    如果帖子标签含有 Sandbox ,则该帖子会被视为“测试帖”,主要用于测试社区功能,排查 bug 等,该标签下内容不定期进行清理。

    362 引用 • 1212 回帖 • 580 关注
  • ZeroNet

    ZeroNet 是一个基于比特币加密技术和 BT 网络技术的去中心化的、开放开源的网络和交流系统。

    1 引用 • 21 回帖 • 591 关注
  • OnlyOffice
    4 引用 • 19 关注
  • 游戏

    沉迷游戏伤身,强撸灰飞烟灭。

    169 引用 • 799 回帖