TopCoder SRM 396 Level2 1000
http://www.topcoder.com/stat?c=problem_statement&pm=8721&rd=12168
给定一个字符串里面包含了若干个1～9的数字，另一个字符串为其子集，对于后者中每个字符，从前面字符串中删去相应的一个数字
求删去剩下的数字的最大值

由于是求最大值，直接在计算过程中不断贪心在最高位谋取最大值
从前面按照9～1的顺序寻求可以做当前最高位的最大值
分以下4步：
1.对于所有都要删去的数字，直接删光
2.从前面开始查找，将所有无法删去的数字加入答案中
3.从前面按照9～1的顺序找可以用的最大值，如果其前面的所有数字都可以删去，那么就取这个数，否则递减
4.若字符串为空则结束，否则循环第一步

这一题足足做了2个多小时
想法很快就有了
但是在实现中String类型不能修改和删除的问题很难处理
最后干脆把String转化为LinkedList来做
不过没有看答案解决掉很难得...继续加油

 1import java.util.*;
 2import java.util.regex.*;
 3import java.text.*;
 4import java.math.*;
 5import java.awt.geom.*;
 6
 7public class RemovingDigits
 8{
 9    public String maxNumber(String number, String digits)
10    {
11        int[] numCnt = new int[10];
12        int[] digCnt = new int[10];
13        Arrays.fill(numCnt, 0);
14        Arrays.fill(digCnt, 0);
15        int i;
16        for(i = 0 ; i < number.length(); ++ i)
17            numCnt[number.charAt(i)-'0']++;
18        for(i = 0 ; i < digits.length(); ++ i)
19            digCnt[digits.charAt(i) - '0']++;
20        StringBuilder ans = new StringBuilder("");
21        List<Character> target = new LinkedList<Character>();
22        for(i = 0 ; i < number.length(); ++ i){
23            target.add(number.charAt(i));
24        }
25        while(!target.isEmpty()){
26            //remove digits that all should be removed
27            for(i = 1 ; i < 10 ; ++ i){
28                if(numCnt[i] == digCnt[i]){
29                    char c = (char) ('0'+i);
30                    while(target.remove((Character)c));
31//                    target.remove((Character)c);
32                    numCnt[i] = 0;
33                    digCnt[i] = 0;
34                }
35            }
36            //append all that cannot be removed
37            for(i = 0 ; i < target.size(); ++ i){
38                if(digCnt[target.get(i)-'0'] != 0)
39                    break;
40                ans.append(target.get(i));                    
41            }
42            for(--i;i >= 0; -- i){
43                numCnt[target.get(i)-'0']--;
44                target.remove(i);
45            }
46            if(target.isEmpty())
47                break;
48                    
49            //find the largest head number
50            Outer:
51            for(i = 9 ; i > 0 ; -- i){
52                //whether there is still this number
53                if(numCnt[i] == 0)
54                    continue;
55                char c = (char) ('0'+i);
56                int idx = target.indexOf((Character)c);
57                int j;
58                int[] tempCnt = new int[10];
59                Arrays.fill(tempCnt, 0);
60                for(j = 0 ; j < idx ; ++ j)
61                    tempCnt[target.get(j)-'0']++;
62                for(j = 1 ; j < 10; ++ j){
63                    if(tempCnt[j] > digCnt[j])
64                        continue Outer;
65                }
66                for(j = 1; j < 10; ++ j){
67                    digCnt[j] -= tempCnt[j];
68                    numCnt[j] -= tempCnt[j];
69                }
70                numCnt[i]--;
71                ans.append(target.get(idx));
72                for(j = idx; j >=0; --j)
73                    target.remove(j);
74                break;
75                
76            }
77        }
78        return ans.toString();
79    }
80}