大厂秋招真题【二分查找】小红书20230726秋招提前批T2-精华帖子

本文主要是介绍大厂秋招真题【二分查找】小红书20230726秋招提前批T2-精华帖子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述与示例

题目描述

小红书的推荐帖子列表为[0,n)，其中所有的帖子初始状态为“普通”，现在运营同学把其中的一些帖子区间标记为了“精华”。

运营同学选择了固定长度k，对整个帖子列表截取，要求计算在固定的截取长度k下，能够截取获得的最多精华帖子数量。

输入描述

第一行输入三个正整数n，m，k，分别代表初始帖子列表长度，精华区间的数量，以及运营同学准备截取的长度。

接下来的m行，每行输入两个正整数li，ri，代表第i个左闭右开区间。

1 ≤ k ≤ n ≤ 1000000000
1 ≤ m ≤ 100000
0 ≤ li < ri ≤ n

保证任意两个区间是不重叠的。

输出描述

一个正整数，代表截取获得的最多的精华帖子数量。

示例

输入

5 2 3
1 2
3 5

输出

2

说明

这是一个长度为5的帖子列表，如果用0表示普通帖子，1表示精华帖子，则该列表为[0, 1, 0, 1, 1]。用长度k = 3的区间截取列表，最多能够包含2个精华帖子。

时空限制

时间限制：3s

内存****限制：512MB

解题思路

最多的精华帖子数量的区间，一定从某个特定区间i的左端点li开始，到li+k结束。故我们枚举所有的左端点li，利用二分查找找到第一个大于等于li+k的右端点rj。二分过程的代码如下

li, ri = intervals[i]
left, right = i, m
while left < right:mid = left + (right-left) // 2if intervals[mid][1] >= li + k:right = midelse:left = mid + 1

对于特定的rj，有可能有以下两种情况

• li+k位于区间[lj, rj)之间，即lj < li+k < rj

暂时无法在飞书文档外展示此内容

• li+k位于区间[lj, rj)之外，即li+k <= lj

暂时无法在飞书文档外展示此内容

我们可以先统计每一个精华区间的前缀和，再根据求得的j和i计算第i个区间到第j个区间之间的精华帖子数量，注意上述两种区别，需要分类讨论。

lj, rj = intervals[j]
if li + k < lj:ans = max(ans, pre_sum_list[j]-pre_sum_list[i])
elif lj <= li + k < rj:ans = max(ans, pre_sum_list[j] - pre_sum_list[i] + (li+k-lj))

代码

python

# 题目：【二分查找】小红书2023秋招提前批-精华帖子
# 作者：闭着眼睛学数理化
# 算法：二分查找/前缀和
# 代码有看不懂的地方请直接在群上提问# 输入帖子数量n，精华区间个数m，截取长度k
n, m, k = map(int, input().split())pre_sum_list = [0]
intervals = list()# 输入m个精华区间，注意这里是左闭右开区间
for _ in range(m):l, r = map(int, input().split())# 储存精华区间intervals.append([l, r])# 该区间的精华帖子数目为r-lpre_sum_list.append(pre_sum_list[-1] + r-l)# 初始化答案为0
ans = 0
# 遍历每一个区间
for i in range(m):# 第i个区间的左端点为lili, ri = intervals[i]# 初始化二分查找的左闭右开区间# left为下标i，right为区间个数mleft, right = i, m# 进行二分查找# 搜索目标为第一个大于等于li+k的右端点rj的下标jwhile left < right:mid = left + (right-left) // 2if intervals[mid][1] >= li + k:right = midelse:left = mid + 1# 退出循环后，left = right即为第一个大于等于li+k的右端点rj的下标jj = left# 若此时j为m，说明最有的精华帖子的区间也小于li+k，此时选择li作为左端点时# 精华帖子的数量为pre_sum_list[-1]-pre_sum_list[i]if j >= m:ans = max(ans, pre_sum_list[-1] - pre_sum_list[i])# 同时，由于在考虑更后的区间下标i，结果一定小于当前结果，故可以直接退出break# 获取该区间所对应的左端点和右端点lj和rjlj, rj = intervals[j]# 如果 li+k 小于左端点 lj，说明当选择li作为左端点时# 精华帖子的数量为pre_sum_list[j]-pre_sum_list[i]if li + k < lj:ans = max(ans, pre_sum_list[j]-pre_sum_list[i])# 如果 li+k 位于区间 [lj,rj)中，说明当选择li作为左端点时# 精华帖子的数量为pre_sum_list[j]-pre_sum_list[i]+(li+k-lj)elif lj <= li + k < rj:ans = max(ans, pre_sum_list[j] - pre_sum_list[i] + (li+k-lj))print(ans)

Java

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int k = scanner.nextInt();int[] preSumList = new int[m + 1];int[][] intervals = new int[m][2];for (int i = 0; i < m; i++) {int l = scanner.nextInt();int r = scanner.nextInt();intervals[i][0] = l;intervals[i][1] = r;preSumList[i + 1] = preSumList[i] + (r - l);}int ans = 0;for (int i = 0; i < m; i++) {int li = intervals[i][0];int ri = intervals[i][1];int left = i;int right = m;while (left < right) {int mid = left + (right - left) / 2;if (intervals[mid][1] >= li + k) {right = mid;} else {left = mid + 1;}}int j = left;if (j >= m) {ans = Math.max(ans, preSumList[m] - preSumList[i]);break;}int lj = intervals[j][0];int rj = intervals[j][1];if (li + k < lj) {ans = Math.max(ans, preSumList[j] - preSumList[i]);} else if (lj <= li + k && li + k < rj) {ans = Math.max(ans, preSumList[j] - preSumList[i] + (li + k - lj));}}System.out.println(ans);}
}

C++

#include <iostream>
#include <vector>using namespace std;int main() {int n, m, k;cin >> n >> m >> k;vector<int> preSumList(m + 1);vector<vector<int>> intervals(m, vector<int>(2));for (int i = 0; i < m; i++) {int l, r;cin >> l >> r;intervals[i][0] = l;intervals[i][1] = r;preSumList[i + 1] = preSumList[i] + (r - l);}int ans = 0;for (int i = 0; i < m; i++) {int li = intervals[i][0];int ri = intervals[i][1];int left = i;int right = m;while (left < right) {int mid = left + (right - left) / 2;if (intervals[mid][1] >= li + k) {right = mid;} else {left = mid + 1;}}int j = left;if (j >= m) {ans = max(ans, preSumList[m] - preSumList[i]);break;}int lj = intervals[j][0];int rj = intervals[j][1];if (li + k < lj) {ans = max(ans, preSumList[j] - preSumList[i]);} else if (lj <= li + k && li + k < rj) {ans = max(ans, preSumList[j] - preSumList[i] + (li + k - lj));}}cout << ans << endl;return 0;
}

时空复杂度

时间复杂度：O(mlogm)。m为标记为精华的区间数量，对于每一个区间都去进行二分查找，一共有m个区间，单词二分查找的时间复杂度是O(logm)。

空间复杂度：O(m)。前缀和哈希表所占空间。

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 OD算法冲刺训练课程表 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多

这篇关于大厂秋招真题【二分查找】小红书20230726秋招提前批T2-精华帖子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---