# emu in blogjava

BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合 :: 管理 :: 171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks
 PlayCards Problem StatementYou 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).DefinitionClass:PlayCardsMethod:maxCardsParameters:String[]Returns:intMethod signature:int maxCards(String[] cards)(be sure your method is public)Constraints-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'.Examples0){"1 S", "2 S", "3 S"}Returns: 3We have a run of three cards, which we can play.1){"4 C", "4 D", "4 S", "3 S", "2 S"}Returns: 3We can take the 4's as a set, or we can take the 2-3-4 run. Either way, we play 3 cards.2){"1 S", "2 S", "2 H", "3 H", "3 D", "4 D", "4 C", "5 C", "5 S"}Returns: 0We've got lots of cards, but no way to put three together.3){"1 S", "2 S"}Returns: 0Since 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: 9The best we can do is to take the set of 4s, the 5-6-7 C, and the remaining three 5s. We could have takenthe 4-5-6-7 of C,or all four 5s, but we would not end up playing as many cards.
posted on 2005-12-13 13:34 emu 阅读(1500) 评论(15)  编辑  收藏 所属分类: google编程大赛模拟题及入围赛真题 ### 评论

# re: google中国编程挑战赛资格赛真题 -- PlayCards 2005-12-16 08:55

# re: google中国编程挑战赛资格赛真题 -- PlayCards 2005-12-16 11:00 emu

# re: google中国编程挑战赛资格赛真题 -- PlayCards 2005-12-16 14:43

# re: google中国编程挑战赛资格赛真题 -- PlayCards 2005-12-16 15:35 emu

# re: google中国编程挑战赛资格赛真题 -- PlayCards 2005-12-16 16:02 Fujson

S H D C
1 T T
2 T T
3 T
4 T T T
5 T T T T
6 T T
7 T T
8 T
9 T
10 T T

# re: google中国编程挑战赛资格赛真题 -- PlayCards 2005-12-16 16:07 Fujson

S H D C
1 T T
2 T T
3 T
4 T T T
5 T T T T
6 T T
7 T T
8 T
9 T
10T T
回复  更多评论

# re: google中国编程挑战赛资格赛真题 -- PlayCards 2005-12-16 22:25

# 确实是有一点点变态的，我需要超过一个钟头来做这一道题。 2005-12-19 18:28 emu

import java.util.ArrayList;
public class PlayCards {
public int maxCards(String[] cards){
//S=0 H=1 D=2 C=3
int[][] map = new int;
for(int i=0;i<cards.length;i++){
String[] t = cards[i].split(" ");
int t0 = Integer.parseInt(t,10)-1;
int t1=0;
if(t.equals("H")) t1=1;
else if(t.equals("D")) t1=2;
else if(t.equals("C")) t1=3;
map[t0][t1]=1;
}
/*
for(int i=0;i<11;i++){
for(int j=0;j<4;j++)
System.out.print(map[i][j]+" ");
System.out.println();
}
*/
ArrayList sets = new ArrayList();
ArrayList set,run;
for(int i=0;i<11;i++){
int c = map[i]+map[i]+map[i]+map[i];
if(c==3){
set = new ArrayList();
}else if (c==4){
set = new ArrayList();
for(int j=0;j<4;j++){
set = new ArrayList();
}
}
}
for(int i=0;i<4;i++){
for(int j=0;j<8;j++){
for(int k=j;k<11;k++){
if(map[k][i]<1) break;
if(k-j<2) continue;
run = new ArrayList();
for(int t=j;t<=k;t++)

}
}
}
int max = 0;
for(int i=0,n=1<<sets.size();i<n;i++){
if(checkConflic(sets,i)){
int m = countCards(sets,i);
if(max<m) max=m;
}
}
return max;
}
private boolean checkConflic(ArrayList sets,int status){
boolean[][] map = new boolean;
for(int i=0,n=sets.size();i<n;i++){
if((status & (1<<i))==0) continue;
ArrayList set = (ArrayList)sets.get(i);
for(int j=0,m=set.size();j<m;j++){
int[] card = (int[])set.get(j);
if(map[card][card])return false;
map[card][card]=true;
}
}
return true;
}
private int countCards(ArrayList sets,int status){
int result =0;
for(int i=0,n=sets.size();i<n;i++){
if((status & (1<<i))==0) continue;
ArrayList set = (ArrayList)sets.get(i);
result += set.size();
}
return result;
}
public static void main(String[] args)
{
PlayCards p = new PlayCards();
System.out.println(p.maxCards(new String[]{"1 S", "2 S", "3 S"}));
System.out.println(p.maxCards(new String[]{"4 C", "4 D", "4 S", "3 S", "2 S"}));
System.out.println(p.maxCards(new String[]{"1 S", "2 S"}));
System.out.println(p.maxCards(new String[]{"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"}
));
}
}
回复  更多评论

# re: google中国编程挑战赛资格赛真题 -- PlayCards 2005-12-22 11:35

# re: google中国编程挑战赛资格赛真题 -- PlayCards 2005-12-22 17:36 emu

# re: google中国编程挑战赛资格赛真题 -- PlayCards 2006-03-08 10:33 xjingg
System.out.println(p.maxCards(new String[]{"1 S", "2 S", "3 S", "4 S", "5 S",
"1 H", "2 H", "3 H", "4 H", "5 H",
"1 D", "2 D", "3 D", "4 D", "5 D",
"1 C", "2 C", "3 C", "4 C", "5 C"}
));

