红书2023秋招提前批算法真题解析
大家好，我是吴师兄，关注我，每天更新大厂最新笔试题解析。
今天更新的是小红书2023秋招提前批算法面试题。
题目一：连续子数组最大和
题目描述
小红拿到了一个数组，她希望进行最多一次操作：将一个元素修改为x。小红想知道，最终的连续子数组最大和最大是多少？
输入描述
第一行输入一个正整数t，代表询问次数。
对于每次询问，输入两行：
第一行输入两个整数n和x。代表数组的大小，以及小红可以修改成的元素。
第二行输入n个正整数a_i，代表小红每次询问拿到的数组。
1 ≤ t ≤ 100000
1 ≤ n ≤ 200000
-10^9 ≤ x, a_i ≤ 10^9
每组所有询问的n的和不超过200000。
输出描述
输出t行，每行输出一个整数，代表每次询问能够得到的连续子数组的最大和。
示例
输入
3
5 10
5 -1 -5 -3 2
2 -3
-5 -2
6 10
4 -2 -11 -1 4 -1
输出
15
-2
15
说明
第一组询问，修改第二个数。
第二组询问，不进行任何修改。
第三组询问，修改第三个数。
时空限制
时间限制：3s
内存限制：512MB
解题思路
注意，本题的部分逻辑和LeetCode53. 最大子数组和 完全一致，属于本题的一道延申题。而修改的操作，可以类比股票问题的做法。
代码
# 题目：【DP】小红书2023秋招提前批-连续子数组最大和
# 作者：闭着眼睛学数理化
# 算法：DP/前缀和
# 相关题目：LC53. 最大子数组和
# 代码有看不懂的地方请直接在群上提问
# 想要参加高阶算法训练营添加微信 278166530
# 用dp解决问题的函数
def sol(nums, n, x):
# dp[i]表示以nums[i]为结尾的子数组，能够取得的最大连续子数组和的情况
# dp[i][0]表示尚未进行修改，能取得的最大子数组和
# dp[i][1]表示已经进行修改，能取得的最大子数组和
dp = [[0, 0] for _ in range(n)]
# 初始化dp数组
dp[0] = [nums[0], x]
# 初始化答案
ans = max(dp[0])
for i in range(1, n):
# 考虑尚未进行过修改的情况，即考虑dp[i][0]的动态转移方程
# 注意此处和 LC53. 最大子数组和 的逻辑是完全一致的
# 如果dp[i-1][0]是负数，那么dp[i][0]则不再考虑dp[i-1][0]，仅包含nums[i]即可
# 如果dp[i-1][0]是正数，那么dp[i][0]则需要考虑dp[i-1][0]，要同时包含nums[i]和dp[i-1][0]
if dp[i-1][0] < 0:
dp[i][0] = nums[i]
else:
dp[i][0] = nums[i] + dp[i-1][0]
# 考虑已经进行过修改的情况，即考虑dp[i][1]的动态转移方程
# 有两种修改情况：
# 在i位置进行修改，得到的最大连续子数组和是 dp[i-1][0] + x
# 在i之前的某个位置进行修改，得到的最大连续子数组和是 dp[i-1][1] + nums[i]
dp[i][1] = max(dp[i-1][0]+x, dp[i-1][1]+nums[i])
# 更新答案
ans = max(ans, max(dp[i]))
return ans
t = int(input())
# 遍历t次，表示t次询问
for _ in range(t):
# 获得本次询问的数组长度n和可以修改数字x
n, x = map(int, input().split())
# 输入本次询问的数组
nums = list(map(int, input().split()))
print(sol(nums, n, x))
时空复杂度
时间复杂度：O(N)。需要一次遍历原数组。
空间复杂度：O(N)。dp数组所占空间，如果使用滚动dp数组，空间复杂度可以降到O(1)。
题目二：精华帖子
题目描述
小红书的推荐帖子列表为[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) // 2
if intervals[mid][1] >= li + k:
right = mid
else:
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))
代码
# 题目：【二分查找】小红书2023秋招提前批-精华帖子
# 作者：闭着眼睛学数理化
# 算法：二分查找/前缀和
# 代码有看不懂的地方请直接在群上提问
# 想要参加高阶算法训练营添加微信 278166530
# 输入帖子数量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-l
pre_sum_list.append(pre_sum_list[-1] + r-l)
# 初始化答案为0
ans = 0
# 遍历每一个区间
for i in range(m):
# 第i个区间的左端点为li
li, ri = intervals[i]
# 初始化二分查找的左闭右开区间
# left为下标i，right为区间个数m
left, right = i, m
# 进行二分查找
# 搜索目标为第一个大于等于li+k的右端点rj的下标j
while left < right:
mid = left + (right-left) // 2
if intervals[mid][1] >= li + k:
right = mid
else:
left = mid + 1
# 退出循环后，left = right即为第一个大于等于li+k的右端点rj的下标j
j = 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和rj
lj, 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)
时空复杂度
时间复杂度：O(mlogm)。m为标记为精华的区间数量，对于每一个区间都去进行二分查找，一共有m个区间，单词二分查找的时间复杂度是O(logm)。
空间复杂度：O(m)。前缀和哈希表所占空间。
题目三：小红的数组构造
题目描述
小红希望你构造一个数组，满足以下条件：
-
- 数组共有
n个元素，且所有元素两两不相等。
- 数组共有
-
- 所有元素的最大公约数等于
k。
- 所有元素的最大公约数等于
-
- 所有元素之和尽可能小。
请你输出数组元素之和的最小值。
输入描述
两个正整数n和k
1 ≤ n, k ≤ 10^5
输出描述
一个正整数，代表数组元素之和的最小值。
示例一
输入
3 1
输出
6
说明
构造数组[1, 2, 3]为满足题意的数组
示例二
输入
2 6
输出
18
说明
构造数列[6, 12]为满足题意的数列。
时空限制
时间限制： 3S
内存限制： 512MB
解题思路
本题较为简单，构造[k, 2k, 3k, ..., nk]这样的数组即为符合要求的数组（这个结论很容易用反证法证明），使用等差数列求和公式可知该数组的和为
k + 2k + 3k + ... + nk = (1 + 2 + 3 + ... + n) * k = (1 + n) * n // 2 * k
故对于输入的两个参数n和k，只需要输出(1 + n) * n * k // 2即为答案。
注意，使用C++和Java的同学要用long而不是int，防止计算结果过大而爆内存。
关于等差数列求和公式和最大公约数相关内容，可详见算法训练营的文档常用数学概念、公式、方法汇总
代码
# 题目：【数学】小红书2023秋招提前批-小红的数组构造
# 作者：闭着眼睛学数理化
# 算法：数学
# 代码有看不懂的地方请直接在群上提问
# 想要参加高阶算法训练营添加微信 278166530
n, k = map(int, input().split())
print((1 + n) * n * k // 2)
时空复杂度
时间复杂度：O(1)。
空间复杂度：O(1)。