Algorithm 06:删数问题
问题:键盘输入一个高精度的正整数N(N<=240位),去掉任意S个数字后剩下的数字按原来左右次序组成一个新的正整数。编程实现对给定的N和S,寻找一种解决方案,使得剩下的数最小。
例如,给定的N=178543,S=4,则得到的结果为13
答:实现代码如下:
/** * @author: YuHuang * @date: 2011-11-30 * @summary: Just for fun. */public class DeleteNumberProblem { public static String doDelete(String n,int s){ char[] numberArray = n.toCharArray(); int len = numberArray.length; if(len<=s) { System.out.println("invalid s!"); return null; }else{ int deleteLength = 0; int pos = 1; while(pos<len){ if(numberArray[pos]<numberArray[pos-1]) { int i=pos; while(i<len){ numberArray[i-1] = numberArray[i]; ++i; } pos = pos>1 ? --pos:pos; --len; ++deleteLength; }else{ pos++; } if(deleteLength==s) break; } len = len-(s-deleteLength); } StringBuilder sb = new StringBuilder(); for(int index=0;index<len;++index){ sb.append(numberArray[index]); } return sb.toString(); } public static void main(String[] args) { String n = "178543"; int s = 4; String result = DeleteNumberProblem.doDelete(n,s); System.out.println(result); }}