# 我的答案,有点长,有clone对象就好办了. 2006-03-08 16:21 xjingg
import java.util.*;

public class PlayCards {
int num;
public PlayCards() {
}
public int maxCards(String[] cards){
int[][] map = new int;
//S=0;H=1;D=2;C=3
if (cards.length<3){
return 0;
}
for(int i=0;i<cards.length;i++){
String[] t = cards[i].split(" ");
int t0 = Integer.parseInt(t);
int t1 = 0;
if (t.equals("H")) t1 = 1;
else if (t.equals("D")) t1 = 2;
else if (t.equals("C")) t1 = 3;
map[t1][t0-1] = 1;
}
List orders=new ArrayList();
for (int i=0;i<4;i++){
int n=0,m=0;
for(int j=0;j<10;j++){
n=n+map[i][j];
m++;
if(m>n){
if (m>3){
int[] order={i,(j-1),n};
}
m=0;
n=0;
}
}
}
List sets=new ArrayList();
for (int i = 0; i < 10; i++) {
int num_y = 0;
for (int j = 0; j < 4; j++) {
num_y = num_y + map[j][i];
if (j == 3 && num_y > 2) {
for (int k=0; k < 4; k++){
if (map[k][i]==0){
int[] set={k,i};
break;
}
if (k==3){
int[] set={4,i};
}
}
}
}
}
List points=new ArrayList();
for (int i=0;i<orders.size();i++){
int[] order=(int[]) orders.get(i);
for (int j=0;j<sets.size();j++){
int[] set=(int[]) sets.get(j);
if (set>=(order-order+1)&&set<=order){
if (set!=order){
int[] point={order,set};
}
}
}
}
if (points.size()>0){
List set_p = new ArrayList();
List set_s = new ArrayList();
List set_o = new ArrayList();
List order_p = new ArrayList();
List order_s = new ArrayList();
List order_o = new ArrayList();
for (int i = 0; i < points.size(); i++) {
}
for (int i = 0; i < sets.size(); i++) {
}
for (int i = 0; i < orders.size(); i++) {
}

dopoint_order(order_p,0,order_s,order_o);
dopoint_set(set_p,0,set_s,set_o);
}else{
all(sets,orders);
}
return num;
}  回复  更多评论

# 接上面的 2006-03-08 16:25 xjingg
public void dopoint_order(List points,int no,List sets,List orders) {
int[] point=(int[]) points.get(no);
points.remove(no);
for (int i = 0; i < sets.size(); i++) {
int[] set = (int[]) sets.get(i);
if (set == point) {
if (set == 4) {
int[] ss={point,set};
sets.remove(i);
// set = point;
break;
} else {
for (int ii = 0; ii < points.size(); ii++) {
int[] pp=(int[]) points.get(ii);
if (set==pp&&pp!=set){
points.remove(ii);
}
}
sets.remove(i);
}
break;
}
}
if (points.size()==0){
all(sets,orders);
}else{
*************
dopoint_order(order_p, 0, order_s, order_o);
dopoint_set(set_p, 0, set_s, set_o);
}
}

public void all(List sets,List orders){
int count=0;
for (int i = 0; i < sets.size(); i++) {
int[] set = (int[]) sets.get(i);
if (set == 4) {
count=count+4;
}else{
count=count+3;
}
}
for (int i = 0; i < orders.size(); i++) {
int[] order = (int[]) orders.get(i);
count=count+order;
}
if (count>num){
num=count;
}
}

public void dopoint_set(List p,int no,List s,List o) {
List points = p;
List sets = s;
List orders = o;
int[] point=(int[]) points.get(no);
points.remove(no);
for (int i = 0; i < orders.size(); i++) {
int[] order = (int[]) orders.get(i);
if(point==order&&order>=point&&point>=(order-order+1)){
orders.remove(i);
int[] lost={order,order};
if (order-point>2){
int[] neworder={point,order,order-point};
lost=new int[] {point-1,order-order+point-1};
}
if (point-order+order-1 > 2) {
int[] neworder = {point, point-1, point-order+order-1};
if (order-point>2){
lost = lost - point + 1;
}else{
lost = lost - point;
}
}
for (int ii = 0; ii < points.size(); ii++) {
int[] pp = (int[]) points.get(ii);
if (pp == order&&lost >= pp&&pp >=(lost - lost + 1)) {
points.remove(ii);
}
}
break;
}
}
if (points.size()==0) {
all(sets,orders);
} else {
***************
dopoint_order(order_p,0,order_s,order_o);
dopoint_set(set_p,0,set_s,set_o);
}
}

public static void main(String[] args) {
PlayCards p = new PlayCards();
}
}  回复  更多评论

# re: google中国编程挑战赛资格赛真题 -- PlayCards 2006-03-08 16:26 xjingg
*********用这段取代
List set_p = new ArrayList();
List set_s = new ArrayList();
List set_o = new ArrayList();
List order_p = new ArrayList();
List order_s = new ArrayList();
List order_o = new ArrayList();
for (int i = 0; i < points.size(); i++) {
}
for (int i = 0; i < sets.size(); i++) {
}
for (int i = 0; i < orders.size(); i++) {
}  回复  更多评论

# re: google中国编程挑战赛资格赛真题 -- PlayCards 2006-03-09 00:52 emu

for(int i=0,n=1<<sets.size();i<n;i++){

-------------------------------------------------------------------

-------------------------------------------------------------------

 只有注册用户登录后才能发表评论。 网站导航: 相关文章: