小红书Java后端2023-8-6笔试

小红书推荐系统

时间限制：3000MS；内存限制：589824KB

题目描述

小红书有一个推荐系统，可以根据用户搜索的关键词推荐用户希望获取的内容。现在给定小孩的搜索记录（记录是分词后的结果），我们认为当一个单词出现的次数不少于3次时。该单词为“用户期望搜索的单词“，即为关键词。请你根据小红的记录，输出小红的用户画像对应得所有关键词。

输入描述

一行字符串。仅由小写字母和空格组成。代表小红的搜索记录。

字符串长度不超过100000.

输出描述

小红所有的关键词。每行输出一个。你需要按照搜索频次从高到低输出。频次相同的，你需要按字典序升序输出。

样例输入

kou red game red ok who game red karaoke yukari kou red red nani kou can koukou ongakugame game

样例输出

red
game
kou

思路 

先使用哈希表记录每个元素出现的次序，再筛选出出现次数大于等于3的单词，然后对字典进行排序，先对出现次序进行升序排序，再根据字典序对出现次数相同的单词进行降序排序，最后添加

”reverse = True“ 属性，就可以实现对出现次数降序排序，字典序升序排序了

map = {}
s = input().split(" ")ans = {}
for i in range(len(s)):if s[i] not in map:map[s[i]] = 1else:map[s[i]] +=1for key,value in map.items():if value>=3:ans[key] = valueans = sorted(ans.items(),key=lambda x:(-x[1],x[0]),reverse=True )x = []
for i in range(len(ans)-1,-1,-1):print(ans[i][0] )

小红的分享日常

时间限制：3000MS 内存限制：589824KB

题目描述

小红书很喜欢前往小红书分享她的日常生活。已知她生活中有n个事件，分享第i个事件需要她花费ti的时间和hi的精力来编辑文章，并能获得ai的快乐值。

小红想知道，在总花费时间不超过T且总花费精力不超过H的前提下，小红最多可以获得多少快乐值？

输入描述

第一行输入一个正整数n，代表事件的数量。

第二行输入两个正整数T和H，代表时间限制和精力限制。

接下来的n行，每行输入三个正整数ti,hi，ai，代表分享第i个事件需要花费ti的时间、hi的精力，收获ai的快乐值。

1<=n<=50
1<=T,H<=500
1<=ti,hi<=30
1<=ai<=10^9

输出描述

一个整数，代表小红最多的快乐值

样例

输入

2
2 2
1 3 3
3 1 4

输出

0

说明

显然，小红无法分享任何事件

思路

背包问题，只是多了一个限制条件，定义状态dp为面对这件事的时候快乐值最大的结果。

代码

    public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int T = sc.nextInt();int H = sc.nextInt();int[] t = new int[n];int[] h = new int[n];int[] a = new int[n];for(int i=0;i<n;i++){t[i] = sc.nextInt();h[i] = sc.nextInt();a[i] = sc.nextInt();}int [][] dp = new int[T+1][H+1];for(int i=0;i<n;i++){for(int j=T;j>=t[i];j--){for(int k=H;k>=h[i];k--){dp[j][k] = Math.max(dp[j][k],dp[j-t[i]][k-h[i]] +a[i]);}}}System.out.println(dp[T][H]);}

小红的小红树

时间限制：3000MS 内存限制：589824KB

小红在刷小红书的时候看到了一颗挂着小红薯的小红树，所以小红也想种一颗小红树挂一些小红薯发小红书。

小红有一颗树，每个结点有一个权值，初始时每个节点都是白色。小红每次操作可以选择两个相邻的结点，如果它们都是白色且权值的和是质数，小红就可以选择其中一个节点染红。

小红想知道最多可以染红多少个节点?

输入描述

第一行输入一个正整数n，代表节点的数量。
第二行输入n个正整数ai，代表每个节点的权值。
接下来的n-1行，每行输入两个正整数u,v，代表节点u和节点v有一条边连接。
1<=n<=10^5
1<=ai<=10^5
1<=u,v<=n

输出描述

输出一个整数表示答案。

样例输入

3
1 2 3
1 2
1 3

样例输出

1

提示

节点1和节点2权值和为3，是质数，所以小红可以染红节点1或节点2，此时无法再染红其他节点。

思路

针对这道题，我们可以计算两个端点为素数的边的个数，这样可以通过全部测试用例，但在某些情况下会出现错误

我们在代码中通过埃拉托斯特尼筛法得到两万以内的全部素数，然后在主函数中进行筛选

代码

 public static void main(String[] args) {new algorithm().solution();}Set<Integer> primes = new HashSet<>();boolean[] st;void get_primes(){int n = 200000;for(int i=2;i<=n;i++){if(!st[i]){primes.add(i);for(int j=i+i;j<=n;j+=i) st[j]=true;}}}int[] V;void solution(){st = new boolean[200001];get_primes();Scanner sc = new Scanner(System.in);int n = sc.nextInt();V = new int[n+1];for(int i=0;i<n;i++)V[i] = sc.nextInt();int res = 0;for(int i=0;i<n-1;i++){int a = sc.nextInt();int b = sc.nextInt();if(primes.contains(a+b)) res++;}System.out.println(res);}