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

文章【小红书笔试题汇总】[全网首发]2024-04-07-小红书春招笔试题-三语言题解(CPP/Python/Java)分享给大家，欢迎收藏Python资料网，专注分享技术知识

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

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

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

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

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

01.盛夏送礼物

题目描述

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

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

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

输入格式

输入包含 $n+1$ 行。

第一行包含两个正整数 n , k   ( 1 ≤ k ≤ n ≤ 1 0 5 ) n,k\ (1 \leq k \leq n \leq 10^5) n,k (1≤k≤n≤105),分别表示对K小姐有过支持的粉丝个数,以及K小姐选择送礼的粉丝个数。

接下来 $n$ 行,每行两个整数 x , y   ( 0 ≤ x , y ≤ 1 0 5 ) x,y\ (0 \leq x,y \leq 10^5) x,y (0≤x,y≤105),表示第 $i$ 位粉丝给K小姐点过 $x$ 次赞,收藏过 $y$ 个K小姐的文章。

输出格式

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

样例输入

4 2
1 2
2 1
3 0
1 3

样例输出

1
4

数据范围

• 1 ≤ k ≤ n ≤ 1 0 5 1 \leq k \leq n \leq 10^5 1≤k≤n≤105
• 0 ≤ x , y ≤ 1 0 5 0 \leq x,y \leq 10^5 0≤x,y≤105

题解

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

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

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

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

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

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

时间复杂度为 $O(n\log n)$,空间复杂度为 $O(n)$。

参考代码

• 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小姐是一位旅行博主,她在旅行途中写下了 $n$ 篇精彩的游记。每篇游记的受欢迎程度可以用点赞数 a i a_i ai​ 和评论数 b i b_i bi​ 来衡量。K小姐打算选出 $k$ 篇游记编入一本「K小姐的旅行精选」,这本精选集的质量定义为入选游记点赞数总和乘以评论数最小值。

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

输入格式

第一行输入两个正整数 $n$ 和 $k$,代表游记的总篇数和精选集的篇数。
第二行输入 $n$ 个正整数 a 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1​,a2​,…,an​,代表每篇游记的点赞数。
第三行输入 $n$ 个正整数 b 1 , b 2 , … , b n b_1, b_2, \dots, b_n b1​,b2​,…,bn​,代表每篇游记的评论数。

输出格式

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

样例输入

4 2
1 2 3 4
3 4 2 1

样例输出

10

数据范围

• 1 ≤ n , a i , b i ≤ 1 0 5 1 \leq n,a_i,b_i \leq 10^5 1≤n,ai​,bi​≤105
• $1\le k\le n$

题解

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

具体步骤如下:

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

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

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

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

时间复杂度 $O(n\log n)$,空间复杂度 $O(n)$。

参考代码

• 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小姐是一位博客作者,她在自己的博客上发表了 $n$ 篇文章。有一天,她想统计每篇文章的点赞数,但是她只记得以下两个信息:

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

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

输入格式

第一行包含两个正整数 $n$ 和 $m$ $(1\le n,m\le 2000)$,分别表示文章的总数和每篇文章点赞数的上限。

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

输出格式

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

样例输入

4 3
<=>

样例输出

5

数据范围

$1\le n,m\le 2000$

题解

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

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

1. s i − 1 s_{i-1} si−1​ 为 >:此时第 $i$ 篇文章的点赞数必须大于第 $i-1$ 篇文章的点赞数,因此可以将 $dp[i-1][1\dots j-1]$ 的值累加到 $dp[i][j]$ 中。
2. s i − 1 s_{i-1} si−1​ 为 <:此时第 $i$ 篇文章的点赞数必须小于第 $i-1$ 篇文章的点赞数,因此可以将 $dp[i-1][j+1\dots m]$ 的值累加到 $dp[i][j]$ 中。
3. s i − 1 s_{i-1} si−1​ 为 =:此时第 $i$ 篇文章的点赞数必须等于第 $i-1$ 篇文章的点赞数,因此 $dp[i][j]=dp[i-1][j]$。

最终的答案为 ∑ j = 1 m d p [ n ] [ j ] \sum_{j=1}^m dp[n][j] ∑j=1m​dp[n][j]。

时间复杂度 $O(nm)$,空间复杂度 $O(nm)$。

参考代码

• 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领取，会在飞书进行同步的跟新。

版权声明：本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！