阿里巴巴3.20笔试,打扑克,bfs+剪枝

//没参加3.20号的笔试,后续自己写出来的,能否AC不作保证
//找到所有的顺子
private List<int[]> selectFive(int[] cardCount){
    List<int[]> result=new LinkedList<>();
    for(int i=0;i<=cardCount.length-5;++i){
        if(cardCount[i]>0){
            int cnt=1;
            for(int j=i+1;j<cardCount.length;++j){
                if(cnt==5) break;
                if(cardCount[j]>0) ++cnt;
                else break;
            }
            if(cnt==5){
                int[] tmp=Arrays.copyOf(cardCount,cardCount.length);
                for(int k=i;k<i+5;++k){
                    --tmp[k];
                }
                result.add(tmp);
            }
        }
    }
    return result;
}
//找出所有的三连对
private List<int[]> selectSix(int[] cardCount){
    List<int[]> result=new LinkedList<>();
    for(int i=0;i<=cardCount.length-3;++i){
        if(cardCount[i]>=2){
            int cnt=1;
            for(int j=i+1;j<cardCount.length;++j){
                if(cnt==3) break;
                if(cardCount[j]>=2) ++cnt;
                else break;
            }
            if(cnt==3){
                int[] tmp=Arrays.copyOf(cardCount,cardCount.length);
                for(int k=i;k<i+3;++k){
                    tmp[k]-=2;
                }
                result.add(tmp);
            }
        }
    }
    return result;
}
//10种扑克牌A~9,每种最多四张,出牌方式可以是单张,一个对子,连续的三个对子已经连续五张的顺子,求解打完扑克牌的最少步骤数
//tip: bfs,时间复杂度略高
public int playingCard(int[] cardCount){
    Queue<int[]> queue=new LinkedList<>();
    Queue<Integer> cntQ=new LinkedList<>();//记录每种选择对应的步数
    //Set<String> states=new HashSet<>();//记录状态,用于剪枝,貌似更慢了....
    queue.add(cardCount);
    cntQ.add(0);
    int ans=Integer.MAX_VALUE;
    int max=0;
    for(int i=0;i<cardCount.length;++i) {//只出单张和对子,所需的操作数,最优解不会超过这个,用于剪枝
        if(cardCount[i]==1){
            max+=cardCount[i];
        }else if(cardCount[i]%2==0) {
            max+=cardCount[i]/2;
        }else{
            max+=cardCount[i]/2+1;
        }
    }
    while (!queue.isEmpty()){
        int[] tmp=queue.poll();
        int cnt=cntQ.poll();
        //states.add(Arrays.toString(tmp));

        List<int[]> tmp5s=selectFive(tmp),tmp6s=selectSix(tmp);
        //出连续的三个对
        for(int[] tmp6:tmp6s){
            if(cnt>=max) break;
            //if(states.contains(Arrays.toString(tmp6))) continue;
            queue.add(tmp6);
            cntQ.add(cnt+1);
        }
        //出连续的五张
        for(int[] tmp5:tmp5s){
            if(cnt>=max) break;
            //if(states.contains(Arrays.toString(tmp5))) continue;
            queue.add(tmp5);
            cntQ.add(cnt+1);
        }

        if(tmp5s.isEmpty()&&tmp6s.isEmpty()){//没有顺子和连续的三个对子,这时可以算出一种方案了
            for(int i=0;i<tmp.length;++i) {
                if(tmp[i]==1){//单张
                    cnt+=tmp[i];
                }else if(tmp[i]%2==0) {//能取对子
                    cnt+=tmp[i]/2;
                }else{
                    cnt+=tmp[i]/2+1;
                }
            }
            ans=Math.min(ans,cnt);
        }
    }
    return ans;
}

@Test
public void testPlayingCard() {
    System.out.println(playingCard(new int[]{4,4,4,4,4,4,4,4,4,4}));
}