扑克牌的问题

问题描述:

     假设有A和B来两个人玩牌。游戏的规则是这样的:将一副牌均分成两份,每人拿一份。A先拿出手中的第一张扑克牌,放在桌上,然后B也拿出手中的第一张扑克牌,放在A刚打出来的扑克牌的上面,就这样两人交替出牌。出牌时,如果某人打出的牌与桌上的某张牌的牌面相同,即可将两种牌以及其中间的所有牌全部取走,并按照从上到下的顺序依次放到自己手中牌的末尾。当任意一人手中的牌全部取完时,游戏结束,对手获胜。 先假设A手上有牌,按顺序依次为:2 4 1 2 5 6,B手上有牌顺序为:3 1 3 5 6 4。写程序判断谁会赢。

这个问题其实就是考察对栈和队列两种数据结构的应用。代码如下:

  1 package com.rampage.algorithm.base;
  2 
  3 import java.util.ArrayList;
  4 import java.util.List;
  5 import java.util.Stack;
  6 
  7 /**
  8  * 
  9  * @author zyq
 10  *
 11  */
 12 public class PokerGame1 {
 13 
 14     public static void main(String[] args) {
 15         
 16         int[] arr1 = { 2, 4, 1, 2, 5, 6 }; int[] arr2 = { 3, 1, 3, 5, 6, 4 };
 17          
 18 
 19         // 这个是一个永远不会结束的循环
 20         /*int[] arr1 = { 1, 1, 1 };
 21         int[] arr2 = { 1, 2, 1 };*/
 22         PokerGame1 game = new PokerGame1();
 23         game.play(arr1, arr2);
 24     }
 25 
 26     /**
 27      * 
 28      * @param arr1
 29      * @param arr2
 30      */
 31     private void play(int[] arr1, int[] arr2) {
 32         if (arr1 == null || arr2 == null || arr1.length == 0 || arr2.length == 0 || arr1.length != arr2.length) {
 33             System.out.println("Illegal card array for game!");
 34             return;
 35         }
 36 
 37         /**
 38          * 其实这道题的考查重点就在于栈和列表两种数据结构的考查,我们用栈来表示桌面上的牌(因为桌面上的牌放上去和取走的时候符合栈的特性)。用队列(queue,java中用List即可)来表示
 39          * 存储每个人手中的牌。
 40          */
 41         List<Integer> list1 = new ArrayList<Integer>(arr1.length);
 42         List<Integer> list2 = new ArrayList<Integer>(arr2.length);
 43         Stack<Integer> stack = new Stack<Integer>(); // 存储桌面上的牌
 44 
 45         // 首先将数组中的牌入列表
 46         for (int i = 0; i < arr1.length; i++) {
 47             list1.add(arr1[i]);
 48             list2.add(arr2[i]);
 49         }
 50 
 51         int turnCount = 0;
 52         // 当两个人手上的牌都不为空的时候,模拟出牌过程
 53 
 54         // 还有一种可能就是会无限循环下去,对于这种情况其实发现到后面就是两者之间的牌会又回到最初的状态。
 55         // 所以这里给两个列表来存储最开始时的牌的状态,如果后续发现又变成一样,则证明会出现无限循环。
 56         List<Integer> originalList1 = new ArrayList<Integer>(list1);
 57         List<Integer> originalList2 = new ArrayList<Integer>(list2);
 58 
 59         while (list1.size() > 0 && list2.size() > 0) {
 60             // 首先A出牌
 61             int element = list1.remove(0);
 62 
 63             // 如果栈中已经有可收回的牌,则收回栈中的牌并且放到A中牌的末尾
 64             if (stack.contains(element)) {
 65                 list1.add(element);
 66                 int popOne;
 67                 while ((popOne = stack.pop()) != element) {
 68                     list1.add(popOne);
 69                 }
 70                 list1.add(popOne);
 71             } else {
 72                 stack.push(element);
 73                 // 如果没有可以收回的牌,则判断当前A中的牌是否为空。
 74                 if (list1.size() == 0) {
 75                     break;
 76                 }
 77             }
 78 
 79             // 然后B出牌
 80             element = list2.remove(0);
 81 
 82             // 如果栈中已经有可收回的牌,则收回栈中的牌并且放到B中牌的末尾
 83             if (stack.contains(element)) {
 84                 list2.add(element);
 85                 int popOne;
 86                 while ((popOne = stack.pop()) != element) {
 87                     list2.add(popOne);
 88                 }
 89                 list2.add(popOne);
 90             } else {
 91                 stack.push(element);
 92                 // 如果没有可以收回的牌,则判断当前B中的牌是否为空。
 93                 if (list2.size() == 0) {
 94                     break;
 95                 }
 96             }
 97 
 98             System.out.println("Turn " + (++turnCount) + " result:");
 99             System.out.print("Player A:");
100             for (int one : list1) {
101                 System.out.print(one + ", ");
102             }
103             System.out.print("\nPlayer B:");
104             for (int one : list2) {
105                 System.out.print(one + ", ");
106             }
107             System.out.print("\nDesk:");
108             for (int i = stack.size() - 1; i >= 0; i--) {
109                 System.out.print(stack.elementAt(i) + ", ");
110             }
111             System.out.println("\n");
112 
113             // 当桌上没牌的时候,判断牌的状态是否又回到最初。
114             if (stack.isEmpty()) {
115                 if ((originalList1.size() == list1.size() && originalList1.containsAll(list1)
116                         && originalList2.size() == list2.size() && originalList2.containsAll(list2))
117                         || (originalList1.size() == list2.size() && originalList1.containsAll(list2)
118                                 && originalList2.size() == list1.size() && originalList2.containsAll(list1))) {
119                     System.out.println("Player A and Player B tie!");
120                     return;
121                 }
122             }
123         }
124 
125         // 根据最后谁手上的牌为空,输出结果
126         if (list1.size() == 0) {
127             System.out.println("Player B win.The cards in player B are:");
128             for (Integer one : list2) {
129                 System.out.print(one + ", ");
130             }
131         } else {
132             System.out.println("Player A win.The cards in player A are:");
133             for (Integer one : list1) {
134                 System.out.print(one + ", ");
135             }
136         }
137 
138         System.out.println("\nThe cards in the desk are:");
139         while (stack.size() > 0) {
140             System.out.print(stack.pop() + ", ");
141         }
142 
143     }
144 }

 输出结果为:

  1 Turn 1 result:
  2 Player A:4, 1, 2, 5, 6, 
  3 Player B:1, 3, 5, 6, 4, 
  4 Desk:3, 2, 
  5 
  6 Turn 2 result:
  7 Player A:1, 2, 5, 6, 
  8 Player B:3, 5, 6, 4, 
  9 Desk:1, 4, 3, 2, 
 10 
 11 Turn 3 result:
 12 Player A:2, 5, 6, 1, 1, 
 13 Player B:5, 6, 4, 3, 4, 3, 
 14 Desk:2, 
 15 
 16 Turn 4 result:
 17 Player A:5, 6, 1, 1, 2, 2, 
 18 Player B:6, 4, 3, 4, 3, 
 19 Desk:5, 
 20 
 21 Turn 5 result:
 22 Player A:6, 1, 1, 2, 2, 5, 5, 
 23 Player B:4, 3, 4, 3, 
 24 Desk:6, 
 25 
 26 Turn 6 result:
 27 Player A:1, 1, 2, 2, 5, 5, 6, 6, 
 28 Player B:3, 4, 3, 
 29 Desk:4, 
 30 
 31 Turn 7 result:
 32 Player A:1, 2, 2, 5, 5, 6, 6, 
 33 Player B:4, 3, 
 34 Desk:3, 1, 4, 
 35 
 36 Turn 8 result:
 37 Player A:2, 2, 5, 5, 6, 6, 1, 3, 1, 
 38 Player B:3, 4, 4, 
 39 Desk:
 40 
 41 Turn 9 result:
 42 Player A:2, 5, 5, 6, 6, 1, 3, 1, 
 43 Player B:4, 4, 
 44 Desk:3, 2, 
 45 
 46 Turn 10 result:
 47 Player A:5, 5, 6, 6, 1, 3, 1, 2, 3, 2, 
 48 Player B:4, 
 49 Desk:4, 
 50 
 51 Turn 11 result:
 52 Player A:5, 6, 6, 1, 3, 1, 2, 3, 2, 
 53 Player B:4, 5, 4, 
 54 Desk:
 55 
 56 Turn 12 result:
 57 Player A:6, 6, 1, 3, 1, 2, 3, 2, 
 58 Player B:5, 4, 
 59 Desk:4, 5, 
 60 
 61 Turn 13 result:
 62 Player A:6, 1, 3, 1, 2, 3, 2, 
 63 Player B:4, 5, 6, 4, 5, 
 64 Desk:
 65 
 66 Turn 14 result:
 67 Player A:1, 3, 1, 2, 3, 2, 
 68 Player B:5, 6, 4, 5, 
 69 Desk:4, 6, 
 70 
 71 Turn 15 result:
 72 Player A:3, 1, 2, 3, 2, 
 73 Player B:6, 4, 5, 
 74 Desk:5, 1, 4, 6, 
 75 
 76 Turn 16 result:
 77 Player A:1, 2, 3, 2, 
 78 Player B:4, 5, 6, 3, 5, 1, 4, 6, 
 79 Desk:
 80 
 81 Turn 17 result:
 82 Player A:2, 3, 2, 
 83 Player B:5, 6, 3, 5, 1, 4, 6, 
 84 Desk:4, 1, 
 85 
 86 Turn 18 result:
 87 Player A:3, 2, 
 88 Player B:6, 3, 5, 1, 4, 6, 
 89 Desk:5, 2, 4, 1, 
 90 
 91 Turn 19 result:
 92 Player A:2, 
 93 Player B:3, 5, 1, 4, 6, 
 94 Desk:6, 3, 5, 2, 4, 1, 
 95 
 96 Turn 20 result:
 97 Player A:2, 6, 3, 5, 2, 
 98 Player B:5, 1, 4, 6, 
 99 Desk:3, 4, 1, 
