2

我最近在一次采访中遇到了以下问题。

有一个序列{a1, a2, a3, a4, ..... aN}。运行是序列的最大严格递增或严格递减的连续部分。例如。如果我们有一个序列，{1,2,3,4,7,6,5,2,3,4,1,2} 我们有 5 次可能的运行{1,2,3,4,7}、{7,6,5,2}、{2,3,4}和。{4,1}{1,2}

给定四个数字N, M, K, L. 计算N恰好M运行的可能数字序列的数量，序列中的每个数字小于或等于K并且相邻数字之间的差小于等于L。

4

3 回答 3

1

可能有一种方法可以对其进行分析分析并提出 O(1) 解决方案。但是，这需要比我聪明得多的人才能弄清楚:) 这是一个动态编程解决方案。

对于这个解决方案，我假设所有值都必须是正数。此外，我假设序列中的所有值都必须不等于先前的值。问题中似乎暗示了这两个条件，但从未明确说明。

首先，让我们稍微改变一下问题，以便除了N、M、K和之外L，我们还可以得到序列中最后一项的值 a n。让我们还添加另一个变量I，它表示最后一项是递增还是递减序列的一部分。然后我们将定义一个函数F来返回给定所有这些值的可能序列的数量。

N = 序列中值的数量
M = 序列中的“运行”次数
K = 允许的最大值
L = 相邻序列项之间的最大差异
I = 最后一项是增加还是减少
a n = 序列中的最后一项
F K,L (N,M,I,a n ) = 给定所有这些值的可能序列数

现在，如果我们有一种方法来计算F，我们可以将n的所有可能值 （从 1 到 K）相加并I得到问题的答案。

假设 I = “增加”。我们想用 的“较小”值来表示F K,L (N,M,"increasing", an )F，因此我们可以递归地计算 的值F以获得最终值。我们将通过对n-1的F所有可能值求和来做到这一点；也就是说，我们基本上说它等于可以以n结尾的有效长度序列的数量，然后我们想象将n附加到它们中的每一个。FN-1

因为我们知道a n是递增序​​列的一部分(I = "increasing")，所以我们知道a n-1 < a n （我们将很快讨论另一种情况）。我们也知道n-1必须在n -1之L内；因此max(1, a n - L) <= a n-1 < a n。

我们现在有两种情况要考虑，这取决于前一项n-1是增加还是减少：

  1. 一个n-1正在增加。然后我们还在增加，所以F我们感兴趣的值是
    F K,L (N-1,M,"increasing",a n-1 )。
  2. n- 1正在减少。 a n现在正在增加，因此现在将再出现一个“运行”值。因此，F我们感兴趣的值是
    F K,L (N-1,M-1,"decreasing",a n-1 )。

我们将所有这些情况对a n-1的所有可能值求和，以获得F K,L (N,M,"increasing", an )的值。我们可以以类似的方式找到F K,L (N,M,"decreasing", an ) ，只是我们将a n -1限制为a n < a n-1 <= min(K, a n +L)，我们从M案例#1而不是案例#2中减去1。

最后，我们陈述基本情况。 F K,L (N,M,I,a n )：如果 M < 1 或 M > N，则为 0；1 如果 N = 1。

然后，正如我上面提到的，只需将F K,L (N,M,I,a n )I中的和a n的所有值相加，即可得到原始问题的答案。运行时复杂度为O(KMN)

于 2012-03-14T18:26:11.990 回答
0

这里有一些提示：

帖子标签似乎表明这是一次电话采访，这意味着您应该了解欧拉数。更具体地说，总共有 M 次升序和降序运行的 N 的排列数由 2*A(N,M/2-1) 给出，也写为

2*  /     N   \
    \ M/2 - 1 /

可以递归求解为结果的 2 倍：

let x = M/2-1; then
A(n,x)=(n-x)*A(n-1,x-1)+(x+1)*A(n-1,x)

两个进一步的限制，k 和 L，用于控制置换循环的形式。例如，如果 L=3，则不允许排列 {9,1,3,6,2}，因为在循环 [1,2,9] 中，9 太大。

您的简历可能将您描绘成组合学专家，这仅意味着您需要查看您的学校笔记。无论如何，我希望这能让你走上自己的道路。

于 2012-03-19T18:16:53.557 回答
0

我将问题分解如下。运行必须在增加和减少之间交替，因此重要的数字是方向转向的地方。对于上面的例子，重要的数字1 - 7 - 2 - 4 - 2如下所示：

(1,2,3,4,7,6,5,2,3,4,1,2)
 x       x     x   x x x

假设你已经给出了这些转折点的位置和值，例如你有

(1,7,2,4,1,2)

然后我们要计算在数字之间填充的方式的数量。这仅取决于N并且L因为我们已经在使用来自K和的约束M来制作骨架。这里的规则是缺失的数字在给定数字之间是单调的，并且不会跳跃超过L. 这是一个简单的计数问题（稍后会详细介绍）。

接下来计算骨架的数量，这仅取决于Kand M（填充它们的计数可能是 0 基于Nand L）。我们对这些了解多少？如果没有间隙，这必须是长度的交替序列（上下上下），M+1其值介于1和之间K。同样，这是经过充分研究的，不难计算。

我对这种方法的唯一犹豫是没有一种简单的方法可以将这两个计数结合起来，所以它不会给出一个干净的公式。但是，它仍然比详尽地枚举解决方案有了很大的改进，也许可以进一步改进这个想法，以提供一个封闭的或干净的递归公式。

于 2012-03-14T18:54:07.937 回答