OD统一考试（C卷）
分值： 200分
题解： Java / Python / C++
题目描述
有这么一款单人卡牌游戏，牌面由颜色和数字组成，颜色为红、黄、蓝、绿中的一种，数字为 0−9 中的一个。游戏开始时玩家从手牌中选取一张卡牌打出，接下来如果玩家手中有和他上一次打出的手牌颜色或者数字相同的手牌，他可以继续将该手牌打出，直至手牌打光或者没有符合条件可以继续打出的手牌。
现给定一副手牌，请找到最优的出牌策略，使打出的手牌最多。
输入描述
第一行是每张手牌的数字，数字由空格分隔
第二行为对应的每张手牌的颜色，用 rybg 这 4 个字母分别代表 4 种颜色，字母也由空格分隔。
手牌数量不超过10。
输出描述
输出一个数字，即最多能打出的手牌的数量。
示例1
输入：
1 4 3 4 5
r y b b r
输出：
3
说明：
如果打(1,r）-> (5,r)，那么能打两张。如果打(4，y) -> (4,b) -> (3,b)，那么能打三张。
示例2
输入：
1 2 3 4
r y b l
输出：
1
说明：
没有能够连续出牌的组合，只能在开始时打出一张手牌，故输出 1 。
题解
题目类型： 深度优先搜索（DFS）
解题思路：
- 通过深度优先搜索遍历所有可能的出牌组合。
- 维护一个全局变量
maxCnt，记录最多能打出的手牌数。- 递归函数
dfs中，遍历未使用过的手牌，判断是否能打出。如果可以，标记为已使用，继续递归下一层。- 在递归的过程中更新
maxCnt。- 最终返回
maxCnt。时间复杂度： 搜索的时间复杂度取决于搜索空间的大小，最坏情况下为 O(2^n)，其中 n 为手牌数量。每张牌有两种状态：打出或不打出。
空间复杂度： 递归调用的深度为手牌数量，因此空间复杂度为 O(n)。
Java
import java.util.Arrays;
import java.util.Objects;
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 读取卡牌数字列表
int[] nums = Arrays.stream(in.nextLine().split(" "))
.mapToInt(Integer::parseInt).toArray();
// 读取卡牌颜色列表
String[] colors = in.nextLine().split(" ");
Solution solution = new Solution();
// 调用 solve 方法求解并输出结果
int result = solution.solve(nums, colors);
System.out.println(result);
}
}
class Solution {
private int maxCnt;
public int solve(int[] nums, String[] colors) {
this.maxCnt = 0;
dfs(-1, 0, nums, colors, new boolean[nums.length]);
return this.maxCnt;
}
private void dfs(int prev, int cnt, int[] nums, String[] colors, boolean[] vis) {
// 更新最多可以打出的手牌数
this.maxCnt = Math.max(cnt, this.maxCnt);
for (int cur = 0; cur < nums.length; cur++) {
if (vis[cur]) continue;
// 之前未打出牌 或 和前面牌数相同 或 和前面牌颜色相同
if (prev == -1 || nums[prev] == nums[cur] || Objects.equals(colors[prev], colors[cur])) {
vis[cur] = true;
dfs(cur, cnt + 1, nums, colors, vis); // 打出当前的牌
vis[cur] = false;
}
}
}
}
Python
from typing import List
def solve(nums: List[int], colors: list[str]) -> int:
# 卡牌数量， 最多可以打出的手牌数
n, max_cnt = len(nums), 0
vis = [False] * n
def dfs(prev, cnt):
"""
param: prev 前一张打出的牌
param: cnt 已经打出的手牌数
"""
nonlocal max_cnt, n, vis
max_cnt = max(cnt, max_cnt) # 更新最多可以打出的手牌数
for cur in range(n):
if vis[cur]:
continue
# 之前未打出牌 或 和前面牌数相同 或 和前面牌颜色相同
if prev == -1 or nums[prev] == nums[cur] or colors[prev] == colors[cur]:
vis[cur] = True
dfs(cur, cnt + 1) # 打出 cur 当前的牌
vis[cur] = False
dfs(-1, 0)
return max_cnt
if __name__ == "__main__":
nums = list(map(int, input().split()))
colors = list(map(str, input().split()))
print(solve(nums, colors))
C++
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
template <typename T>
vector<T> readList() {
string input;
getline(cin, input);
stringstream stream(input);
vector<T> result;
T value;
while (stream >> value) {
result.push_back(value);
}
return result;
}
int maxCnt;
void dfs(int prev, int cnt, vector<int>& nums, vector<string>& colors, vector<bool>& vis) {
// 更新最多可以打出的手牌数
maxCnt = max(cnt, maxCnt);
for (size_t cur = 0; cur < nums.size(); cur++) {
if (vis[cur]) continue;
// 之前未打出牌 或 和前面牌数相同 或 和前面牌颜色相同
if (prev == -1 || nums[prev] == nums[cur] || colors[prev] == colors[cur]) {
vis[cur] = true;
dfs(cur, cnt + 1, nums, colors, vis); // 打出当前的牌
vis[cur] = false;
}
}
}
int main() {
// 读取卡牌数字列表
vector<int> nums = readList<int>();
// 读取卡牌颜色列表
vector<string> colors = readList<string>();
maxCnt = 0;
// 调用 dfs 方法求解并输出结果
vector<bool> vis(nums.size(), false);
dfs(-1, 0, nums, colors, vis);
cout << maxCnt << endl;
return 0;
}
❤️华为OD机试面试交流群（每日真题分享）： 加V时备注“华为od加群”
🙏整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
