算法笔记 10_删数问题


问题描述

 给定n位正整数a,去掉其中任意k个数字后,剩下的数字按原次序排列组成一个新的正整数。 
 对于给定的n和k,设计一个算法,找出剩下数字组成的新数最少的删数方案。 
     输入示例1:178543 4 
     输出:13
     输入示例2:12222222299 4
     输出:1222222

算法思想

用贪心算法解决。按照高位到低位的顺序搜索,若各位数字递增,则删除最后一个数字;否则删除第一个递减区间的首字符,然后回到串首,再重复删除。

C++ 代码如下

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
while(1)
{
     char a[100];    //定义字符串数组来记录输入的数字,方便把每一位数字分开存放调用。
    int n;   //定义要删除的位数

    cout << "Please input the number you like: " << endl;    
    cin >> a;    
    cout << "Please input the number of digits you wanna delete: " << endl; 
    cin >> n;    
    if( n == strlen(a) )    //情况一:判断如果用户把输入的数字所有位都删了,那结果为0(strlen() 获取字符串长度)
    {   
        cout << "The result is: " << 0 << endl;        
        return 0; 
    } 

    while(n > 0)        //情况二:用户要删除 n 位
    {   
        int i = 0;  //每次开始将 i 初始化为0,方便重新遍历检测 
        while(i < strlen(a) && a[i] <= a[i+1]) // 判断是否相邻的位数为递增,并且记录递增的位数
            i++;  
        for(int j=i; j<strlen(a); j++)  //当上面递增区间检测停止(也就是说不再递增之后)
            a[j] = a[j+1];  //从第 i 位数字开始,每一位数字向前移动一位
        n--;  // n 减一,减少一次遍历“减位”
    }  

    cout << "The result is: " << a << endl;    
    cout << "____________________________________________________________" << endl;
}   
    return 0;
}


happysneaker.com

Unity那些事儿
请先登录后发表评论
  • 最新评论
  • 总共0条评论