给定一个整数,从整数当中去掉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