100 
101 Turn 21 result:
102 Player A:6, 3, 5, 2, 
103 Player B:1, 4, 6, 
104 Desk:5, 2, 3, 4, 1, 
105 
106 Turn 22 result:
107 Player A:3, 5, 2, 
108 Player B:4, 6, 1, 6, 5, 2, 3, 4, 1, 
109 Desk:
110 
111 Turn 23 result:
112 Player A:5, 2, 
113 Player B:6, 1, 6, 5, 2, 3, 4, 1, 
114 Desk:4, 3, 
115 
116 Turn 24 result:
117 Player A:2, 
118 Player B:1, 6, 5, 2, 3, 4, 1, 
119 Desk:6, 5, 4, 3, 
120 
121 Player B win.The cards in player B are:
122 1, 6, 5, 2, 3, 4, 1, 
123 The cards in the desk are:
124 2, 6, 5, 4, 3, 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏影子

SpringMVC接收复杂对象

34210
来自专栏一“技”之长

iOS SEL的理解与使用 原

   有很多人,认为block的推广可取代代理设计模式,其实block并不能取代代理,代理的模式可以让代码逻辑性更强,更整洁,也会有更高的可读性和可扩展性。相比...

554
来自专栏武培轩的专栏

剑指Offer-孩子们的游戏(圆圈中最后剩下的数)

