题目描述与示例
题目描述
斗地主起源于湖北十堰房县，据传是一位叫吴修全的年轻人根据当地流行的扑克玩法“跑得快”改编的，如今已风靡整个中国，并流行于互联网上。
牌型：单顺，又称顺子，最少 5 张牌，最多 12 张牌( 3...A )，不能有 2，也不能有大小王，不计花色。 例如：3-4-5-7-8，7-8-9-10-J-Q，3-4-5-6-7-8-9-10-J-Q-K-A 可用的牌 3<4<5<6<7<8<9<10<J<Q<K<A<2<B(小王)<C(大王)， 每种牌除大小王外有 4 种花色(共有 13X4+2 张牌)
输入描述
- 手上已有的牌
- 已经出过的牌(包括对手出的和自己出的牌)
输出描述
对手可能构成的最长的顺子（如果有相同长度的顺子，输出牌面最大的那一个)，如果无法构成顺子，则输出 NO-CHAIN
示例一
输入
3-3-3-3-4-4-5-5-6-7-8-9-10-J-Q-K-A
4-5-6-7-8-8-8
输出
9-10-J-Q-K-A
示例二
输入
3-3-3-3-8-8-8-8
K-K-K-K
输出
NO-CHAIN
解题思路
比较常规的哈希表题目，但由于涉及到字符和数字之间的相互转换，即"J"、"Q"、"K"、"A"和数字11、12、13、14之间的相互转换，故代码比较长，需要细心完成。
代码
Python
# 题目：2023B-斗地主
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：哈希表
# 代码看不懂的地方，请直接在群上提问
from collections import Counter, defaultdict
# 将手上的牌、已经打出的牌储存为lst1和lst2
# 注意这里没有转换成数字，元素仍为字符串
lst1 = input().split("-")
lst2 = input().split("-")
# 使用计数器Counter，储存所有已经使用过的牌的个数
# 注意这里的key是str类型
cnt_using_str = Counter(lst1 + lst2)
# 如果存在2和大小王"B"、"C"
# 因为不影响顺子的判断，可以直接删去
del cnt_using_str["2"]
del cnt_using_str["B"]
del cnt_using_str["C"]
# 构建将字符转换为数字的哈希映射
convert_dic = {f"{num}": num for num in range(3, 11)}
convert_dic["J"] = 11
convert_dic["Q"] = 12
convert_dic["K"] = 13
convert_dic["A"] = 14
# 构建将数字转换为字符的哈希映射
convert_dic2 = {num: f"{num}" for num in range(3, 11)}
convert_dic2[11] = "J"
convert_dic2[12] = "Q"
convert_dic2[13] = "K"
convert_dic2[14] = "A"
# 将cnt_using_str里的key转化为int类型，对应的value不变
# 储存在一个新的哈希表cnt_using_num中
cnt_using_num = defaultdict(int)
for k, v in cnt_using_str.items():
cnt_using_num[convert_dic[k]] = v
# 初始化三个变量
# 当前顺子长度、最长顺子长度、最长顺子对应的答案ans
cur_length = 0
max_length = 0
ans = "NO-CHAIN"
# 考虑3-15的所有数字
# 其中J、Q、K、A分别对应11、12、13、14
for i in range(3, 16):
# 数字i被用完的情况，即在cnt_using_num中的值为4
# 之所以把15也加入考虑
# 是因为i取14时，若没有仍然可以延长cur_length
# 会进入else中的分支，而无法实现ans的更新
if cnt_using_num[i] == 4 or i == 15:
# 若此时cur_length大于之前储存的max_length
# 且cur_length大于等于5（顺子长度最低的要求）
if cur_length >= max_length and cur_length >= 5:
# 此时顺子为：i-cur_length, ..., i-3, i-2, i-1
# 更新答案，注意这里要使用convert_dic2哈希表
# 把数字重新转回字母后，再合并
ans = "-".join(convert_dic2[j] for j in range(i-cur_length, i))
max_length = cur_length
# 顺子当前长度需要重置为0
cur_length = 0
# 数字i没被用完的情况，可以继续延长顺子
# cur_length+1
else:
cur_length += 1
print(ans)
Java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] lst1 = scanner.nextLine().split("-");
String[] lst2 = scanner.nextLine().split("-");
Map<String, Integer> cntUsingStr = new HashMap<>();
for (String card : lst1) {
cntUsingStr.put(card, cntUsingStr.getOrDefault(card, 0) + 1);
}
for (String card : lst2) {
cntUsingStr.put(card, cntUsingStr.getOrDefault(card, 0) + 1);
}
cntUsingStr.remove("2");
cntUsingStr.remove("B");
cntUsingStr.remove("C");
Map<String, Integer> convertDic = new HashMap<>();
for (int num = 3; num <= 10; num++) {
convertDic.put(String.valueOf(num), num);
}
convertDic.put("J", 11);
convertDic.put("Q", 12);
convertDic.put("K", 13);
convertDic.put("A", 14);
Map<Integer, String> convertDic2 = new HashMap<>();
for (int num = 3; num <= 10; num++) {
convertDic2.put(num, String.valueOf(num));
}
convertDic2.put(11, "J");
convertDic2.put(12, "Q");
convertDic2.put(13, "K");
convertDic2.put(14, "A");
Map<Integer, Integer> cntUsingNum = new HashMap<>();
for (Map.Entry<String, Integer> entry : cntUsingStr.entrySet()) {
int num = convertDic.get(entry.getKey());
cntUsingNum.put(num, entry.getValue());
}
int curLength = 0;
int maxLength = 0;
String ans = "NO-CHAIN";
for (int i = 3; i <= 15; i++) {
if (cntUsingNum.getOrDefault(i, 0) == 4 || i == 15) {
if (curLength >= maxLength && curLength >= 5) {
List<String> sequence = new ArrayList<>();
for (int j = i - curLength; j < i; j++) {
sequence.add(convertDic2.get(j));
}
ans = String.join("-", sequence);
maxLength = curLength;
}
curLength = 0;
} else {
curLength++;
}
}
System.out.println(ans);
}
}
C++
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main() {
string input1, input2;
getline(cin, input1);
getline(cin, input2);
vector<string> lst1;
vector<string> lst2;
string card;
for (char c : input1) {
if (c == '-') {
lst1.push_back(card);
card = "";
} else {
card += c;
}
}
lst1.push_back(card);
card = "";
for (char c : input2) {
if (c == '-') {
lst2.push_back(card);
card = "";
} else {
card += c;
}
}
lst2.push_back(card);
map<string, int> cntUsingStr;
for (string card : lst1) {
cntUsingStr[card]++;
}
for (string card : lst2) {
cntUsingStr[card]++;
}
cntUsingStr.erase("2");
cntUsingStr.erase("B");
cntUsingStr.erase("C");
map<string, int> convertDic;
for (int num = 3; num <= 10; num++) {
convertDic[to_string(num)] = num;
}
convertDic["J"] = 11;
convertDic["Q"] = 12;
convertDic["K"] = 13;
convertDic["A"] = 14;
map<int, string> convertDic2;
for (int num = 3; num <= 10; num++) {
convertDic2[num] = to_string(num);
}
convertDic2[11] = "J";
convertDic2[12] = "Q";
convertDic2[13] = "K";
convertDic2[14] = "A";
map<int, int> cntUsingNum;
for (auto entry : cntUsingStr) {
int num = convertDic[entry.first];
cntUsingNum[num] = entry.second;
}
int curLength = 0;
int maxLength = 0;
string ans = "NO-CHAIN";
for (int i = 3; i <= 15; i++) {
if (cntUsingNum[i] == 4 || i == 15) {
if (curLength >= maxLength && curLength >= 5) {
vector<string> sequence;
for (int j = i - curLength; j < i; j++) {
sequence.push_back(convertDic2[j]);
}
ans = "";
for (int j = 0; j < sequence.size(); j++) {
ans += sequence[j];
if (j < sequence.size() - 1) {
ans += "-";
}
}
maxLength = curLength;
}
curLength = 0;
} else {
curLength++;
}
}
cout << ans << endl;
return 0;
}
时空复杂度
时间复杂度：O(N)。主要是构建哈希表所需要的时间。
空间复杂度：O(1)。哈希表的长度不会大于15，可视为常数级别空间。
