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

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

题目描述:
给定一个十进制的正整数 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;
}
  • 算法
    428 引用 • 254 回帖 • 24 关注

相关帖子

欢迎来到这里!

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

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

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

  • 其他回帖
  • visus

    没有人给答案,我日

  • ellenbboe

    这不是概率论吗-.-

    1 回复
  • ellenbboe
    A_{m}^{3}
  • 查看全部回帖

推荐标签 标签

  • 小薇

    小薇是一个用 Java 写的 QQ 聊天机器人 Web 服务,可以用于社群互动。

    由于 Smart QQ 从 2019 年 1 月 1 日起停止服务,所以该项目也已经停止维护了!

    34 引用 • 467 回帖 • 743 关注
  • Angular

    AngularAngularJS 的新版本。

    26 引用 • 66 回帖 • 533 关注
  • Caddy

    Caddy 是一款默认自动启用 HTTPS 的 HTTP/2 Web 服务器。

    12 引用 • 54 回帖 • 163 关注
  • Firefox

    Mozilla Firefox 中文俗称“火狐”(正式缩写为 Fx 或 fx,非正式缩写为 FF),是一个开源的网页浏览器,使用 Gecko 排版引擎,支持多种操作系统,如 Windows、OSX 及 Linux 等。

    8 引用 • 30 回帖 • 407 关注
  • Typecho

    Typecho 是一款博客程序,它在 GPLv2 许可证下发行,基于 PHP 构建,可以运行在各种平台上,支持多种数据库(MySQL、PostgreSQL、SQLite)。

    12 引用 • 65 回帖 • 452 关注
  • 小说

    小说是以刻画人物形象为中心,通过完整的故事情节和环境描写来反映社会生活的文学体裁。

    28 引用 • 108 回帖
  • 友情链接

    确认过眼神后的灵魂连接,站在链在!

    24 引用 • 373 回帖 • 1 关注
  • 持续集成

    持续集成(Continuous Integration)是一种软件开发实践,即团队开发成员经常集成他们的工作,通过每个成员每天至少集成一次,也就意味着每天可能会发生多次集成。每次集成都通过自动化的构建(包括编译,发布,自动化测试)来验证,从而尽早地发现集成错误。

    15 引用 • 7 回帖 • 1 关注
  • Netty

    Netty 是一个基于 NIO 的客户端-服务器编程框架,使用 Netty 可以让你快速、简单地开发出一个可维护、高性能的网络应用,例如实现了某种协议的客户、服务端应用。

    49 引用 • 33 回帖 • 20 关注
  • GitHub

    GitHub 于 2008 年上线,目前,除了 Git 代码仓库托管及基本的 Web 管理界面以外,还提供了订阅、讨论组、文本渲染、在线文件编辑器、协作图谱(报表)、代码片段分享(Gist)等功能。正因为这些功能所提供的便利,又经过长期的积累,GitHub 的用户活跃度很高,在开源世界里享有深远的声望,并形成了社交化编程文化(Social Coding)。

    209 引用 • 2031 回帖
  • 游戏

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

    176 引用 • 815 回帖
  • PHP

    PHP(Hypertext Preprocessor)是一种开源脚本语言。语法吸收了 C 语言、 Java 和 Perl 的特点,主要适用于 Web 开发领域,据说是世界上最好的编程语言。

    179 引用 • 407 回帖 • 489 关注
  • 负能量

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

    88 引用 • 1235 回帖 • 406 关注
  • uTools

    uTools 是一个极简、插件化、跨平台的现代桌面软件。通过自由选配丰富的插件,打造你得心应手的工具集合。

    6 引用 • 14 回帖 • 3 关注
  • LaTeX

    LaTeX(音译“拉泰赫”)是一种基于 ΤΕΧ 的排版系统,由美国计算机学家莱斯利·兰伯特(Leslie Lamport)在 20 世纪 80 年代初期开发,利用这种格式,即使使用者没有排版和程序设计的知识也可以充分发挥由 TeX 所提供的强大功能,能在几天,甚至几小时内生成很多具有书籍质量的印刷品。对于生成复杂表格和数学公式,这一点表现得尤为突出。因此它非常适用于生成高印刷质量的科技和数学类文档。

    12 引用 • 53 回帖 • 82 关注
  • 一些有用的避坑指南。

    69 引用 • 93 回帖
  • Hadoop

    Hadoop 是由 Apache 基金会所开发的一个分布式系统基础架构。用户可以在不了解分布式底层细节的情况下,开发分布式程序。充分利用集群的威力进行高速运算和存储。

    86 引用 • 122 回帖 • 618 关注
  • 新人

    让我们欢迎这对新人。哦,不好意思说错了,让我们欢迎这位新人!
    新手上路,请谨慎驾驶!

    52 引用 • 228 回帖 • 1 关注
  • Electron

    Electron 基于 Chromium 和 Node.js,让你可以使用 HTML、CSS 和 JavaScript 构建应用。它是一个由 GitHub 及众多贡献者组成的活跃社区共同维护的开源项目,兼容 Mac、Windows 和 Linux,它构建的应用可在这三个操作系统上面运行。

    15 引用 • 136 回帖
  • 996
    13 引用 • 200 回帖 • 1 关注
  • AngularJS

    AngularJS 诞生于 2009 年,由 Misko Hevery 等人创建,后为 Google 所收购。是一款优秀的前端 JS 框架,已经被用于 Google 的多款产品当中。AngularJS 有着诸多特性,最为核心的是:MVC、模块化、自动化双向数据绑定、语义化标签、依赖注入等。2.0 版本后已经改名为 Angular。

    12 引用 • 50 回帖 • 474 关注
  • SVN

    SVN 是 Subversion 的简称,是一个开放源代码的版本控制系统,相较于 RCS、CVS,它采用了分支管理系统,它的设计目标就是取代 CVS。

    29 引用 • 98 回帖 • 683 关注
  • ReactiveX

    ReactiveX 是一个专注于异步编程与控制可观察数据(或者事件)流的 API。它组合了观察者模式,迭代器模式和函数式编程的优秀思想。

    1 引用 • 2 回帖 • 154 关注
  • danl
    129 关注
  • Android

    Android 是一种以 Linux 为基础的开放源码操作系统,主要使用于便携设备。2005 年由 Google 收购注资,并拉拢多家制造商组成开放手机联盟开发改良,逐渐扩展到到平板电脑及其他领域上。

    334 引用 • 323 回帖 • 2 关注
  • 外包

    有空闲时间是接外包好呢还是学习好呢?

    26 引用 • 232 回帖 • 4 关注
  • DevOps

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

    46 引用 • 25 回帖