华为机试：连续出牌数量

【编程题目 |200分】连续出牌数量【2022 Q1,Q2考试题】

题目描述

• 手里给一副手牌，数字从0-9，有r(红色),，g(绿色），b(蓝色)，y(黄色)四种颜色，出牌规则为每次打出的牌必须跟上一张的数字或者颜色相同，否则不能抽选。
• 选手应该怎么选才能使得抽选的次数最大，并且输出这个最大次数。

输入描述

• 第一行 牌的数值n (1<=n<=9)
• 第二行 牌的颜色（r,g,b,y四种颜色表示)

输出描述

• 输出最大出牌数量

示例

输入

1 4 3 4 5
r y b b r
1
2

输出

3
1

说明

如果打（1, r）-> (5, r)，那么能打两张。

如果打（4，y) -> (4, b) -> (3, b)，那么能打三张。

思路分析

这道题还可以考虑BFS，相同数字或者相同颜色的都存入连续关系。

从第一个进如队列，统计每一个对应的最大次数，最后再更新最大值。

存入连续关系得时候可以使用二维list

以序号为索引，判断元素相同或颜色相同的都加入相应的list。

然后就是常规的BFS入队进行处理。

参考代码

import java.util.*;
import java.util.Scanner;

public class lianXuChupaiNum {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String[] str1 = in.nextLine().split(" ");
        String[] str2 = in.nextLine().split(" ");
        String[][] arr = new String[str1.length][2];
        for (int i = 0; i < str1.length; i++) {
            arr[i][0] = str1[i];
            arr[i][1] = str2[i];
        }
        // 存储相等关系
        List<List<Integer>> list = new ArrayList<>(arr.length);
        for (int i = 0; i < arr.length; i++) {  // 初始化
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (i != j) {
                    if (arr[i][0].equals(arr[j][0]) || arr[i][1].equals(arr[j][1])) {
                        list.get(i).add(j);
                    }
                }
            }
        }
        // BFS
        Queue<Integer> queue = new ArrayDeque<>();
        Queue<Integer> visited = new ArrayDeque<>();  // 用于判断是否访问过
        int res = 1;
        for (int i = 0; i < arr.length; i++) {
            int temp = 0;
            int[] result = new int[arr.length];
            Arrays.fill(result, 1);
            queue.add(i);
            visited.add(i);
            while (!queue.isEmpty()) {
                int poll = queue.poll();
                for (int node : list.get(poll)) {
                    if (!visited.contains(node)) {
                        visited.add(node);
                        result[node] = result[poll] + 1;
                        temp = Math.max(temp, result[node]);
                        queue.add(node);
                    }
                }
            }
            res = Math.max(res, temp);
        }
        System.out.println(res);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

欢迎在评论区指正以及留下自己的更简洁的方法。