De Shaw OA 实习生难题

问题 1

给定一个二进制字符串，寻找长度为 3 的子序列，要求相邻字符不同（例如：101, 010）。

约束：N <= 1e5

问题 2

给定一个数组，我们希望通过以下操作将其变为非递增：

• 可以从 a[i] 移动 1 到 a[i+1]，之后 a[i] 变为 a[i]-1，a[i+1] 变为 a[i+1]+1（如果 i+1<n）
• 可以从 a[i] 移动 1 到 a[i-1]，之后 a[i] 变为 a[i]-1，a[i-1] 变为 a[i-1]+1（如果 i-1>=0）

计算将其变为非递减所需的最小移动次数。

约束：N <= 250，a[i] <= 1e9

示例：a[] = [5, 3, 2, 3, 3, 3] -> [4, 4, 2, 3, 3, 3] -> [4, 3, 3, 3, 3, 3]，输出为 2。

问题 3

给定数组 a[]，计算满足 1 <= b[i] <= a[i] 且相邻元素不同的数组 b 的数量。结果需对 1e9+7 取模，因为答案可能很大。

约束：N <= 1e5，a[i] <= 1e6

示例：a[] = [2, 3]，b[] = [1, 2], [1, 3], [2, 1], [2, 3]，输出为 4。

博主点评： 这三道题目不仅考察了基础的动态规划和贪心算法，还涉及到复杂的状态转移与组合计数。对于面试者来说，掌握这些问题的解法将大大提升他们的编程能力与逻辑思维。