【哈希表】2023A-集五福
【哈希表】2023A-集五福
题目描述与示例
本题练习地址：https://www.algomooc.com/problem/P2800
集五福
题目描述
集五福作为近年来大家喜闻乐见迎新春活动，集合爱国福、富强福、和谐福、友善福、敬业福即可分享超大红包。以 0 和 1 组成的长度为 5 的字符串代表每个人所得到的福卡，每一位代表一种福卡，1 表示已经获得该福卡，单类型福卡不超过 1 张，随机抽取一个小于 10 人团队，求该团队最多可以集齐多少套五福？
输入描述
输入若干个由0、1组成的长度等于5的字符串，代表团队中每个人福卡获得情况 注意1：1人也可以是一个团队 注意2：1人可以有0到5张福卡，但福卡不能重复
输出描述
输出该团队最多能凑齐多少套五福
示例一
输入
11001,11101输出
0示例二
输入
11101,10111输出
1解题思路
一共有五种不同的福卡，假设我们按照在长度等于5的字符串中的索引给这些福卡编号，即分别有0 1 2 3 4一共5种福卡。我们直接统计整个团队中，每种福卡的个数，而能够凑齐的福卡的套数，由数目最少的那一种福卡的数目来决定。
为了统计每一种福卡的个数，我们既可以使用哈希表来完成，也可以使用一个长度为5的列表来完成。这两种计数方式没有本质区别。
本题显然也是哈希表在【统计元素频率】类型的题目中的典型应用。
代码
代码一
用哈希表进行统计
Python
# 题目：2023Q1A-集五福
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：哈希表
# 代码看不懂的地方，请直接在群上提问
# 导入collections中的Counter计数器类，使用dict()也可以但是代码就要多一些判断
from collections import Counter
# 团队数组，包含了n个字符串，表示每个人拥有的五福
team = input().split(",")
# 用于统计团队中各种五福个数的长度为的哈希表
cnt = Counter()
# 遍历团队中的每一个人
for person in team:
# 遍历每一个人拥有的五福
for i, num in enumerate(person):
# 如果这个人拥有第i个五福，那么计数+1
if num == "1":
cnt[i] += 1
# 整个团队中最少的那个五福的数目，决定了能凑齐五福的套数
# 要注意：如果哈希表长度小于5，说明有某个福字的数量为0，应该输出0
print(0) if len(cnt) < 5 else print(min(cnt.values()))Java
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] team = scanner.nextLine().split(",");
Map<Integer, Integer> cnt = new HashMap<>();
for (String person : team) {
for (int i = 0; i < person.length(); i++) {
char num = person.charAt(i);
if (num == '1') {
cnt.put(i, cnt.getOrDefault(i, 0) + 1);
}
}
}
if (cnt.size() < 5) {
System.out.println(0);
} else {
int minCnt = Integer.MAX_VALUE;
for (int count : cnt.values()) {
minCnt = Math.min(minCnt, count);
}
System.out.println(minCnt);
}
}
}C++
#include <iostream>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <limits.h>
using namespace std;
int main() {
string line;
getline(cin, line);
istringstream iss(line);
string person;
vector<string> team;
while (getline(iss, person, ',')) {
team.push_back(person);
}
unordered_map<int, int> cnt;
for (const string& person : team) {
for (int i = 0; i < person.length(); i++) {
if (person[i] == '1') {
cnt[i]++;
}
}
}
if (cnt.size() < 5) {
cout << 0 << endl;
} else {
int minCount = INT_MAX;
for (const auto& kv : cnt) {
minCount = min(minCount, kv.second);
}
cout << minCount << endl;
}
return 0;
}代码二
用列表表示哈希表进行统计
Python
# 题目：2023Q1A-集五福
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：用列表表示哈希表
# 代码看不懂的地方，请直接在群上提问
# 团队数组，包含了n个字符串，表示每个人拥有的五福
team = input().split(",")
# 用于统计团队中各种五福个数的长度为5的列表
cnt = [0] * 5
# 遍历团队中的每一个人
for person in team:
# 遍历每一个人拥有的五福
for i, num in enumerate(person):
# 如果这个人拥有第i个五福，那么计数+1
if num == "1":
cnt[i] += 1
# 整个团队中最少的那个五福的数目，决定了能凑齐五福的套数
print(min(cnt))Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String[] team = scanner.nextLine().split(",");
int[] cnt = new int[5];
for (String person : team) {
for (int i = 0; i < person.length(); i++) {
if (person.charAt(i) == '1') {
cnt[i]++;
}
}
}
int minCnt = Integer.MAX_VALUE;
for (int num : cnt) {
minCnt = Math.min(minCnt, num);
}
System.out.println(minCnt);
}
}C++
#include <iostream>
#include <sstream>
#include <vector>
#include <limits.h>
using namespace std;
int main() {
string line;
getline(cin, line);
istringstream iss(line);
string person;
vector<string> team;
while (getline(iss, person, ',')) {
team.push_back(person);
}
vector<int> cnt(5, 0);
for (const string& person : team) {
for (int i = 0; i < person.length(); i++) {
if (person[i] == '1') {
cnt[i]++;
}
}
}
int minCount = INT_MAX;
for (int count : cnt) {
minCount = min(minCount, count);
}
cout << minCount << endl;
return 0;
}时空复杂度
时间复杂度：O(N)。仅需一次遍历字符串数组。
空间复杂度：O(1)。无论是哈希表还是列表，长度最多为5，为常数级别空间。