Java教程

贪心策略------删数问题

本文主要是介绍贪心策略------删数问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

4-2 删数问题 (30 分)

给定n位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数a和正整数 k,设计一个算法找出剩下数字组成的新数最小的删数方案。如果数字最前面有0不输出。

输入格式:

第 1 行是1 个正整数 a。第 2 行是正整数k。

输出格式:

输出最小数。

输入样例:

在这里给出一组输入。例如:

178543 
4 
5001 
1
123456 
2
109 
1

输出样例:

在这里给出相应的输出。例如:

13
1
1234


一、贪心策略

  从给定的数字中,找到升序的最后一个数,也可以说是降序的首个数。

二、代码实现

#include<iostream>
#include<algorithm>
#include<string.h>  // strlen() 的头文件 
using namespace std;
int main(){
    
    char D[1000]; // 默认空格初始化 
//    cout<<D[0]<<endl;
//    cout<<D<<endl;  // 输出D每个字符,相当于输出字符串 
    cin>>D;
    int len=strlen(D); // 字符串求长度,不能用D.length(),因为非数组,此时D为字符串 
    int n;
    cin>>n;
    
    for(int i=0;i<n;i++){ // 总共删除n次,用for取每一次 
        
        int j=0;
        while(D[j]<=D[j+1]){
            j++;
        }
        
        while(j<=len-1){  
            D[j]=D[j+1]; // 后面的数字覆盖到前面过来 
            j++;
        }
        len--; // 总长度减1,因为删除一次
    }

    // 输出:注意0XX这样的输出,需要去掉前面的0
    
    int is=0; // 用于判断首位是否为0,直到遍历出现 非0 数 则置 1
    
    for(int i=0;i<len;i++){
        
        if(D[i]=='0' && is==0)// 注意字符和数字的表达,D存的是字符,is是整数 
            continue; // 不搭理,跳过 
            
        if(D[i]!=0){  // 遍历到非0数了 
            is=1; // 置 1,可以输出0啦 
            cout<<D[i];  // 不需要换行 
        }
    }  
    return 0;
}

 三、时间复杂度

删除for循环中有两个while循环,时间复杂度为O(n^3),输出for循环时间复杂度为O(n),
所以整个过程的时间复杂度应该是为O(n^3)。(可能不对。。。或许)

四、心得

对于贪心策略,就是要尽量做到最贪心的思路,这是贪心策略的精髓,根据题目要求,确定要贪心的方向即可。

这篇关于贪心策略------删数问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!