最大数详解编程语言

给定一个整数,从整数当中去掉k个数字,要求剩下数字形成的新整数尽可能小。

什么意思呢?让我们举几个栗子:

给定整数1593212,删去3个数字,新整数的最小情况是1212

给定整数30200,删去1个数字,新整数的最小情况是200

给定整数10,删去2个数字,新整数的最小情况是0

需要注意的是,给定的整数大小可以超过long类型的范围,所以需要用字符串来表示。

给定整数 541270936,要求删去一个数,让剩下的整数尽可能小。

此时,无论删除哪一个数字,最后的结果都是从9位整数变成8位整数。既然同样是8位整数,我们显然应该优先把高位的数字降低,这样对新整数的值影响最大。

JAVA:

import java.io.*; 
import java.util.*; 
 
class test   
{ 
    public static void main (String[] args) throws java.lang.Exception 
    { 
        System.out.println(removeKDigits("1593212",3)); 
        System.out.println(removeKDigits("30200",1)); 
        System.out.println(removeKDigits("10",2)); 
        System.out.println(removeKDigits("541270936",3)); 
         
    } 
    /** 
        * 删除整数的k个数字,获得删除后的最小值 
        * @param num  原整数 
        * @param k  删除数量 
    */ 
     
    public static String removeKDigits(String num, int k) { 
         
        //新整数的最终长度 = 原整数长度 - k 
        int newLength = num.length() - k; 
        //创建一个栈,用于接收所有的数字 
        char[] stack = new char[num.length()]; 
        int top = 0; 
        for (int i = 0; i < num.length(); ++i) { 
            //遍历当前数字 
            char c = num.charAt(i); 
            //当栈顶数字大于遍历到的当前数字,栈顶数字出栈(相当于删除数字) 
            while (top > 0 && stack[top-1] > c && k > 0) { 
                top -= 1; 
                k -= 1; 
            } 
            //遍历到的当前数字入栈 
            stack[top++] = c; 
        } 
        // 找到栈中第一个非零数字的位置,以此构建新的整数字符串 
        int offset = 0; 
        while (offset < newLength && stack[offset] == '0') { 
            offset++; 
        } 
        return offset == newLength? "0": new String(stack, offset, newLength - offset); 
    } 
}

输出:

1212 
200 
0 
120936

C++:

#include <iostream> 
#include <string> 
#include <cstdio> 
#include <sstream> 
#include <vector> 
 
using namespace std; 
 
int main(){ 
     
    string num = "541270936"; 
    int k = 3; 
    int size = num.length()-k; 
    for (int i=1;i<num.length() && k>0;i++) { 
 
        for(int z=i-1;z>=0;z--){ 
            if(k==0){ 
                break; 
            } 
            if(num[z]=='-'){ 
                continue; 
            } 
            if((int)num[i]<(int)num[z]){ 
                num[z]='-'; 
                k--; 
            } 
        } 
    } 
    int begin = 0; 
    bool flag = true; 
    while(true){ 
        if(num[begin]=='-'||(int)num[begin]-48==0){ 
            begin++; 
        }else{ 
            break; 
        } 
    } 
    for(int j=begin;j<num.length();j++){ 
        if(num[j]!='-'){ 
            flag = false; 
            cout<<num[j]; 
        } 
    } 
    if(flag){ 
        cout<<"0"<<endl; 
    }else{ 
        cout<<endl; 
    } 
     
    return 0; 
}

原创文章,作者:Maggie-Hunter,如若转载,请注明出处:https://blog.ytso.com/20678.html

(0)
上一篇 2021年7月19日
下一篇 2021年7月19日

相关推荐

发表回复

登录后才能评论