第二道题,权值750
Problem Statement
You are playing a card game, and in your hand, you are holding several
cards. Each card has a suit, 'S', 'H', 'D', or 'C', and a value between
1 and 10, inclusive. You may play cards as part of a set, which is
three or more cards of the same value, or as part of a run, which is
three or more cards of the same suit, in sequential order. (Runs may
not wrap, thus, 9-10-1 is not a valid run.) Each card may be played
only once.
For example, "1 S", "1 H" and "1 D" would be a valid set. "2 S", "3 S",
and "4 S" would be a valid run.
You want to play as many cards as possible, maybe in several plays (see
example 4). Given a String[] cards representing the cards held in your
hand, you are to return an int indicating the maximum number of cards
you can play. Each card will be given in the form "value suit" (quotes
added for clarity).
有一个纸牌游戏，共有四种花色'S', 'H', 'D',
'C'，每个花色都有1到10数字的十张牌，出牌的时候可以一起一套3张或更多的同样数字不同花色的牌，或者出相同花色连续数字的牌（但9,10,1不算连续的牌）
例如："1 S", "1 H" ，"1 D"和"2 S", "3 S", "4
S"都算一套，每副牌由String[]表示。每副牌中的每张牌可能组成不同的套（如例子4），但是每张只用一次，求最多可出的张数。
Definition
Class:
PlayCards
Method:
maxCards
Parameters:
String[]
Returns:
int
Method signature:
int maxCards(String[] cards)
(be sure your method is public)
Constraints
定义类名PlayCards，方法名public int maxCards(String[] cards)
-
cards will contain between 0 and 20 elements, inclusive.
-
No two elements of cards will be the same.
-
Each element of cards will be of the form "value suit" (quotes added
for clarity).
-
Each number represented will be between 1 and 10, inclusive, with no
leading zeroes.
-
Each suit represented will be 'S', 'H', 'D', or 'C'.
Examples
0)
{"1 S", "2 S", "3 S"}
Returns: 3
We have a run of three cards, which we can play.
"1 S", "2 S", "3 S"可以组成一套，返回的张数为3张
1)
{"4 C", "4 D", "4 S", "3 S", "2 S"}
Returns: 3
We can take the 4's as a set, or we can take the 2-3-4 run. Either way,
we play 3 cards.
"4 C", "4 D", "4 S"或"4 S", "3 S", "2
S"都可以组成一套，返回的张数都为3张
2)
{"1 S", "2 S", "2 H", "3 H", "3 D", "4 D", "4 C", "5 C", "5 S"}
Returns: 0
We've got lots of cards, but no way to put three together.
不能组成一套,一套最少为3张
3)
{"1 S", "2 S"}
Returns: 0
Since we have to play at least three cards at a time, there's nothing
to do here.
不能组成一套
4)
{"1 S", "2 S", "10 S", "5 S", "8 S",
"3 H", "9 H", "6 H", "5 H", "4 H",
"10 D", "5 D", "7 D", "4 D", "1 D",
"2 C", "4 C", "5 C", "6 C", "7 C"}
Returns: 9
The best we can do is to take the set of 4s, the 5-6-7 C, and the
remaining three 5s. We could have taken the 4-5-6-7 of C, or all four
5s, but we would not end up playing as many cards.
This problem statement is the exclusive and proprietary property of
TopCoder, Inc. Any unauthorized use or reproduction of this information
without the prior written consent of TopCoder, Inc. is strictly
prohibited. (c)2003, TopCoder, Inc. All rights reserved.
能组成若干套,由于每张牌只能用一次,其中"5 C", "6 C",
"7 C"和"5 S"，"5 H", "5 D"和"4 D", "4 C", "4 H"共为9张
或者"4 C", "5 C", "6 C", "7 C"和"3 H", "6 H", "5 H", "4
H"但是只有8张...
求最多的张数
思想:穷举出所有的遍历方案,找出最大的张数
import java.util.ArrayList;
public class PlayCards {
public int maxCards(String[] cards){
int cardsCount =0;
//备份牌
ArrayList bak = new ArrayList();
for(int i=0;i<cards.length;i++){
bak.add(cards[i]);
}
//所有牌都可以作为第1张牌开始遍历
for(int i=0;i<cards.length;i++){
int t=0;
//求出牌的数字
int num = new
Integer(cards[i].substring(0,cards[i].length()-1).trim()).intValue();
for(int j=0;j<5;j++){//能组成一套的所有方案进行遍历
if(j<4){//按照同数字不同花色查找,共有4种方案
t = countCards(i,j,0,0,(ArrayList)bak.clone());
if(cardsCount<t){
cardsCount = t;
}
}else{//按照同花色连续数字查找,共有4种方案,要包含当前num,start小与等num,end大与等num
for(int start=1;start<=num;start++){
for(int end=num;end<=10;end++){
if(end-start>=2){//必须为最少3张
t = countCards(i,j,start,end,(ArrayList)bak.clone());
if(cardsCount<t){
cardsCount = t;
}
}
}
}
}
}
}
return cardsCount;
}
//统计在牌al中,一第i张牌作为起始,按照第j套方案统计或者如果j==5起始牌为start结束牌end统计
private int countCards(int i,int j,int start,int end,ArrayList al){
ArrayList al2 = null;
int cardsCount =0;
if(j<4){
//按照同数字不同花色查找,共有4种方案
al2 = getSetA(i,j,al);
}else{//按照同花色连续数字查找
al2 = getSetB(i,start,end,al);
}
if(al2!=null){//如果找到则抽出找到的牌,剩下的继续查找
ArrayList bak = (ArrayList)al.clone();
cardsCount = al2.size();
for(int m=0;m<al2.size();m++){
for(int n=bak.size()-1;n>=0;n--){
if(al2.get(m).equals(bak.get(n))){
bak.remove(n);
}
}
}
int t = 0;
int cardsCount2 = 0;
//所有牌都可以作为第1张牌开始遍历
for(int m=0;m<bak.size();m++){
int num = new
Integer(((String)al.get(m)).substring(0,((String)al.get(m)).length()-1).trim()).intValue();
for(int n=0;n<5;n++){//能组成一套的所有方案进行遍历
if(j<4){//按照同数字不同花色查找,共有4种方案
t = countCards(m,n,0,0,(ArrayList)bak.clone());
if(cardsCount2<t){
cardsCount2 = t;
}
}else{//按照同花色连续数字查找,共有4种方案,要包含当前num,start2小与等num,end2大与等num
for(int start2=1;start2<=num;start2++){
for(int end2=num;end2<=10;end2++){
if(end2-start2>=2){//必须为最少3张
//换种方案查找需要恢复刚才的牌
t = countCards(m,n,start2,end2,(ArrayList)bak.clone());
if(cardsCount2<t){
cardsCount2 = t;
}
}
}
}
}
}
}
cardsCount = cardsCount + cardsCount2;
}
return cardsCount;
}
//检查al中第i张牌,组成同一花色不同数字的牌是否存在,如果存在返回这套牌
//start为开始的数字，end为结束的数字
private ArrayList getSetB(int i,int start,int end,ArrayList al){
String card = (String)al.get(i);
//求出花色
String suit =
评论