台州网站建设技术支持,利川市网站建设,项目管理网络图,天元建设集团有限公司第六分公司文章目录 题目来源T1#xff1a;5900: 【DP】小红书2023秋招提前批-连续子数组最大和5801: 【二分查找】小红书2023秋招提前批-精华帖子解法1——排序滑动窗口解法2——前缀和 二分查找 5000: 【模拟】小红书2023秋招提前批-小红的数组构造解法——数学 5300: 【哈希表】小红… 文章目录 题目来源T15900: 【DP】小红书2023秋招提前批-连续子数组最大和5801: 【二分查找】小红书2023秋招提前批-精华帖子解法1——排序滑动窗口解法2——前缀和 二分查找 5000: 【模拟】小红书2023秋招提前批-小红的数组构造解法——数学 5300: 【哈希表】小红书2023秋招-推荐系统 题目来源
红书2023秋招提前批算法真题解析
T15900: 【DP】小红书2023秋招提前批-连续子数组最大和
https://oj.algomooc.com/problem.php?id5900 做这题之前可以先做一下力扣中的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?id5801
这道题目很像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 ∗ k , 3 ∗ k , . . . n ∗ k {k,2*k,3*k,...n*k} k,2∗k,3∗k,...n∗k
使用等差数列求和公式得答案为 k ∗ n ∗ ( n 1 ) / 2 k * n * (n 1) / 2 k∗n∗(n1)/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?id5300#
按照题目要求读取数据存入哈希表做计数统计。 将结果放入列表自定义筛选和排序即可。
import java.util.*;class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);MapString, Integer cnt new HashMap();while (sc.hasNext()) {String word sc.next();cnt.merge(word, 1, Integer::sum);}ListPair ls new ArrayList();for (Map.EntryString, 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;}
}