package Other; import java.util.LinkedList; /** * 孩子们的游戏(圆圈中最后剩下的数) * 每年六一儿童...

2555
来自专栏HansBug's Lab

2729: [HNOI2012]排队

2729: [HNOI2012]排队 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 957  Solved:...

2695
来自专栏蜉蝣禅修之道

LeetCode之Climbing Stairs与斐波那契数列的联想

1304
来自专栏一英里广度一英寸深度的学习

SparkSQL 电影评价数据分析

Dataset调用createOrReplaceTempView生成临时表,session内有效。 spark.sql执行sqll操作,可以选择创建的临时表。

793
来自专栏知识分享

关于stm32的正交解码

关于正交解码,我先解释何为正交解码,,,,其实名字挺高大上的,,,,还是先说编码器吧 看一下我用过的一种编码器 ? ? ? 编码器的 线 数 ,是说编码器转一圈...

3176
来自专栏Jed的技术阶梯

Spark常用Actions算子

介绍以下Actions算子: foreach foreachPatition reduce collect count first take t...

481
来自专栏ml

HDUOJ----1181 变形课

变形课 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/65536 K (Java...

2896
来自专栏步履前行

Java8 LocalDate

3.一般用法 //当前时间 yyyy-MM-dd LocalDate now = LocalDate.now(); //根据制定的年月日生成LocalDate...

722

扫描关注云+社区