emu in blogjava

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  171 随笔 :: 103 文章 :: 1052 评论 :: 2 Trackbacks
PlayCards
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).

Definition

Class:
PlayCards
Method:
maxCards
Parameters:
String[]
Returns:
int
Method 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'.
Examples
0)


{"1 S", "2 S", "3 S"}
Returns: 3
We have a run of three cards, which we can play.
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.
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)


{"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.
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
我想到一种描述,但是没有想到方法。
用一个矩阵来描述,一个方向为数字,一个方向为字母。比如最后一个case描述如下:
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

这样,任一个方向上连续的几个‘T’,就是一组符合条件的卡。  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- PlayCards 2005-12-16 16:07 Fujson
刚才的tab键不能正确显示,因该是这样:
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
肯定是要转化为一个 4*10 矩阵的,newsmth 的google版有人贴了解法,不过,我总觉得有问题,还没找出挑战的参数。  回复  更多评论
  

# 确实是有一点点变态的,我需要超过一个钟头来做这一道题。 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[11][4];
        for(int i=0;i<cards.length;i++){
            String[] t = cards[i].split(" ");
            int t0 = Integer.parseInt(t[0],10)-1;
            int t1=0;
            if(t[1].equals("H")) t1=1;
                else if(t[1].equals("D")) t1=2;
                else if(t[1].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][0]+map[i][1]+map[i][2]+map[i][3];
            if(c==3){
                set = new ArrayList();
                for(int j=0;j<4;j++) if(map[i][j]>0) set.add(new int[]{i,j});
                sets.add(set);
            }else if (c==4){
                set = new ArrayList();
                for(int j=0;j<4;j++) set.add(new int[]{i,j});
                sets.add(set);
                for(int j=0;j<4;j++){
                set = new ArrayList();
                for(int k=0;k<4;k++) if(j!=k) set.add(new int[]{i,k});
                sets.add(set);
                }
            }
        }
        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++)
                        run.add(new int[]{t,i});
                    sets.add(run);

                }
            }
        }
        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[11][4];
        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[0]][card[1]])return false;
                map[card[0]][card[1]]=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
你弄好了? 测试时间2秒够了? 稍微讲一下算法吧,java不是太明白,谢谢 :)  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- PlayCards 2005-12-22 17:36 emu
就是首先生成所有可能的set和run,然后尝试所有run和set的组合,看看那个符合要求啊。  回复  更多评论
  

# 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"}
));
输出结果为12,算法有错误,而且楼主的思路典型的穷举法,会很耗资源的.
我的数学模型:
先计算出所有的sets和runs以及他们的交点,每个交点都有2种状态,set有效或者run有效,对每个交点进行2种状态的选择,判断之后,再刷新一下重新把失效的交点剔除,到最后交点集为0,则完成一种状态,统计出card数.
内容太长,程序就不贴出来了.  回复  更多评论
  

# 我的答案,有点长,有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[4][10];
//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[0]);
int t1 = 0;
if (t[1].equals("H")) t1 = 1;
else if (t[1].equals("D")) t1 = 2;
else if (t[1].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};
orders.add(order);
}
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};
sets.add(set);
break;
}
if (k==3){
int[] set={4,i};
sets.add(set);
}
}
}
}
}
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[1]>=(order[1]-order[2]+1)&&set[1]<=order[1]){
if (set[0]!=order[0]){
int[] point={order[0],set[1]};
points.add(point);
}
}
}
}
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++) {
set_p.add(points.get(i));
order_p.add(points.get(i));
}
for (int i = 0; i < sets.size(); i++) {
set_s.add(sets.get(i));
order_s.add(sets.get(i));
}
for (int i = 0; i < orders.size(); i++) {
set_o.add(orders.get(i));
order_o.add(orders.get(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[1] == point[1]) {
if (set[0] == 4) {
int[] ss={point[0],set[1]};
sets.remove(i);
sets.add(i,ss);
// set[0] = point[0];
break;
} else {
for (int ii = 0; ii < points.size(); ii++) {
int[] pp=(int[]) points.get(ii);
if (set[1]==pp[1]&&pp[0]!=set[0]){
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[0] == 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[2];
}
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[0]==order[0]&&order[1]>=point[1]&&point[1]>=(order[1]-order[2]+1)){
orders.remove(i);
int[] lost={order[1],order[2]};
if (order[1]-point[1]>2){
int[] neworder={point[0],order[1],order[1]-point[1]};
orders.add(i,neworder);
lost=new int[] {point[1]-1,order[2]-order[1]+point[1]-1};
}
if (point[1]-order[1]+order[2]-1 > 2) {
int[] neworder = {point[0], point[1]-1, point[1]-order[1]+order[2]-1};
orders.add(i, neworder);
if (order[1]-point[1]>2){
lost[1] = lost[0] - point[1] + 1;
}else{
lost[1] = lost[0] - point[1];
}
}
for (int ii = 0; ii < points.size(); ii++) {
int[] pp = (int[]) points.get(ii);
if (pp[0] == order[0]&&lost[0] >= pp[1]&&pp[1] >=(lost[0] - lost[1] + 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++) {
set_p.add(points.get(i));
order_p.add(points.get(i));
}
for (int i = 0; i < sets.size(); i++) {
set_s.add(sets.get(i));
order_s.add(sets.get(i));
}
for (int i = 0; i < orders.size(); i++) {
set_o.add(orders.get(i));
order_o.add(orders.get(i));
}  回复  更多评论
  

# re: google中国编程挑战赛资格赛真题 -- PlayCards 2006-03-09 00:52 emu
谢谢 xjingg 。
我其实并不是算法错了,问题出在这一行:
for(int i=0,n=1<<sets.size();i<n;i++){
当sets.size()太大的时候溢出了,所以无法取得正确结果。而且确实在规定的时间内是无法通过测试的。

我们来看看你的数学模型:
-------------------------------------------------------------------
先计算出所有的sets和runs以及他们的交点,每个交点都有2种状态,set有效或者run有效,对每个交点进行2种状态的选择,判断之后,再刷新一下重新把失效的交点剔除,到最后交点集为0,则完成一种状态,统计出card数.
-------------------------------------------------------------------
我不明白的是“对每个交点进行2种状态的选择,判断之后”是依据什么来选择、判断的?
按照我的理解,这两种状态都需要穷举才能指定哪种是正确的选择。这样子你的算法的时间复杂度实质上和我的是一致的(2^n)。在你给出的数据中你为2^20 我的却为2^49,确实实际的差异是巨大的,但是面对更复杂的情形如何呢?
你给出的代码无法通过编译,很想看看你的代码在给出大半副牌的情形下的表现。  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: