删数问题 贪心算法
2021/12/13 20:49:16
本文主要是介绍删数问题 贪心算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
删数问题
描述:
给定一个高精度正整数a, 去掉其中k个数字后按原左右次序将组成一个新的正整数。对给定的a, k寻找一种方案,使得剩下的数字组成的新数最小。
应用贪心算法设计求解 设计要点
操作对象为n位高精度数,存储在数组a中。
在整数的位数固定的前提下,让高位的数字尽量小,整数的值就小。这就是所要选取的贪心策略。
每次删除一个数字,选择一个使剩下的数最小的数字作为删除对象。
当k=1时,对于n位数构成的数删除哪一位,使得剩下的数据最小。删除满足如下条件的a[i]:它是第一个a[i]>a[i+1]的数,如果不存在则删除a[n](最后一位数字,具体实现时请注意下标表示方法)。
当k>1(当然小于n),按上述操作一个一个删除。每删除一个数字后,后面的数字向前移位。删除一个达到最小后,再从头开始,删除第2个,依此分解为k次完成。
若删除不到k个后已无左边大于右边的降序或相等,则停止删除操作,打印剩下串的左边n-k个数字即可(相当于删除了若干个最右边的数字)。
import java.util.Scanner; public class Deletion_problem {//数删问题 public static void main(String args[]){ Scanner scanner = new Scanner(System.in); int a = scanner.nextInt(); int k = scanner.nextInt(); if(a <= 0 || k <= 0){ System.exit(0); } StringBuffer buffer = new StringBuffer(a + "");//因为字符窜也可以用下标表示字符,且数组不好删除 int j; for(int i = 0;i < k;i++){//保证数字字符窜是呈递增状态,如果有开始递减就删除开始递减那个数 保证第一个数相对较小 for(j = 0;j < buffer.length() - 1 && buffer.charAt(j) < buffer.charAt(j + 1);j++);//保证字符单调递增并且小于最后一个数, // 但全是顺序递增就取最后一个 buffer.delete(j,j+1);//删除j } System.out.println(buffer.length() == 0 ?0:Integer.parseInt(buffer.toString()));//当a == k时,表示为0 } }
这篇关于删数问题 贪心算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现