TopCoder SRM 396 Level2 1000
http://www.topcoder.com/stat?c=problem_statement&pm=8721&rd=12168
給定一個字符串里面包含了若干個1～9的數(shù)字，另一個字符串為其子集，對于后者中每個字符，從前面字符串中刪去相應(yīng)的一個數(shù)字
求刪去剩下的數(shù)字的最大值

由于是求最大值，直接在計算過程中不斷貪心在最高位謀取最大值
從前面按照9～1的順序?qū)で罂梢宰霎?dāng)前最高位的最大值
分以下4步：
1.對于所有都要刪去的數(shù)字，直接刪光
2.從前面開始查找，將所有無法刪去的數(shù)字加入答案中
3.從前面按照9～1的順序找可以用的最大值，如果其前面的所有數(shù)字都可以刪去，那么就取這個數(shù)，否則遞減
4.若字符串為空則結(jié)束，否則循環(huán)第一步

這一題足足做了2個多小時
想法很快就有了
但是在實現(xiàn)中String類型不能修改和刪除的問題很難處理
最后干脆把String轉(zhuǎn)化為LinkedList來做
不過沒有看答案解決掉很難得...繼續(xù)加油

 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}