华为OD新系统机试真题 华为OD新系统上机考试真题 4月15号 200分题型

小猫钓鱼纸牌游戏(C/C++/Py/Java/Js/Go)题解，可点击查看

题目描述

有两名玩家甲和乙，他们玩一种“小猫钓鱼”扑克牌游戏。扑克牌为 A、2、3、…、J、Q、K，不考虑花色都用 1−13来表示，然后给甲、乙两人各发 n 张牌，按给定顺序排成队列，这些牌背面朝上，正面朝下放置，队列的第一个元素是背面的第一张牌。

游戏规则如下:

1. 出牌与收牌
   • 初始出牌时，甲先出牌，打出的牌正面朝上放在桌面的最底部，然后乙出牌，正面朝上放在甲的牌张上面，然后甲乙轮流出牌，直到触发收牌或者任意一个玩家牌出完。
   • 如果玩家出牌后触发了收牌，则把收到的一摞牌作为整体翻面后，背面朝上正面朝下放到现有牌的底部，然后当前收牌的玩家继续出牌。
2. 收牌规则
   • 若当前打出的牌点数，与桌面上之前某张牌的点数相同，则触发收牌，收牌的范围是两张相同点数牌之间的所有牌(含这两张)。
   • 若当前打出的牌是 J，并且此时桌面上已有至少一张牌(不含当前这张)，则当前玩家触发收牌，收牌的范围是桌面上的所有牌。若桌面上原本没有牌，则 J仅作为普通牌放到桌面
3. 游戏结束条件
   • 若某位玩家在自己回合开始时已经没有牌可出，则游戏立即结束，如果此时对方还有余牌，则对方获胜，如果对方也无牌，则平局。
   • 若在模拟过程中，出牌总次数超过一个上限(10000 次)仍未结束，则认为游戏进入死循环，判定为平局。

输入描述

甲的初始牌队列和乙的初始牌队列，甲乙初始手牌数量相等，均为整数 n(1≤n≤100)

输出描述

一方获胜时，输出获胜方手中背面朝上最上方的那张牌的数值。若平局，如果桌面无牌则输出 0，否则输出当前桌面上正面朝上的最上方的那张牌的数值。

用例1

输入

1,2
10,12

输出

12

说明

甲的牌堆为1,2

乙的牌堆为10,12

出牌顺序:甲出 1，乙出 10，甲出 2，乙出 12，甲无牌可出，乙无余牌，游戏结束，平局。

桌面牌堆为1,10,2,12

平局输出桌面排队正面朝上最上牌值12.

用例2

输入

1,3
1,3

输出

1

说明

甲的牌堆为1,3
乙的牌堆为1,3
出牌顺序
1. 甲出1，剩余3,桌面1
2. 乙出1，剩余3，匹配桌面1，拿走1,1，桌面牌为空。放回乙，乙当前变为3,1,1
3. 乙出3，剩余1,1 桌面为3
4. 甲出3，匹配桌面的3，拿走3,3，桌面牌为空,甲变为3,3
5. 甲出3，剩余3，桌面为3
6. 乙出1，剩余1，桌面为3，1
7. 甲出3，匹配桌面上的3，桌面变为空，甲变为3,1,3
8. 甲出3，剩余1,3，桌面3
9. 乙出1，乙变为空，桌面变为3，1
10.甲出1，剩余3，匹配桌面1，拿走1,1，桌面变为3，甲变为3,1,1
11 甲出3, 剩余1,1 匹配桌面3，拿走3,3 桌面变为空，甲变成1,1,3,3
12.甲出3，变为1,3,3 桌面为1
13.乙无牌可出，甲获胜，甲牌非空，输出背面最朝上的牌1

题解

思路

思路: 纯模拟题

