💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🎀 01.小红书的话题热度统计

问题描述

小红书是一个很受年轻人欢迎的社区平台。在小红书上，用户可以发布和浏览各种话题的笔记。平台会根据用户对话题的讨论热度，统计出热门话题。

现在给定 个用户发布的话题，每个话题由一个长度不超过 的仅包含大小写字母和数字的字符串表示。当一个话题出现次数大于等于 次时，就称为热门话题。

请你按照话题成为热门话题的时间顺序，输出所有的热门话题。注意，这里以一个话题第 次出现的时间作为该话题成为热门话题的时间。

输入格式

第一行包含一个正整数 ，表示话题的总数。

接下来 行，每行一个字符串，表示一个话题。

输出格式

第一行输出一个正整数 ，表示热门话题的数量。

接下来 行，每行一个字符串，表示一个热门话题。按照话题成为热门话题的时间顺序输出。

样例输入

5
apple
apple
blue
apple
green

样例输出

1
apple

数据范围

题解

我们可以使用哈希表来解决这个问题。具体步骤如下：

1. 使用一个哈希表 统计每个话题出现的次数。
2. 使用另一个哈希表 记录话题是否已经被加入到结果中。
3. 遍历所有话题，对于每个话题：
   • 将其在 中的计数值加 。
   • 如果该话题出现次数大于等于 ，且之前没有被加入过结果，则将其加入结果数组。
4. 遍历结束后，结果数组中按顺序保存了所有的热门话题。

时间复杂度为 ，空间复杂度为 。其中 为话题的总数。

参考代码

• Python

from collections import defaultdict

n = int(input())
cnt = defaultdict(int)
in_res = defaultdict(bool)
res = []

for _ in range(n):
    topic = input()
    cnt[topic] += 1
    if cnt[topic] >= 3 and not in_res[topic]:
        res.append(topic)
        in_res[topic] = True

print(len(res))
for topic in res:
    print(topic)

• 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 sc = new Scanner(System.in);
        int n = sc.nextInt();
        Map<String, Integer> cnt = new HashMap<>();
        Map<String, Boolean> inRes = new HashMap<>();
        List<String> res = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String topic = sc.next();
            cnt.put(topic, cnt.getOrDefault(topic, 0) + 1);
            if (cnt.get(topic) >= 3 && !inRes.getOrDefault(topic, false)) {
                res.add(topic);
                inRes.put(topic, true);
            }
        }

        System.out.println(res.size());
        for (String topic : res) {
            System.out.println(topic);
        }
    }
}

• Cpp

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    unordered_map<string, int> cnt;
    unordered_map<string, bool> in_res;
    vector<string> res;

    while (n--) {
        string topic;
        cin >> topic;
        cnt[topic]++;
        if (cnt[topic] >= 3 && !in_res[topic]) {
            res.push_back(topic);
            in_res[topic] = true;
        }
    }

    cout << res.size() << endl;
    for (const auto& topic : res) {
        cout << topic << endl;
    }
    return 0;
}

🍓 02.LYA 的游戏之旅

问题描述

LYA 是一位热爱游戏的少女。她有 个游戏，每个游戏都有对应的游玩时间 、体力消耗 和快乐值 。

现在 LYA 想要制定一个游戏计划，使得在总游玩时间不超过 且总体力消耗不超过 的前提下，获得尽可能多的快乐值。

请你帮助 LYA 计算，她最多可以获得多少快乐值。

输入格式

第一行输入三个正整数 ，分别代表游戏数量、游玩时间限制和体力限制。

接下来的 行，每行输入三个正整数 ，分别代表第 个游戏的游玩时间、体力消耗和快乐值。

输出格式

输出一个整数，代表 LYA 最多可以获得的快乐值。

样例输入

4 10 15
1 7 5
5 4 6
3 8 1
10 5 7

样例输出

11

数据范围

题解

本题可以使用二维动态规划来解决。定义状态 表示在游玩时间不超过 ，体力消耗不超过 的情况下，可以获得的最大快乐值。

状态转移方程为：

其中 表示当前正在考虑的游戏编号， 分别表示第 个游戏的游玩时间、体力消耗和快乐值。

最终答案即为 。

时间复杂度为 ，空间复杂度为 。

参考代码

• Python

def max_happiness(n, T, H, games):
    f = [[0] * (H + 1) for _ in range(T + 1)]
    for t, h, a in games:
        for i in range(T, t - 1, -1):
            for j in range(H, h - 1, -1):
                f[i][j] = max(f[i][j], f[i - t][j - h] + a)
    return f[T][H]

n, T, H = map(int, input().split())
games = [tuple(map(int, input().split())) for _ in range(n)]
print(max_happiness(n, T, H, games))

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int