土人的家
導航
BlogJava
首頁
新隨筆
聯(lián)系
聚合
管理
統(tǒng)計信息
Posts - 15
Stories - 0
Comments - 0
Trackbacks - 0
常用鏈接
我的隨筆
我的評論
我的參與
留言簿
給我留言
查看公開留言
查看私人留言
隨筆分類
DP(4)
(rss)
Greedy(2)
(rss)
Math(2)
(rss)
Search(6)
(rss)
隨筆檔案
2009年12月 (5)
2009年11月 (10)
搜索
最新評論
閱讀排行榜
1.?MatchString(196)
2.?TheSumOfLuckyNumbers(170)
3.?ProperDivisors(149)
4.?CollectingMarbles(147)
5.?IdealString(145)
評論排行榜
1.?TheSumOfLuckyNumbers(0)
2.?IdealString(0)
3.?AvoidingProduct(0)
4.?CollectingMarbles(0)
5.?MatchString(0)
RemovingDigits
TopCoder SRM 396 Level2 1000
http://www.topcoder.com/stat?c=problem_statement&pm=8721&rd=12168
給定一個字符串里面包含了若干個1~9的數(shù)字,另一個字符串為其子集,對于后者中每個字符,從前面字符串中刪去相應的一個數(shù)字
求刪去剩下的數(shù)字的最大值
由于是求最大值,直接在計算過程中不斷貪心在最高位謀取最大值
從前面按照9~1的順序?qū)で罂梢宰霎斍白罡呶坏淖畲笾?br /> 分以下4步:
1.對于所有都要刪去的數(shù)字,直接刪光
2.從前面開始查找,將所有無法刪去的數(shù)字加入答案中
3.從前面按照9~1的順序找可以用的最大值,如果其前面的所有數(shù)字都可以刪去,那么就取這個數(shù),否則遞減
4.若字符串為空則結束,否則循環(huán)第一步
這一題足足做了2個多小時
想法很快就有了
但是在實現(xiàn)中String類型不能修改和刪除的問題很難處理
最后干脆把String轉(zhuǎn)化為LinkedList來做
不過沒有看答案解決掉很難得...繼續(xù)加油
1
import
java.util.
*
;
2
import
java.util.regex.
*
;
3
import
java.text.
*
;
4
import
java.math.
*
;
5
import
java.awt.geom.
*
;
6
7
public
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
}
posted on 2009-11-19 20:21
jav7er
閱讀(134)
評論(0)
編輯
收藏
所屬分類:
Greedy
新用戶注冊
刷新評論列表
只有注冊用戶
登錄
后才能發(fā)表評論。
網(wǎng)站導航:
博客園
IT新聞
Chat2DB
C++博客
博問
管理
相關文章:
MatchString
RemovingDigits
Powered by:
BlogJava
Copyright © jav7er
主站蜘蛛池模板:
同仁县
|
松溪县
|
宁河县
|
垫江县
|
蓬溪县
|
邵东县
|
辽宁省
|
红河县
|
龙口市
|
松阳县
|
盐边县
|
丰台区
|
登封市
|
喀什市
|
那曲县
|
格尔木市
|
沭阳县
|
汤阴县
|
雷州市
|
南召县
|
莒南县
|
台山市
|
洞口县
|
禹州市
|
光泽县
|
新沂市
|
肇东市
|
永年县
|
尼木县
|
武宁县
|
富民县
|
滨海县
|
南涧
|
扶风县
|
司法
|
益阳市
|
鲁甸县
|
三河市
|
芦溪县
|
夏津县
|
攀枝花市
|