Joy_program，一个小程序题

Question

题目：面对任意一个整数，如果我们需要删除掉其中的几位，怎样才能保证输出的数值最小呢？Input 输入的第一行包含一个正整数，且此正整数中只包含1－9等九个数字（即不包含0）。数字的总位数不超过1000位；第二行包含一个正整数n。表示要从第一行的数值中删除n位数字（0 < n < 1000）Output 输出从输入的数值中删掉n位后能够产生的最小整数Sample Input 
1372123
3Sample Output 
1123

Answer 1

保证在较高位上，每个数字都比低一位的数字小
import java.math.*;
import java.util.*;public class Main
{
public static void main(String[] args) throws Exception
{
Scanner s = new Scanner(System.in);
char[] arr = s.nextLine().toCharArray();
int size = s.nextInt();
char[] copy = new char[arr.length - size];
int count;
for(int i = 1; size > 0 && i < arr.length; i++)
{
if(arr[i] > arr[i - 1])
{
continue;
}
count = 1;
for(int j = i - 2; j >= 0 && arr[j] != (char)-1 && count <= size; j--)
{
if(arr[j] < arr[i])
{
break;
}
count++;
}
for(int j = i - count; j < i; j++)
{
arr[j] = (char)-1;
}
size -= count;
}
for(int i = 0, j = 0; j < copy.length; i++)
{
if(arr[i] == (char)-1)
{
continue;
}
copy[j++] = arr[i];
}
System.out.println(copy);
}
}

Answer 2

呵呵，楼主，我估计你在搞ACM，但是这种思想不是很正确，应该多看看书，给你推荐一本书《数据结构与问题求解Java语言描述》，作者比较牛逼，有很多数学思想在里面

Answer 3

2楼太天真了3楼经测试，也不对啊呵呵，没有搞ACM，只是做下算法题，提高编程能力

Answer 4

要输出最小，只要保证最高位是最小。整数为m位，删掉n位，只需删掉整数的前n+1个不重复数的最大的n个数。
1372123 删掉前3+1=4个不重复的数中（1，3，7，2）最大的3个数是372  output=1123.
611372123 删掉前3+1=4个不重复的数中（6，1，1，3，7）最大的3个数是637 output=112123

Answer 5

楼上反例：61123785  删掉前3+1=4个不重复的数中（6，1，1，2,3）最大的3个数是623 output=11785但是11235是最小的呀

Answer 6

思路：
一个长度为m的数a，要删成长度为n的数b：
第一步：从a的第一位开始到第m-n+1位结束，找到最小的一个数字，这个数字作为b的第一位
第二步：从第一位数字位置起始，到第m-n+2位结束，找到最小的一个数字，作为b的第二位
第三步：从第二个数字位置起始，到第m-n+3位结束......
...
第n步：找到第n-1个数字位置起始，到第m位结束的最小数字作为最后一位。。当n不是很大的时候可以这样做，如果n很大要用到递归...具体递归算法还没想好

Answer 7

给出代码，思路见9楼：import java.util.Arrays;public class SplitMaxNumber {
public static String getSplitMaxNumber(String number,int max) {
if(!number.matches("^[1-9]+$")){
return null;
}
StringBuffer sb = new StringBuffer();
int beginIndex =0;
int count =1;
split(number,beginIndex,max,count,sb);
return sb.toString();
}
public static void split(String number,int beginIndex,int max,int count,StringBuffer sb){
if(count>max){
return;
}
String split = number.substring(beginIndex,number.length()-max+count);
char[] numbers = split.toCharArray();
Arrays.sort(numbers);
int index=0;
for(int i=0;i<split.length();i++){
if(split.charAt(i)==numbers[0]){
index=i;
break;
}
}
sb.append(split.charAt(index));
beginIndex+=index+1;
split(number,beginIndex,max,count+1,sb);
}
public static void main(String[] args) {
//因为int最多21亿，所以用string表示正整数
String number ="187815631564846487";
int max=5;
System.out.println(getSplitMaxNumber(number, max));
}
}

Answer 8

还是漏了一点，方法里面你自己加上max>number.length()的时候返回null吧，要不然会报错

Answer 9

Thank you测试通过求递归解法，嘿嘿

Answer 10

思路和 9# 一样。
这是递归写法。    public static String g(String src, int length) {
        char[] result = new char[src.length() - length];
        g(src.toCharArray(), 0, result, 0);
        return new String(result);
    }    private static void g(char[] src, int start, char[] result, int index) {
        if (index >= result.length) {
            return;
        }
        char c = src[start];
        for (int i = start + 1, n = src.length - result.length + index; i <= n; i++) {
            if (src[i] < c) {
                c = src[i];
                start = i;
            }
        }
        result[index] = c;
        g(src, start + 1, result, index + 1);
    }

Answer 11

递归的感觉别扭...囧，修正了下，这样看起来简单多了import java.util.Arrays;/*
 * 实现：一个只含1-9的正整数，删除n个数后得到子串最小值
 */
public class SplitMaxNumber {
public static String getSplitMaxNumber(String number,int deleteCount) {
int size = number.length()-deleteCount;
if(!number.matches("^[1-9]+$")||size<=0){
return null;
}
StringBuffer sb = new StringBuffer();
int beginIndex =0;
int count =1;
while(sb.length()<size){
String split = number.substring(beginIndex,number.length()-size+count);
char[] numbers = split.toCharArray();
Arrays.sort(numbers);
int index=0;
for(int i=0;i<split.length();i++){
if(split.charAt(i)==numbers[0]){
index=i;
break;
}
}
sb.append(split.charAt(index));
beginIndex+=index+1;
count++;
}
return sb.toString();
}

public static void main(String[] args) {
//因为int最多21亿，所以用string表示不含0的正整数
String number ="48978945481";
int deleteCount=7;//要删除掉的位数
System.out.println(getSplitMaxNumber(number, deleteCount));
}
}