题解 | #小红背单词#

题目链接

小红背单词

题目描述

小红按顺序背 $n$ 个单词。她记住一个新单词的规则如下：如果她已经记住了 $k$ 个单词，那么她需要背一个没有记住的新单词 $k+1$ 次，才能记住这个新单词。

请根据小红背单词的顺序，计算她最终记住了多少个单词。

解题思路

这是一个模拟题，我们需要精确地追踪小红的记忆状态。具体来说，需要记录两类信息：

已经记住的单词集合：哪些单词已经被小红完全掌握。
正在背的单词的次数：对于那些尚未记住的单词，它们各自被背了多少次。

算法步骤如下：

初始化数据结构：
- 使用一个哈希集合（set）来存储已经记住的单词，我们称之为 known_words。这可以让我们快速判断一个单词是否已被记住。
- 使用一个哈希表（map）来记录每个尚未记住的单词被背的次数，我们称之为 encounter_counts。
遍历单词列表：按顺序处理输入的每一个单词。
处理每个单词：对于当前遇到的单词 word：
- 首先，检查 word 是否已经在 known_words 集合中。
  - 如果是，说明这个单词已经记住了，我们不需要做任何事，直接跳到下一个单词。
- 如果 word 不在 known_words 中，说明这是一个尚未掌握的单词。
  - 在 encounter_counts 中将 word 的计数值加1。
  - 获取当前已经记住的单词数量 $k = \text{known\_words.size()}$ 。
  - 检查 word 的当前背诵次数是否达到了记忆阈值，即 encounter_counts[word] \ge k + 1。
  - 如果达到了，说明小红刚刚记住了这个新单词。我们将 word 添加到 known_words 集合中，表示她已经掌握了这个单词。
得出结果：遍历完所有单词后，known_words 集合的大小就是小红最终记住的单词总数。

代码

c++
java
python

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    set<string> known_words;
    map<string, int> encounter_counts;
    
    for (int i = 0; i < n; ++i) {
        string word;
        cin >> word;
        
        // 如果单词已经记住，则跳过
        if (known_words.count(word)) {
            continue;
        }
        
        // 否则，增加该单词的背诵次数
        encounter_counts[word]++;
        
        // 检查是否达到了记忆条件
        int k = known_words.size();
        if (encounter_counts[word] >= k + 1) {
            known_words.insert(word);
        }
    }
    
    cout << known_words.size() << '\n';
    
    return 0;
}

import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;
import java.util.Map;
import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        Set<String> knownWords = new HashSet<>();
        Map<String, Integer> encounterCounts = new HashMap<>();
        
        for (int i = 0; i < n; i++) {
            String word = sc.next();
            
            // 如果单词已经记住，则跳过
            if (knownWords.contains(word)) {
                continue;
            }
            
            // 否则，增加该单词的背诵次数
            encounterCounts.put(word, encounterCounts.getOrDefault(word, 0) + 1);
            
            // 检查是否达到了记忆条件
            int k = knownWords.size();
            if (encounterCounts.get(word) >= k + 1) {
                knownWords.add(word);
            }
        }
        
        System.out.println(knownWords.size());
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    words = [sys.stdin.readline().strip() for _ in range(n)]
    
    known_words = set()
    encounter_counts = {}
    
    for word in words:
        # 如果单词已经记住，则跳过
        if word in known_words:
            continue
            
        # 否则，增加该单词的背诵次数
        encounter_counts[word] = encounter_counts.get(word, 0) + 1
        
        # 检查是否达到了记忆条件
        k = len(known_words)
        if encounter_counts[word] >= k + 1:
            known_words.add(word)
            
    print(len(known_words))

solve()

算法及复杂度

算法：模拟 + 哈希表
时间复杂度：我们需要遍历全部 $n$ 个单词。对于每个单词，我们在哈希集合和哈希表中的操作（查找、插入、更新）的平均时间复杂度都与单词的长度 $L$ 相关。因此，总的时间复杂度为 $\mathcal{O}(n \cdot L_{avg})$ ，其中 $L_{avg}$ 是单词的平均长度。
空间复杂度：在最坏的情况下，我们需要存储所有不重复的单词。设不重复单词的数量为 $U$ ，则空间复杂度为 $\mathcal{O}(U \cdot L_{avg})$ 。