小红书，今年给的太多啦！

大家好，我是吴师兄。

越来越感觉互联网行业在各个领域都是赢者通吃一切的规则，比如校招，有的人 0 offer，有的人却在挑 offer，最近有不少同学跟我说拿到了包括小红书在内的好几个 offer，由于小红书给的待遇很诱人，决定去小红书。

今天就来分享一下小红书的几道算法题，有兴趣的同学可以尝试一下自己能做出几题。

题目一：连续子数组最大和

题目描述

小红拿到了一个数组，她希望进行最多一次操作：将一个元素修改为x。小红想知道，最终的连续子数组最大和最大是多少？

输入描述

第一行输入一个正整数t，代表询问次数。

对于每次询问，输入两行：

第一行输入两个整数n和x。代表数组的大小，以及小红可以修改成的元素。

第二行输入n个正整数a_i，代表小红每次询问拿到的数组。

代码语言：javascript复制

1 ≤ t ≤ 100000
1 ≤ n ≤ 200000
-10^9 ≤ x, a_i ≤ 10^9

每组所有询问的n的和不超过200000。

输出描述

输出t行，每行输出一个整数，代表每次询问能够得到的连续子数组的最大和。

示例

输入

代码语言：javascript复制

3
5 10
5 -1 -5 -3 2
2 -3
-5 -2
6 10
4 -2 -11 -1 4 -1

输出

代码语言：javascript复制

15
-2
15

说明

第一组询问，修改第二个数。

第二组询问，不进行任何修改。

第三组询问，修改第三个数。

时空限制

时间限制：3s

内存限制：512MB

解题思路

注意，本题的部分逻辑和LeetCode53. 最大子数组和完全一致，属于本题的一道延申题。而修改的操作，可以类比股票问题的做法。

代码

代码语言：javascript复制

# 想要参加高阶算法

时空复杂度

时间复杂度：O(N)。需要一次遍历原数组。

空间复杂度：O(N)。dp数组所占空间，如果使用滚动dp数组，空间复杂度可以降到O(1)。

题目二：精华帖子

题目描述

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

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

输入描述

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

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

代码语言：javascript复制

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

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

输出描述

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

示例

输入

代码语言：javascript复制

5 2 3
1 2
3 5

输出

代码语言：javascript复制

说明

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

时空限制

时间限制：3s

内存限制：512MB

解题思路

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

代码语言：javascript复制

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个区间之间的精华帖子数量，注意上述两种区别，需要分类讨论。

代码语言：javascript复制

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))

代码

代码语言：javascript复制

# 想要参加高阶算法

时空复杂度

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

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

题目三：小红的数组构造

题目描述

小红希望你构造一个数组，满足以下条件：

1. 数组共有n个元素，且所有元素两两不相等。
1. 所有元素的最大公约数等于k。
1. 所有元素之和尽可能小。

请你输出数组元素之和的最小值。

输入描述

两个正整数n和k

代码语言：javascript复制

1 ≤ n, k ≤ 10^5

输出描述

一个正整数，代表数组元素之和的最小值。

示例一

输入

代码语言：javascript复制

3 1

输出

代码语言：javascript复制

说明

构造数组[1, 2, 3]为满足题意的数组

示例二

输入

代码语言：javascript复制

2 6

输出

代码语言：javascript复制

说明

构造数列[6, 12]为满足题意的数列。

时空限制

时间限制： 3S

内存限制： 512MB

解题思路

本题较为简单，构造[k, 2k, 3k, ..., nk]这样的数组即为符合要求的数组（这个结论很容易用反证法证明），使用等差数列求和公式可知该数组的和为

代码语言：javascript复制

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，防止计算结果过大而爆内存。

关于等差数列求和公式和最大公约数相关内容，可详见算法训练营的文档常用数学概念、公式、方法汇总

图片

代码

代码语言：javascript复制

# 想要参加高阶算法训练营添加微信 278166530

n, k = map(int, input().split())
print((1   n) * n * k // 2)

时空复杂度

时间复杂度：O(1)。

空间复杂度：O(1)。

微信 dp 内存数组算法

0 人点赞