最长连续手牌

题目描述

有这么一款单人卡牌游戏，牌面由颜色和数字组成，颜色为红、黄、蓝、绿中的一种，数字为 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）

解题思路：

1. 通过深度优先搜索遍历所有可能的出牌组合。
2. 维护一个全局变量 maxCnt，记录最多能打出的手牌数。
3. 递归函数 dfs 中，遍历未使用过的手牌，判断是否能打出。如果可以，标记为已使用，继续递归下一层。
4. 在递归的过程中更新 maxCnt。
5. 最终返回 maxCnt。

时间复杂度： 搜索的时间复杂度取决于搜索空间的大小，最坏情况下为 O(2^n)，其中 n 为手牌数量。每张牌有两种状态：打出或不打出。

空间复杂度： 递归调用的深度为手牌数量，因此空间复杂度为 O(n)。

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;
}

希望这个专栏能让您熟练掌握算法, 🎁🎁🎁 立即订阅。

整理题解不易， 如果有帮助到您，请给点个赞 ‍❤️‍ 和收藏 ⭐，让更多的人看到。🙏🙏🙏