【华为OD-E卷 - 连续出牌数量 100分（python、java、c++、js、c）】
【华为OD-E卷 - 连续出牌数量 100分（python、java、c++、js、c）】
题目
有这么一款单人卡牌游戏，牌面由颜色和数字组成，颜色为红、黄、蓝、绿中的一种，数字为0-9中的一个。游戏开始时玩家从手牌中选取一张卡牌打出，接下来如果玩家手中有和他上一次打出的手牌颜色或者数字相同的手牌，他可以继续将该手牌打出，直至手牌打光或者没有符合条件可以继续打出的手牌。
现给定一副手牌，请找到最优的出牌策略，使打出的手牌最多
输入描述
- 输入为两行
第一行是每张手牌的数字，数字由空格分隔， 第二行为对应的每张手牌的颜色，用r y b g这4个字母分别代表4种颜色，字母也由空格分隔。 手牌数量不超过10
输出描述
- 输出一个数字，即最多能打出的手牌的数量
用例
用例一：
输入：
1 4 3 4 5
r y b b r
输出：
3
用例二：
输入：
1 2 3 4
r y b l
输出：
1
python解法
- 解题思路：
- 这段代码的目标是计算最长的连续牌链，其中：
每张牌有两个属性：值 (val) 和 花色 (shd)。
连续牌的规则：
相邻的两张牌，必须满足 值相同 或者 花色相同。
解题步骤
输入读取：
第一行 values 代表所有牌的值（如 [‘A’, ‘2’, ‘3’]）。
第二行 shades 代表所有牌的花色（如 [‘H’, ‘D’, ‘H’]）。
初始化 Card 对象：
使用 Card 类表示牌，包含 val（值）和 shd（花色）。
深度优先搜索 (DFS) 计算最长牌链：
采用回溯法遍历所有可能的排列，计算最长合法链的长度。
search() 递归搜索：
遍历所有未访问的牌。
确保当前牌 current 与上一张牌 previous 满足条件：
previous.val == current.val 或者 previous.shd == current.shd。
继续递归，直到所有可能的链都遍历完。
输出最长链的长度：
max_depth[0] 记录当前最长链的长度。
# 输入获取
values = input().split() # 读取牌的值
shades = input().split() # 读取牌的花色
# 定义牌的类，每张牌有 "值" 和 "花色"
class Card:
def __init__(self, val, shd):
self.val = val # 牌的值
self.shd = shd # 牌的花色
# 递归搜索最长的合法牌链
def search(sequence, visited, previous, depth, max_depth):
# 更新当前最长链的深度
max_depth[0] = max(max_depth[0], depth)
# 遍历所有牌，尝试加入当前链
for idx in range(len(sequence)):
if visited[idx]: # 如果该牌已被使用，则跳过
continue
current = sequence[idx]
# 如果有前一张牌，检查是否符合连续条件 (值相同 或 花色相同)
if previous and previous.val != current.val and previous.shd != current.shd:
continue # 如果不符合，跳过该牌
# 选择该牌，并继续搜索
visited[idx] = True
search(sequence, visited, current, depth + 1, max_depth)
visited[idx] = False # 回溯，撤销选择
# 计算最长合法牌链的函数
def calculate_max_chain():
total = len(values) # 牌的总数
# 生成牌的列表，每张牌是一个 Card 对象
deck = [Card(values[i], shades[i]) for i in range(total)]
max_depth = [0] # 记录最长链的长度
visited = [False] * total # 记录哪些牌已经使用
# 开始深度优先搜索，查找最长牌链
search(deck, visited, None, 0, max_depth)
return max_depth[0] # 返回最长链的长度
# 输出最长合法牌链的长度
print(calculate_max_chain())
java解法
- 解题思路
- 该程序的目的是计算最长的连续牌链，其中：
每张牌包含值 (val) 和 颜色 (col)。
牌链的规则：
相邻的牌，必须满足值相同或颜色相同。
解题步骤
读取输入
第一行输入为整数数组 vals，代表所有牌的值。
第二行输入为字符串数组 cols，代表所有牌的颜色。
创建 Tile 类
Tile 类存储每张牌的值和颜色。
回溯搜索 (DFS)
采用**回溯 + 深度优先搜索（DFS）**遍历所有可能的排列，计算最长合法链的长度。
变量说明：
vis[]：布尔数组，标记当前牌是否被使用。
prev：表示当前牌链中的上一张牌。
maxChain[0]：存储最长牌链的长度。
递归 search() 方法
遍历所有牌，尝试加入牌链：
如果当前牌 cur 和上一张牌 prev 不符合值或颜色相同的规则，则跳过。
标记 vis[i] = true，递归搜索下一张牌。
回溯 (vis[i] = false)，撤销选择，继续搜索其他可能路径。
最终返回 maxChain[0] 作为最长合法牌链的长度
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取第一行输入（牌的值）并转换为整数数组
int[] vals = Arrays.stream(sc.nextLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
// 读取第二行输入（牌的颜色）并存储为字符串数组
String[] cols = sc.nextLine().split(" ");
// 计算最长合法牌链
System.out.println(calc(vals, cols));
}
// 定义Tile类，表示每张牌
static class Tile {
int val; // 牌的值
char col; // 牌的颜色（用字符表示）
public Tile(int val, String col) {
this.val = val;
this.col = col.charAt(0); // 取颜色字符串的第一个字符
}
}
// 计算最长合法牌链
public static int calc(int[] vals, String[] cols) {
int len = vals.length;
Tile[] tiles = new Tile[len];
// 创建牌的数组，每张牌由值和颜色组成
for (int i = 0; i < len; i++) {
tiles[i] = new Tile(vals[i], cols[i]);
}
int[] maxChain = {0}; // 存储最长牌链长度
boolean[] vis = new boolean[len]; // 记录哪些牌已经使用
// 进行深度优先搜索（DFS）
search(tiles, vis, null, 0, maxChain);
return maxChain[0]; // 返回最长牌链的长度
}
// 递归搜索最长的合法牌链
public static void search(Tile[] tiles, boolean[] vis, Tile prev, int len, int[] maxChain) {
// 更新最长牌链长度
maxChain[0] = Math.max(maxChain[0], len);
// 遍历所有牌，尝试加入牌链
for (int i = 0; i < tiles.length; i++) {
if (vis[i]) continue; // 如果该牌已被使用，则跳过
Tile cur = tiles[i];
// 如果前一张牌存在，检查是否符合连续条件 (值相同 或 颜色相同)
if (prev != null && prev.val != cur.val && prev.col != cur.col) continue;
// 选择该牌，并继续搜索
vis[i] = true;
search(tiles, vis, cur, len + 1, maxChain);
vis[i] = false; // 回溯，撤销选择
}
}
}
C++解法
- 解题思路
更新中
C解法
每张牌包含数字 (num) 和 颜色 (color)。
牌链的规则：
相邻的牌，必须满足数字相同或颜色相同。
解题步骤
读取输入
先读取一行整数，表示牌的数字，存入 cards[i].num。
然后读取一行字符，表示牌的颜色，存入 cards[i].color。
深度优先搜索（DFS）
使用 bfs()（其实是递归深度优先搜索，函数命名 bfs 可能是误导）。
变量说明：
used[]：布尔数组，标记当前牌是否被使用。
lastCard：表示当前牌链中的上一张牌。
maxCount：存储最长牌链的长度。
递归 bfs() 计算最长合法牌链
遍历所有牌：
如果当前牌 current 和 lastCard 不符合数字或颜色相同的规则，则跳过。
标记 used[i] = 1，递归搜索下一张牌。
回溯 (used[i] = 0)，撤销选择，继续搜索其他可能路径。
最终返回 maxCount 作为最长合法牌链的长度
#include <stdio.h>
#include <stdbool.h>
#define MAX_SIZE 10 // 假设最多 10 张牌
// 结构体表示一张牌
typedef struct {
int num; // 牌的数字
char color; // 牌的颜色
} Card;
int maxCount = 0; // 记录最长牌链的长度
Card cards[MAX_SIZE]; // 存储牌组
int cardsSize = 0; // 牌的总数量
void dfs(int used[], Card* lastCard, int count); // 递归搜索函数
int main() {
// 读取牌的数字
while (scanf("%d", &cards[cardsSize].num)) {
cardsSize++;
if (getchar() != ' ') break; // 遇到换行，停止读取
}
// 读取牌的颜色
for (int i = 0; i < cardsSize; i++) {
cards[i].color = (char)getchar(); // 读取字符颜色
getchar(); // 跳过空格或换行
}
int used[MAX_SIZE] = {0}; // 记录哪些牌已被使用
dfs(used, NULL, 0); // 开始深度优先搜索
printf("%d\n", maxCount); // 输出最长合法牌链长度
return 0;
}
// 递归搜索最长牌链
void dfs(int used[], Card* lastCard, int count) {
// 更新最长牌链的长度
if (count > maxCount) {
maxCount = count;
}
// 遍历所有牌，尝试加入牌链
for (int i = 0; i < cardsSize; i++) {
if (used[i]) continue; // 如果该牌已被使用，跳过
Card current = cards[i];
// 如果 lastCard 存在，检查是否符合连续规则（数字相同 或 颜色相同）
if (lastCard == NULL || lastCard->num == current.num || lastCard->color == current.color) {
used[i] = 1; // 标记该牌为已使用
dfs(used, ¤t, count + 1); // 递归搜索
used[i] = 0; // 回溯，撤销选择
}
}
}
JS解法
更新中
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