产品展示

Products Classification

算法:删去k个数字后的最小值

  • 产品时间:2022-01-07 00:45
  • 价       格:

简要描述:点击上方关注,天天学习一个java知识点原创: 法式员小灰————— 第二天 —————什么意思呢?让我们举几个栗子:给定整数1593212,删去3个数字,新整数的最小情况是1212给定整数30200,删去1个数字,新整数的最小情况是200给定整数10,删去2个数字,新整数的最小情况是0需要注意的是,给定的整数巨细可以凌驾long类型的规模,所以需要用字符串来表现。————————————我们来举一个栗子:给定整数 541270936,要求删去一个数,让剩下的整数尽可能小。...

详细介绍
本文摘要:点击上方关注,天天学习一个java知识点原创: 法式员小灰————— 第二天 —————什么意思呢?让我们举几个栗子:给定整数1593212,删去3个数字,新整数的最小情况是1212给定整数30200,删去1个数字,新整数的最小情况是200给定整数10,删去2个数字,新整数的最小情况是0需要注意的是,给定的整数巨细可以凌驾long类型的规模,所以需要用字符串来表现。————————————我们来举一个栗子:给定整数 541270936,要求删去一个数,让剩下的整数尽可能小。

亚搏手机版app下载

点击上方关注,天天学习一个java知识点原创: 法式员小灰————— 第二天 —————什么意思呢?让我们举几个栗子:给定整数1593212,删去3个数字,新整数的最小情况是1212给定整数30200,删去1个数字,新整数的最小情况是200给定整数10,删去2个数字,新整数的最小情况是0需要注意的是,给定的整数巨细可以凌驾long类型的规模,所以需要用字符串来表现。————————————我们来举一个栗子:给定整数 541270936,要求删去一个数,让剩下的整数尽可能小。

此时,无论删除哪一个数字,最后的效果都是从9位整数酿成8位整数。既然同样是8位整数,我们显然应该优先把高位的数字降低,这样对新整数的值影响最大。如何把高位的数字降低呢?很简朴,我们把原整数的所有数字从左到右举行比力,如果发现某一位的数字大于它右面的数字,那么在删除该数字后,一定会使得该数位的值降低,因为右面比它小的数字顶替了它的位置。在咱们这个例子中,数字5右侧的数字4小于5,所以删除数字5,最高位数字降低成了4。

小灰的代码使用了两层循环,外层循环基于删除次数(k),内层循环从左到右遍历所有数字。当遍历到需要删除的数字时,使用字符串的自身方法subString() 把对应数字删除,并重新拼接字符串。显然,这段代码的时间庞大度是O(kn)。

效果,提交以后......翻译过来就是:恭喜你,打败了16.56%的小同伴!1.每一次内层循环,都需要重新遍历所有数字好比给定的整数是 11111111111114132,我们在第一轮循环中,需要遍历大部门数字,一直遍历到数字4,发现4>1,从而删除4。以现在的代码逻辑,下一轮循环中,我们要重新开始遍历,再次重复遍历大部门数字,一直遍历到数字3,发现3>2,从而删除3。

事实上,我们应该停留在上一次删除的位置继续举行比力。而不是重新开始。2.subString方法自己性能不高subString方法的底层实现,涉及到了新字符串的建立,以及逐个字符的拷贝。

这个方法自身的时间庞大度是O(n)。因此,我们应该制止在每删除以后数字后就挪用subString方法。代码中很是巧妙地运用了栈的特性,在遍历原整数的数字时,让所有数字一个个入栈,当某个数字需要删除时,让该数字出栈。

最后,法式把栈中的元素转化为字符串效果。我们仍然以整数 541270936,k=3 为例:遍历到数字5,数字5入栈:遍历到数字4,发现栈顶5>4,栈顶5出栈,数字4入栈:遍历到数字1,发现栈顶4>1,栈顶4出栈,数字1入栈:继续遍历数字2,数字7,依次入栈。遍历数字0,发现栈顶7>0,栈顶7出栈,数字0入栈:此时k的次数已经用完,无需再比力,剩下的数字一口吻入栈:此时栈中的元素就是最终的效果。

代码只对所有数字遍历了一趟,遍历的时间庞大度是O(n),尔后把栈转化为字符串的时间庞大度也是O(n),所以最终的时间庞大度是O(n)。同时,法式中使用栈往返溯遍历过的数字以及删除数字,所以法式的空间庞大度是O(n)。

leetcode原题链接如下,有兴趣的小同伴可以自己实验哦:https://leetcode.com/problems/remove-k-digits/description/。


本文关键词:算法,删去,亚搏手机版app下载,个,数字,后的,最小值,点击,上方

本文来源:亚搏手机版app下载-www.jxggd.com

 


产品咨询

留言框

  • 产品:

  • 留言内容:

  • 您的单位:

  • 您的姓名:

  • 联系电话:

  • 常用邮箱:

  • 详细地址:


推荐产品

Copyright © 2004-2021 www.jxggd.com. 亚搏手机版app下载科技 版权所有 备案号:ICP备86681665号-5

在线客服 联系方式 二维码

服务热线

079-78119711

扫一扫,关注我们