Medium
题目描述
给你一个由字符串数组 cards 表示的卡牌组，每张卡牌显示两个小写字母。
还给你一个字母 x。你按照以下规则进行游戏：
- 从 0 分开始。
- 每一轮，你必须从卡牌组中找到两张兼容的卡牌，这两张卡牌都在任意位置包含字母
x。 - 移除这对卡牌并获得 1 分。
- 当你无法再找到一对兼容的卡牌时，游戏结束。
返回在最优策略下你能获得的最大分数。
如果两张卡牌的字符串恰好在 1 个位置不同，则它们是兼容的。
示例 1：
输入：cards = ["aa","ab","ba","ac"], x = "a"
输出：2
解释：
第一轮，选择并移除卡牌 "ab" 和 "ac"，它们兼容因为只在索引 1 处不同。
第二轮，选择并移除卡牌 "aa" 和 "ba"，它们兼容因为只在索引 0 处不同。
因为没有更多兼容的对，总分数是 2。
示例 2：
输入：cards = ["aa","ab","ba"], x = "a"
输出：1
解释：
第一轮，选择并移除卡牌 "aa" 和 "ba"。
因为没有更多兼容的对，总分数是 1。
示例 3：
输入：cards = ["aa","ab","ba","ac"], x = "b"
输出：0
解释：
只有包含字符 'b' 的卡牌是 "ab" 和 "ba"。然而，它们在两个索引处都不同，所以不兼容。因此，输出是 0。
约束条件：
2 <= cards.length <= 10^5cards[i].length == 2- 每个
cards[i]只由 ‘a’ 到 ‘j’ 之间的小写英文字母组成 x是 ‘a’ 到 ‘j’ 之间的小写英文字母
解题思路
解题思路
这道题的关键在于理解"兼容"的定义：两张卡牌恰好在一个位置不同。我们需要对包含字符 x 的卡牌进行分类统计，然后运用最优匹配策略。
分类统计：
both：两个位置都是x的卡牌数量（如 “xx”）cnt1[c]：第一个位置是x，第二个位置是字符c的卡牌数量（如 “xc”）cnt2[c]：第一个位置是字符c，第二个位置是x的卡牌数量（如 “cx”）
兼容关系分析：
- 两张都在同一位置有
x的卡牌：只有当另一位置字符相同时才兼容 - 一张两个位置都是
x，另一张只有一个位置是x：总是兼容 - 一张第一个位置是
x，另一张第二个位置是x：当非x位置字符相同时兼容
最优策略：
使用动态规划思想，枚举将多少张双 x 卡牌分配给第一类单 x 卡牌，剩余的分配给第二类。对于每种分配，分别计算最大匹配数，取所有方案的最大值。
代码实现
class Solution {
public:
int solve(vector<int>& cnt, int have) {
sort(cnt.rbegin(), cnt.rend());
int ans = 0;
for (int c : cnt) {
int pairs = min(have, c);
ans += pairs;
have -= pairs;
ans += c / 2;
}
return ans;
}
int score(vector<string>& cards, char x) {
int both = 0;
vector<int> cnt1(10, 0), cnt2(10, 0);
for (const string& card : cards) {
bool hasX1 = (card[0] == x);
bool hasX2 = (card[1] == x);
if (hasX1 && hasX2) {
both++;
} else if (hasX1) {
cnt1[card[1] - 'a']++;
} else if (hasX2) {
cnt2[card[0] - 'a']++;
}
}
int maxScore = 0;
for (int i = 0; i <= both; i++) {
int score1 = solve(cnt1, i);
int score2 = solve(cnt2, both - i);
maxScore = max(maxScore, score1 + score2);
}
return maxScore;
}
};
class Solution:
def solve(self, cnt, have):
cnt.sort(reverse=True)
ans = 0
for c in cnt:
pairs = min(have, c)
ans += pairs
have -= pairs
ans += c // 2
return ans
def score(self, cards: List[str], x: str) -> int:
both = 0
cnt1 = [0] * 10
cnt2 = [0] * 10
for card in cards:
hasX1 = card[0] == x
hasX2 = card[1] == x
if hasX1 and hasX2:
both += 1
elif hasX1:
cnt1[ord(card[1]) - ord('a')] += 1
elif hasX2:
cnt2[ord(card[0]) - ord('a')] += 1
maxScore = 0
for i in range(both + 1):
score1 = self.solve(cnt1[:], i)
score2 = self.solve(cnt2[:], both - i)
maxScore = max(maxScore, score1 + score2)
return maxScore
public class Solution {
private int Solve(int[] cnt, int have) {
Array.Sort(cnt, (a, b) => b.CompareTo(a));
int ans = 0;
foreach (int c in cnt) {
int pairs = Math.Min(have, c);
ans += pairs;
have -= pairs;
ans += c / 2;
}
return ans;
}
public int Score(string[] cards, char x) {
int both = 0;
int[] cnt1 = new int[10];
int[] cnt2 = new int[10];
foreach (string card in cards) {
bool hasX1 = card[0] == x;
bool hasX2 = card[1] == x;
if (hasX1 && hasX2) {
both++;
} else if (hasX1) {
cnt1[card[1] - 'a']++;
} else if (hasX2) {
cnt2[card[0] - 'a']++;
}
}
int maxScore = 0;
for (int i = 0; i <= both; i++) {
int[] temp1 = (int[])cnt1.Clone();
int[] temp2 = (int[])cnt2.Clone();
int score1 = Solve(temp1, i);
int score2 = Solve(temp2, both - i);
maxScore = Math.Max(maxScore, score1 + score2);
}
return maxScore;
}
}
var score = function(cards, x) {
const solve = (cnt, have) => {
cnt.sort((a, b) => b - a);
let ans = 0;
for (const c of cnt) {
const pairs = Math.min(have, c);
ans += pairs;
have -= pairs;
ans += Math.floor(c / 2);
}
return ans;
};
let both = 0;
const cnt1 = new Array(10).fill(0);
const cnt2 = new Array(10).fill(0);
for (const card of cards) {
const hasX1 = card[0]
复杂度分析
| 复杂度 | 大小 |
|---|---|
| 时间复杂度 | O(n + k²) |
| 空间复杂度 | O(k) |
其中 n 是卡牌数量，k = 10 是字符集大小。时间复杂度中的 k² 来自于枚举分配方案和排序操作。