【小红书笔试题汇总】[全网首发]2024-04-07-小红书春招笔试题-三语言题解(CPP/Python/Java)

🍭 大家好这里是KK爱Coding ，一枚热爱算法的程序员

✨ 本系列打算持续跟新小红书近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。

文章目录

• • 01.盛夏送礼物
  • • 题目描述
    • 输入格式
    • 输出格式
    • 样例输入
    • 样例输出
    • 数据范围
    • 题解
    • 参考代码
  • 02.K小姐的旅行笔记
  • • 题目描述
    • 输入格式
    • 输出格式
    • 样例输入
    • 样例输出
    • 数据范围
    • 题解
    • 参考代码
  • 03.K小姐的博客点赞统计
  • • 问题描述
    • 输入格式
    • 输出格式
    • 样例输入
    • 样例输出
    • 数据范围
    • 题解
    • 参考代码
  • 写在最后
  • 📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。

01.盛夏送礼物

题目描述

K小姐是一名知名博主,她在某个盛夏的午后决定给她的粉丝送一些小礼物。她有 名粉丝,编号从 到 ,但她只能选择其中 名送礼物。为了公平起见,她决定选择其中对她支持力度最大的前 名粉丝。如果有两名粉丝的支持力度相同,则优先选择点赞数更多的粉丝;如果点赞数也相同,则优先选择编号更小的粉丝(因为这意味着Ta关注K小姐的时间更早)。

每名粉丝如果给K小姐点一次赞,则对K小姐的支持力度就增加 点;如果收藏K小姐的一篇文章,则对K小姐的支持力度增加 点。

现在K小姐想知道,她应该选择哪 名粉丝送出礼物,你能帮帮她吗?

输入格式

输入包含 行。

第一行包含两个正整数 ,分别表示对K小姐有过支持的粉丝个数,以及K小姐选择送礼的粉丝个数。

接下来 行,每行两个整数 ,表示第 位粉丝给K小姐点过 次赞,收藏过 个K小姐的文章。

输出格式

输出包含一行 个正整数,表示K小姐选择出送礼物的粉丝们的编号。(按照升序输出)

样例输入

4 2
1 2
2 1
3 0
1 3

样例输出

1
4

数据范围

题解

本题可以按照题目描述,直接进行模拟。

1. 将每个粉丝的信息(点赞数、收藏数、编号)存储在一个数组或向量中。

2. 定义一个自定义的排序规则:

   • 首先比较支持力度(点赞数 + 收藏数 * 2)
   • 如果支持力度相同,则比较收藏数
   • 如果收藏数也相同,则比较编号

3. 对存储粉丝信息的数组或向量按照自定义的排序规则进行排序。

4. 取排序后的前 个粉丝的编号,按照升序输出即可。

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

参考代码

• Python

n, k = map(int, input().split())
fans = []
for i in range(n):
    x, y = map(int, input().split())
    fans.append((x, y, i + 1))

fans.sort(key=lambda x: (-x[0] - x[1] * 2, -x[1], x[2]))

res = [fans[i][2] for i in range(k)]
res.sort()
print(*res, sep='\n')

• Java

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[][] fans = new int[n][3];
        for (int i = 0; i < n; i++) {
            fans[i][0] = sc.nextInt();
            fans[i][1] = sc.nextInt();
            fans[i][2] = i + 1;
        }

        Arrays.sort(fans, new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                int wa = a[0] + a[1] * 2;
                int wb = b[0] + b[1] * 2;
                if (wa != wb) {
                    return wb - wa;
                } else if (a[1] != b[1]) {
                    return b[1] - a[1];
                } else {
                    return a[2] - b[2];
                }
            }
        });

        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = fans[i][2];
        }
        Arrays.sort(res);
        for (int i = 0; i < k; i++) {
            System.out.println(res[i]);
        }
    }
}

• Cpp

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> fans(n, vector<int>(3));
    for (int i = 0; i < n; i++) {
        cin >> fans[i][0] >> fans[i][1];
        fans[i][2] = i + 1;
    }

    sort(fans.begin(), fans.end(), [](const vector<int>& a, const vector<int>& b) {
        int wa = a[0] + a[1] * 2;
        int wb = b[0] + b[1] * 2;
        if (wa != wb) {
            return wa > wb;
        } else if (a[1] != b[1]) {
            return a[1] > b[1];
        } else {
            return a[2] < b[2];
        }
    });

    vector<int> res(k);
    for (int i = 0; i < k; i++) {
        res[i] = fans[i][2];
    }
    sort(res.begin(), res.end());
    for (int i = 0; i < k; i++) {
        cout << res[i] << endl;
    }

    return 0;
}

