emu in blogjava

这个算法怎么弄啊？ 谁来说说？   回复  更多评论
  

这个还真有点不好搞的，我一个钟头搞不定。周末看看有没有时间研究了。  回复  更多评论
  

我甚至没想到用什么数据结构来描述和操作比较合适 晕了就  回复  更多评论
  

饭要一口一口吃的，先把数据结构和算法的教科书啃通了再来做吧。  回复  更多评论
  

我想到一种描述，但是没有想到方法。
用一个矩阵来描述，一个方向为数字，一个方向为字母。比如最后一个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’，就是一组符合条件的卡。  回复  更多评论
  

刚才的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
  回复  更多评论
  

肯定是要转化为一个 4*10 矩阵的，newsmth 的google版有人贴了解法，不过，我总觉得有问题，还没找出挑战的参数。  回复  更多评论
  

一个钟头要求做这么变态一道题再加一道小题，要求确实高了一点。不知道有多少高手得分？

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"}
));
    }
}
  回复  更多评论
  

你弄好了？ 测试时间2秒够了？ 稍微讲一下算法吧，java不是太明白，谢谢 ：）  回复  更多评论
  

就是首先生成所有可能的set和run，然后尝试所有run和set的组合，看看那个符合要求啊。  回复  更多评论
  

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数.
内容太长,程序就不贴出来了.  回复  更多评论
  

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;
}  回复  更多评论
  

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();
}
}  回复  更多评论
  

*********用这段取代
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));
}  回复  更多评论
  

谢谢 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，确实实际的差异是巨大的，但是面对更复杂的情形如何呢？
你给出的代码无法通过编译，很想看看你的代码在给出大半副牌的情形下的表现。  回复  更多评论