emu in blogjava

這個(gè)算法怎么弄啊？ 誰來說說？   回復(fù)  更多評(píng)論
  

這個(gè)還真有點(diǎn)不好搞的，我一個(gè)鐘頭搞不定。周末看看有沒有時(shí)間研究了。  回復(fù)  更多評(píng)論
  

我甚至沒想到用什么數(shù)據(jù)結(jié)構(gòu)來描述和操作比較合適 暈了就  回復(fù)  更多評(píng)論
  

飯要一口一口吃的，先把數(shù)據(jù)結(jié)構(gòu)和算法的教科書啃通了再來做吧。  回復(fù)  更多評(píng)論
  

我想到一種描述，但是沒有想到方法。
用一個(gè)矩陣來描述，一個(gè)方向?yàn)閿?shù)字，一個(gè)方向?yàn)樽帜浮１热缱詈笠粋€(gè)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

這樣，任一個(gè)方向上連續(xù)的幾個(gè)‘T’，就是一組符合條件的卡。  回復(fù)  更多評(píng)論
  

剛才的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
  回復(fù)  更多評(píng)論
  

肯定是要轉(zhuǎn)化為一個(gè) 4*10 矩陣的，newsmth 的google版有人貼了解法，不過，我總覺得有問題，還沒找出挑戰(zhàn)的參數(shù)。  回復(fù)  更多評(píng)論
  

一個(gè)鐘頭要求做這么變態(tài)一道題再加一道小題，要求確實(shí)高了一點(diǎn)。不知道有多少高手得分？

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"}
));
    }
}
  回復(fù)  更多評(píng)論
  

你弄好了？ 測(cè)試時(shí)間2秒夠了？ 稍微講一下算法吧，java不是太明白，謝謝 ：）  回復(fù)  更多評(píng)論
  

就是首先生成所有可能的set和run，然后嘗試所有run和set的組合，看看那個(gè)符合要求啊。  回復(fù)  更多評(píng)論
  

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"}
));
輸出結(jié)果為12,算法有錯(cuò)誤,而且樓主的思路典型的窮舉法,會(huì)很耗資源的.
我的數(shù)學(xué)模型:
先計(jì)算出所有的sets和runs以及他們的交點(diǎn),每個(gè)交點(diǎn)都有2種狀態(tài),set有效或者run有效,對(duì)每個(gè)交點(diǎn)進(jìn)行2種狀態(tài)的選擇,判斷之后,再刷新一下重新把失效的交點(diǎn)剔除,到最后交點(diǎn)集為0,則完成一種狀態(tài),統(tǒng)計(jì)出card數(shù).
內(nèi)容太長(zhǎng),程序就不貼出來了.  回復(fù)  更多評(píng)論
  

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;
}  回復(fù)  更多評(píng)論
  

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();
}
}  回復(fù)  更多評(píng)論
  

*********用這段取代
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));
}  回復(fù)  更多評(píng)論
  

謝謝 xjingg 。
我其實(shí)并不是算法錯(cuò)了，問題出在這一行：
for(int i=0,n=1<<sets.size();i<n;i++){
當(dāng)sets.size()太大的時(shí)候溢出了，所以無法取得正確結(jié)果。而且確實(shí)在規(guī)定的時(shí)間內(nèi)是無法通過測(cè)試的。

我們來看看你的數(shù)學(xué)模型：
-------------------------------------------------------------------
先計(jì)算出所有的sets和runs以及他們的交點(diǎn),每個(gè)交點(diǎn)都有2種狀態(tài),set有效或者run有效,對(duì)每個(gè)交點(diǎn)進(jìn)行2種狀態(tài)的選擇,判斷之后,再刷新一下重新把失效的交點(diǎn)剔除,到最后交點(diǎn)集為0,則完成一種狀態(tài),統(tǒng)計(jì)出card數(shù).
-------------------------------------------------------------------
我不明白的是“對(duì)每個(gè)交點(diǎn)進(jìn)行2種狀態(tài)的選擇,判斷之后”是依據(jù)什么來選擇、判斷的？
按照我的理解，這兩種狀態(tài)都需要窮舉才能指定哪種是正確的選擇。這樣子你的算法的時(shí)間復(fù)雜度實(shí)質(zhì)上和我的是一致的（2^n）。在你給出的數(shù)據(jù)中你為2^20 我的卻為2^49，確實(shí)實(shí)際的差異是巨大的，但是面對(duì)更復(fù)雜的情形如何呢？
你給出的代碼無法通過編譯，很想看看你的代碼在給出大半副牌的情形下的表現(xiàn)。  回復(fù)  更多評(píng)論