算法学习——贪心算法之删数字(求最小值)
2023-02-18 16:36:58 时间
算法描述
在给定的n位数字,删除其中的k位数字( k < n),使得最后的n-k为数字为最小值(原次序不变)
算法思路
-
考虑到是要移出数字,我们使用链表设计此算法较为方便,链表可以直接移出某个位置的元素
-
使用贪心算法,每一步都要达到最优
-
从最高位开始,若下一位比上一位要小,则将上一位的数字移出,结束之后再次从最高位开始
这里需要注意,会有特例
当输入从小到大的的一个数的时候,上述算法将会无法运行,比如123456,删除1个数字变为最小,我们把6删去,这样才是最小的(即从末尾删除数字)
算法实现
Scanner scanner = new Scanner(System.in);
System.out.println("请输入整数:");
String s = scanner.nextLine();
System.out.println("删除数字的个数:");
int n = scanner.nextInt();
scanner.close();
int a[] = new int[s.length()];
for(int i=0;i<s.length();i++){
char temp =s.charAt(i);
a[i] = temp -'0';//不减去‘0’则会获得Ascii码
}
LinkedList<Integer> linkedList = new LinkedList<Integer>();
for(int i=0;i<a.length;i++){
linkedList.add(a[i]);
}
int flag =0;
while(flag<n){
for(int i=0;i<linkedList.size()-1;i++){
if(linkedList.get(i)>linkedList.get(i+1)){
linkedList.remove(i);//使用链表移出元素
flag++;
break;//结束本次循环,跳转到while循环中
}
//考虑到特殊情况,当遍历完全部数字都不满足条件,从末尾删除数字
if(i==linkedList.size()-2){
linkedList.removeLast();
flag++;
}
}
}
System.out.print("截取的"+n+"个数字后的最小值为");
for(int i=0;i<linkedList.size();i++){
System.out.print(linkedList.get(i));
}
结果
相关文章
- 程序员,保险公司招聘不要轻易跑过去,省省路费省省时间,别浪费感情,特别是招聘什么业务主管经理的
- 求助,有谁能跟杭州公安局的人说上话?西湖区文新派出所更好,想解决一下女儿名字的问题,万分感谢。
- 走通用软件架构路线?走通用软件产品路线?我们都要有梦想与大家一起分享走过的经验
- 实施行政审批流程系统程组件的经验总结,规范化电子化流程管理(有点儿长,准备好茶叶)
- 当项目经理要么学会向客户说"不",要么选择折磨自己,增加成本延长项目周期
- 半天打造小型万能OA办公系统, 靠的就是万能表单提交 + 轻量级工作流审批组件
- 用一个系统去控制管理多个现有系统, 实现核心集中的统一管理控制系统
- C# GetSchema Get List of Table 获取数据库中所有的表名以及表中的纪录条数的方法
- C#缺省参数可以让代码变得更加简洁明了与时俱进心里敞亮了很多了
- 让一个软件系统同时支持多个多种数据库灵活配置,让客户可以任意配置各个核心数据库部分
- 浅谈管理软件开发类项目是怎么来的,怎么接到项目的,欢迎大家补充
- 开发各种信息管理系统的标准演示数据都帮你整理好了,少了录入演示\测试\模拟数据的烦恼了[提供下载]
- C# winform 窗体接收命令行参数自动登录进行系统,模拟600个WCF客户端的并发压力测试
- 从深圳回杭州的飞机上捡了一个不错的手机,被小考验了一下
- 国内的IT生意还真TMD难做,想生存发展大家还得多思考一下,出路在哪里?稍微迷茫了一点点
- 工作流引擎组件[行政审批流程组件] 开发实施过程中遇到的问题汇总,希望能对大家有参考价值
- 大哥你需求里说只要工作流引擎组件[行政审批流程组件],怎么真正需要的东西这么....悲剧了,客户需求无止境.........
- 浅谈专心只学一门C#的优缺点[邀月补充:一精胜于十专]
- CTO(首席技术官)
- C# C/S 图片验证码功能源码