亚洲1234区乱码,亚洲一本之道高清乱码,亚洲av之男人的天堂网站

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 閱讀(1700) 評論(15) 編輯收藏所屬分類: google編程大賽模擬題及入圍賽真題

我想到一種描述，但是沒有想到方法。
用一個矩陣來描述，一個方向為數字，一個方向為字母。比如最后一個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，確實實際的差異是巨大的，但是面對更復雜的情形如何呢？
你給出的代碼無法通過編譯，很想看看你的代碼在給出大半副牌的情形下的表現。回復更多評論

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理
相關文章: 沒忍住手癢做了一道題，結果還沒作對。差點被燕潘考倒了 1000分模擬題CraneWork 500分模擬題 MaximalPalindromeSubstrings 250分模擬題 SalesRouting SecretSum (code jam china round2 500分真題) FactorialSystem (code jam china round2 300分真題) RecurringNumbers (code jam china 1000分真題) google中國編程挑戰賽入圍賽真題 -- HardDuplicateRemover(1000分) google中國編程挑戰賽入圍賽真題 -- BlockStructure(500分)

emu in blogjava

公告

常用鏈接

留言簿(92)

隨筆分類(20)

隨筆檔案(171)

文章分類(89)

文章檔案(103)

相冊

收藏夾(46)

友情連接

收藏

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜

評論