【算法题】小红书2023秋招提前批算法真题解析

题目来源

红书2023秋招提前批算法真题解析

T1：5900: 【DP】小红书2023秋招提前批-连续子数组最大和

https://oj.algomooc.com/problem.php?id=5900

做这题之前可以先做一下力扣中的：53. 最大子数组和 作为前置知识。

每次询问就是一批输入数据。
定义 dp 数组 [n][2] 表示 以 a[i] 为结尾且选 a[i] 的子数组的最大和是多少，第二维的 0 和 1 分别表示当前有没有将元素换成 x 的操作。

import java.util.*;class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int t = sc.nextInt();while (t-- != 0) {int n = sc.nextInt(), x = sc.nextInt();int[] a = new int[n];int[][] dp = new int[n][2];     // 没变和变了for (int i = 0; i < n; ++i) a[i] = sc.nextInt();dp[0][0] = a[0];dp[0][1] = x;int ans = Math.max(dp[0][0], dp[0][1]);for (int i = 1; i < n; ++i) {dp[i][0] = Math.max(dp[i - 1][0] + a[i], a[i]);dp[i][1] = Math.max(dp[i - 1][1] + a[i], dp[i - 1][0] + x);ans = Math.max(ans, Math.max(dp[i][0], dp[i][1]));}System.out.println(ans);}}
}

5801: 【二分查找】小红书2023秋招提前批-精华帖子

https://oj.algomooc.com/problem.php?id=5801

这道题目很像：2271. 毯子覆盖的最多白色砖块数

解法1——排序+滑动窗口

该解法的解析见：【LeetCode周赛】2022上半年题目精选集——双指针

import java.util.*;class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();int[][] e = new int[m][2];for (int i = 0; i < m; ++i) {e[i][0] = sc.nextInt();e[i][1] = sc.nextInt();}// 排序Arrays.sort(e, (x, y) -> x[0] - y[0]);int ans = 0, sum = 0;// 开滑(枚举右端点，尝试移动左端点)for (int l = 0, r = 0; r < m; ++r) {sum += e[r][1] - e[r][0];// 把超过的移出去while (e[r][1] - e[l][1] > k) {sum -= e[l][1] - e[l][0];l++;}// 检查第一个区间是否占完了if (e[r][1] - k > e[l][0]) {ans = Math.max(ans, sum - (e[r][1] - k - e[l][0]));} else ans = Math.max(ans, sum);}System.out.println(ans);}
}

解法2——前缀和 + 二分查找

前缀和是为了快速求出一个区间中的精华区一共有多少个精华帖子。
二分查找是为了快速找出以某一个精华区为起点时，最后一个被覆盖到的精华区的索引。

import java.util.*;class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();int[][] e = new int[m][2];int[] s = new int[m + 1];for (int i = 0; i < m; ++i) {e[i][0] = sc.nextInt();e[i][1] = sc.nextInt();s[i + 1] = s[i] + e[i][1] - e[i][0];}int ans = 0;for (int i = 0; i < m; ++i) {   // 枚举每个瓷砖作为起始瓷砖// 使用二分查找最后一个被覆盖到的瓷砖int l = i, r = m - 1;while (l < r) {int mid = l + r + 1 >> 1;if (e[i][0] + k < e[mid][0]) r = mid - 1;else l = mid;}ans = Math.max(ans, s[l] - s[i] + Math.min(e[i][0] + k, e[l][1]) - e[l][0]);}System.out.println(ans);}
}

5000: 【模拟】小红书2023秋招提前批-小红的数组构造

解法——数学

冷静思考！—— 最后的数组是这样的 $k,2\ast k,3\ast k,...n\ast k$

使用等差数列求和公式得答案为 $k\ast n\ast (n+1)/2$

import java.util.*;class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(), k = sc.nextInt();System.out.println((long)k * n * (n + 1) / 2);}
}

记得要转 long 否则答案会溢出 int。

5300: 【哈希表】小红书2023秋招-推荐系统

https://oj.algomooc.com/problem.php?id=5300#

按照题目要求读取数据，存入哈希表做计数统计。
将结果放入列表，自定义筛选和排序即可。

import java.util.*;class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);Map<String, Integer> cnt = new HashMap<>();while (sc.hasNext()) {String word = sc.next();cnt.merge(word, 1, Integer::sum);}List<Pair> ls = new ArrayList<>();for (Map.Entry<String, Integer> entry: cnt.entrySet()) {if (entry.getValue() >= 3) {ls.add(new Pair(entry.getKey(), entry.getValue()));}}Collections.sort(ls, (x, y) -> {int c1 = x.value, c2 = y.value;return c1 != c2? c2 - c1: x.key.compareTo(y.key);});for (Pair p: ls) {System.out.println(p.key);}}
}class Pair {String key;Integer value;Pair(String key, Integer value) {this.key = key;this.value = value;}
}