算法学习——贪心算法之删数字（求最小值）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法学习——贪心算法之删数字（求最小值），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1339字，纯文字阅读大概需要2分钟。

内容图文

算法描述

在给定的n位数字，删除其中的k位数字（ k < n），使得最后的n-k为数字为最小值（原次序不变）

算法思路

1. 考虑到是要移出数字，我们使用链表设计此算法较为方便，链表可以直接移出某个位置的元素

2. 使用贪心算法，每一步都要达到最优

3. 从最高位开始，若下一位比上一位要小，则将上一位的数字移出，结束之后再次从最高位开始

这里需要注意，会有特例

当输入从小到大的的一个数的时候，上述算法将会无法运行，比如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));
    }
    
    

结果

内容总结

以上是互联网集市为您收集整理的算法学习——贪心算法之删数字（求最小值）全部内容，希望文章能够帮你解决算法学习——贪心算法之删数字（求最小值）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---