解题思路
这是一个集合统计问题。需要统计所有料理所需的不同材料的总数,可以使用集合来去重。
关键点:
- 使用集合存储不同的材料
- 处理多行输入
- 字符串分割处理
- 处理输入结束的情况
算法步骤:
- 创建集合存储材料
- 读取每行输入并分割
- 将材料加入集合
- 返回集合大小
代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<string>& recipes) {
set<string> materials;
for (const string& recipe : recipes) {
istringstream iss(recipe);
string material;
// 分割每行的材料并加入集合
while (iss >> material) {
materials.insert(material);
}
}
return materials.size();
}
};
int main() {
string line;
vector<string> recipes;
// 读取所有行
while (getline(cin, line)) {
if (line.empty()) break;
recipes.push_back(line);
}
Solution solution;
cout << solution.solve(recipes) << endl;
return 0;
}
import java.util.*;
public class Main {
static class Solution {
public int solve(List<String> recipes) {
Set<String> materials = new HashSet<>();
// 处理每个配方
for (String recipe : recipes) {
// 分割每行并添加到集合中
String[] items = recipe.split(" ");
for (String material : items) {
materials.add(material);
}
}
return materials.size();
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
List<String> recipes = new ArrayList<>();
// 读取所有行
while (sc.hasNextLine()) {
String line = sc.nextLine();
if (line.isEmpty()) break;
recipes.add(line);
}
Solution solution = new Solution();
System.out.println(solution.solve(recipes));
sc.close();
}
}
class Solution:
def solve(self, recipes: list) -> int:
# 使用集合存储所有不同的材料
materials = set()
# 处理每个配方
for recipe in recipes:
# 分割每行并添加到集合中
materials.update(recipe.split())
return len(materials)
# 读取输入
recipes = []
while True:
try:
line = input()
if not line:
break
recipes.append(line)
except EOFError:
break
solution = Solution()
print(solution.solve(recipes))
算法及复杂度
- 算法:集合去重
- 时间复杂度:,其中 是配方数量, 是每个配方的平均材料数
- 空间复杂度:,其中 是不同材料的总数