1. 使用双端队列维持当前甲乙手头牌的信息，桌面牌可使用数组保存，对于判断桌面牌中是否有与当前牌相同判断可以使用一个pos[14]数组，pos[i]记录在i面值在桌面牌中位置，不存在值为-1.
2. 整体思路如下
   • 初始创建pos数组值全设为-1，根据输入创建甲乙牌状态信息的双端对了，创建桌面牌数组。
   • 对于当前出牌一方，首先判断是否还有牌可出？
     • 没有牌可出，判断对方是否有牌可出？
       • 对手也无牌可出，接下来根据桌面牌得出结果，为空返回0，不为空返回最上方牌的值。
       • 对手有牌，返回获胜方手中背面朝上最上方的那张牌的数值
     • 继续执行下面逻辑
   • 利用pos判断当前要出的牌桌面牌中是否存在， 判断桌面牌是否为空，得到这两个信息之后，判断当前出牌是否能够收牌，能够收牌的情况下记录收牌的起始位置，根据题目给出的两个情况之一
     • 当前牌为J且桌面牌不为空，起始位置为0(包含)
     • 桌面牌存在与当前打的牌相同，起始位置就为pos中记录位置
   • 当前是否能收牌分情况处理？
     • 不能收牌，切换打牌用户
     • 能收牌，将桌面牌{起始索引，尾部}的牌按从前向后顺序压入当前出牌方队尾。注意此时也需要设置移除桌面牌的pos值为-1。处理完这个逻辑，不切换打牌用户继续执行逻辑。
3. 根据2的逻辑进行模拟，如果打牌次数超过10000，此时为平局，如果桌面牌为空返回0，不为空返回最上方牌的值。

code

import java.util.*;

public class Main {

    // 通用切割函数
    static List<Integer> split(String str, String delimiter) {
        List<Integer> res = new ArrayList<>();
        String[] arr = str.split(delimiter);
        for (String s : arr) {
            res.add(Integer.parseInt(s));
        }
        return res;
    }

    static int fishGame(List<Integer> aCard, List<Integer> bCard) {
        Deque<Integer> a = new ArrayDeque<>(aCard);
        Deque<Integer> b = new ArrayDeque<>(bCard);

        // 牌桌上的牌
        List<Integer> tableCard = new ArrayList<>();

        // 0 表示甲出牌 1表示乙出牌
        int current = 0;

        // 维护牌面值在牌桌上出现的位置
        int[] pos = new int[14];
        Arrays.fill(pos, -1);

        for (int i = 0; i <= 10000; i++) {
            Deque<Integer> currentCard = (current == 0) ? a : b;
            Deque<Integer> otherCard = (current == 0) ? b : a;

            // 当前出牌牌堆为空
            if (currentCard.isEmpty()) {
                if (!otherCard.isEmpty()) return otherCard.peekFirst();
                return tableCard.isEmpty() ? 0 : tableCard.get(tableCard.size() - 1);
            }

            int val = currentCard.pollFirst();

            int samePos = pos[val];
            boolean tableEmptyFlag = tableCard.isEmpty();

            tableCard.add(val);
            pos[val] = tableCard.size() - 1;

            boolean takeUpFlag = false;
            int takeUpStart = -1;

            // J收牌
            if (val == 11 && !tableEmptyFlag) {
                takeUpFlag = true;
                takeUpStart = 0;
            } else if (samePos != -1) {
                takeUpFlag = true;
                takeUpStart = samePos;
            }

            if (takeUpFlag) {
                List<Integer> takeUpCard = tableCard.subList(takeUpStart, tableCard.size());
                List<Integer> copy = new ArrayList<>(takeUpCard);
                tableCard.subList(takeUpStart, tableCard.size()).clear();

                for (int v : copy) {
                    pos[v] = -1;
                    currentCard.addLast(v);
                }
            } else {
                current ^= 1;
            }
        }

        return tableCard.isEmpty() ? 0 : tableCard.get(tableCard.size() - 1);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String a = sc.nextLine();
        String b = sc.nextLine();

        List<Integer> aCard = split(a, ",");
        List<Integer> bCard = split(b, ",");

        System.out.println(fishGame(aCard, bCard));
    }
}