02.K小姐的旅行笔记

题目描述

K小姐是一位旅行博主,她在旅行途中写下了 篇精彩的游记。每篇游记的受欢迎程度可以用点赞数 和评论数 来衡量。K小姐打算选出 篇游记编入一本「K小姐的旅行精选」,这本精选集的质量定义为入选游记点赞数总和乘以评论数最小值。

K小姐希望知道,这本精选集的最佳质量可以达到多少。

输入格式

第一行输入两个正整数 和 ,代表游记的总篇数和精选集的篇数。
第二行输入 个正整数 ,代表每篇游记的点赞数。
第三行输入 个正整数 ,代表每篇游记的评论数。

输出格式

输出一个整数,代表K小姐的旅行精选可以达到的最佳质量。

样例输入

4 2
1 2 3 4
3 4 2 1

样例输出

10

数据范围

题解

本要从所有游记中选出 篇,使得选中游记的点赞数总和最大,同时评论数的最小值也要尽量大。

具体步骤如下:

1. 将所有游记按照评论数从大到小排序。

2. 从前 篇游记中,计算点赞数总和乘以第 小的评论数,作为一个可能的最大质量。

3. 从第 篇游记开始,每次固定一篇作为评论数最小值,再从剩余游记中选择点赞数最大的 篇,计算精选集质量并更新答案。

4. 输出得到的最佳质量即可。

时间复杂度 ,空间复杂度 。

参考代码

• Python

import heapq

n, k = map(int, input().split())
likes = list(map(int, input().split())) 
comments = list(map(int, input().split()))

articles = sorted(zip(likes, comments), key=lambda x: -x[1])

hp = []
total = 0
best = 0
for like, comment in articles:
    if len(hp) < k:
        heapq.heappush(hp, like)
        total += like
    elif hp[0] < like:
        total += like - heapq.heappop(hp)
        heapq.heappush(hp, like)
    
    best = max(best, total * comment)

print(best)

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        int[] likes = new int[n];
        int[] comments = new int[n];
        for (int i = 0; i < n; i++) {
            likes[i] = sc.nextInt();
        }
        for (int i = 0; i < n; i++) {
            comments[i] = sc.nextInt();
        }
        
        int[][] articles = new int[n][2];
        for (int i = 0; i < n; i++) {
            articles[i] = new int[]{likes[i], comments[i]};
        }
        Arrays.sort(articles, (a, b) -> b[1] - a[1]);
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(k);
        long total = 0, best = 0;
        for (int[] a : articles) {
            int like = a[0], comment = a[1];
            if (pq.size() < k) {
                pq.offer(like);
                total += like;
            } else if (pq.peek() < like) {
                total += like - pq.poll();
                pq.offer(like);
            }
            best = Math.max(best, total * comment);
        }
        System.out.println(best);
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> likes(n), comments(n);
    for (int i = 0; i < n; i++) {
        cin >> likes[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> comments[i];
    }
    
    vector<pii> articles;
    for (int i = 0; i < n; i++) {
        articles.push_back({likes[i], comments[i]});
    }
    sort(articles.begin(), articles.end(), [](pii a, pii b) {
        return a.second > b.second;
    });
    
    priority_queue<int, vector<int>, greater<int>> pq;
    ll total = 0, best = 0;
    for (auto [like, comment] : articles) {
        if (pq.size() < k) {
            pq.push(like);
            total += like;
        } else if (pq.top() < like) {
            total += like - pq.top();
            pq.pop();
            pq.push(like);
        }
        best = max(best, total * comment);
    }
    cout << best << endl;
    return 0;
}

03.K小姐的博客点赞统计

问题描述

K小姐是一位博客作者,她在自己的博客上发表了 篇文章。有一天,她想统计每篇文章的点赞数,但是她只记得以下两个信息:

1. 每篇文章的点赞数都是正整数,且不超过 。
2. 第 篇文章的点赞数和第 篇文章的点赞数之间的大小关系。

现在,K小姐想知道,在已知这些信息的情况下,所有文章的点赞数一共有多少种可能的情况。由于答案可能很大,请输出答案对 取模的结果。

输入格式

第一行包含两个正整数 和 ,分别表示文章的总数和每篇文章点赞数的上限。

第二行包含一个长度为 的字符串 ,其中只包含字符 >、< 和 =。如果 为 >,则表示第 篇文章的点赞数严格大于第 篇文章的点赞数;如果 为 <,则表示第 篇文章的点赞数严格小于第 篇文章的点赞数;如果 为 =,则表示第 篇文章的点赞数等于第 篇文章的点赞数。

