解题思路

这是一个集合统计问题。需要统计所有料理所需的不同材料的总数,可以使用集合来去重。

关键点:

  1. 使用集合存储不同的材料
  2. 处理多行输入
  3. 字符串分割处理
  4. 处理输入结束的情况

算法步骤:

  1. 创建集合存储材料
  2. 读取每行输入并分割
  3. 将材料加入集合
  4. 返回集合大小

代码

#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))

算法及复杂度

  • 算法:集合去重
  • 时间复杂度:,其中 是配方数量, 是每个配方的平均材料数
  • 空间复杂度:,其中 是不同材料的总数