输出格式

输出一个整数,表示所有可能的点赞数情况数对 取模的结果。

样例输入

4 3
<=>

样例输出

5

数据范围

题解

本题可以使用动态规划求解。定义 表示考虑前 篇文章,且第 篇文章的点赞数为 时的方案数。

对于第 篇文章,根据第 篇文章与第 篇文章的大小关系,可以分为三种情况进行状态转移:

1. 为 >:此时第 篇文章的点赞数必须大于第 篇文章的点赞数,因此可以将 的值累加到 中。
2. 为 <:此时第 篇文章的点赞数必须小于第 篇文章的点赞数,因此可以将 的值累加到 中。
3. 为 =:此时第 篇文章的点赞数必须等于第 篇文章的点赞数,因此 。

最终的答案为 。

时间复杂度 ,空间复杂度 。

参考代码

• Python

MOD = 1000000007

def compute_prefix_sum(v):
    prefix = [0] * len(v)
    prefix[0] = v[0]
    for i in range(1, len(v)):
        prefix[i] = (prefix[i - 1] + v[i]) % MOD
    return prefix

def main():
    n, m = map(int, input().split())
    relations = input().strip()

    dp = [[0] * (m + 1) for _ in range(n)]

    for j in range(1, m + 1):
        dp[0][j] = 1

    for i in range(1, n):
        prefix = compute_prefix_sum(dp[i - 1])
        for j in range(1, m + 1):
            if relations[i - 1] == '>':
                dp[i][j] = (prefix[m] - prefix[j] + MOD) % MOD
            elif relations[i - 1] == '<':
                dp[i][j] = prefix[j - 1]
            elif relations[i - 1] == '=':
                dp[i][j] = dp[i - 1][j]

    result = 0
    for j in range(1, m + 1):
        result = (result + dp[n - 1][j]) % MOD

    print(result)

if __name__ == "__main__":
    main()

• Java

import java.util.Scanner;

public class Main {
    static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        String relations = scanner.next();

        int[][] dp = new int[n][m + 1];

        for (int j = 1; j <= m; ++j) {
            dp[0][j] = 1;
        }

        for (int i = 1; i < n; ++i) {
            int[] prefix = computePrefixSum(dp[i - 1]);
            for (int j = 1; j <= m; ++j) {
                if (relations.charAt(i - 1) == '>') {
                    dp[i][j] = (prefix[m] - prefix[j] + MOD) % MOD;
                } else if (relations.charAt(i - 1) == '<') {
                    dp[i][j] = prefix[j - 1];
                } else if (relations.charAt(i - 1) == '=') {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        int result = 0;
        for (int j = 1; j <= m; ++j) {
            result = (result + dp[n - 1][j]) % MOD;
        }

        System.out.println(result);
    }

    static int[] computePrefixSum(int[] v) {
        int[] prefix = new int[v.length];
        prefix[0] = v[0];
        for (int i = 1; i < v.length; ++i) {
            prefix[i] = (prefix[i - 1] + v[i]) % MOD;
        }
        return prefix;
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int MOD = 1000000007;

vector<int> computePrefixSum(const vector<int>& v) {
    vector<int> prefix(v.size());
    prefix[0] = v[0];
    for (size_t i = 1; i < v.size(); ++i) {
        prefix[i] = (prefix[i - 1] + v[i]) % MOD;
    }
    return prefix;
}

int main() {
    int n, m;
    cin >> n >> m;
    string relations;
    cin >> relations;

    vector<vector<int>> dp(n, vector<int>(m + 1));

    for (int j = 1; j <= m; ++j) {
        dp[0][j] = 1;
    }

    for (int i = 1; i < n; ++i) {
        vector<int> prefix = computePrefixSum(dp[i - 1]);
        for (int j = 1; j <= m; ++j) {
            if (relations[i - 1] == '>') {
                dp[i][j] = (prefix[m] - prefix[j] + MOD) % MOD;
            } else if (relations[i - 1] == '<') {
                dp[i][j] = prefix[j - 1];
            } else if (relations[i - 1] == '=') {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    int result = 0;
    for (int j = 1; j <= m; ++j) {
        result = (result + dp[n - 1][j]) % MOD;
    }

    cout << result << endl;

    return 0;
}

写在最后

📧 KK这边最近正在收集近一年互联网各厂的笔试题汇总，如果有需要的小伙伴可以关注后私信一下 KK领取，会在飞书进行同步的跟新。