algorithm - 最少停靠站数

Question

我收到了这个面试问题并卡住了:

There are an infinite number of train stops starting from station number 0.

There are an infinite number of trains. The nth train stops at all of the k * 2^(n - 1) stops where k is between 0 and infinity.

When n = 1, the first train stops at stops 0, 1, 2, 3, 4, 5, 6, etc.

When n = 2, the second train stops at stops 0, 2, 4, 6, 8, etc.

When n = 3, the third train stops at stops 0, 4, 8, 12, etc.

Given a start station number and end station number, return the minimum number of stops between them. You can use any of the trains to get from one stop to another stop.

For example, the minimum number of stops between start = 1 and end = 4 is 3 because we can get from 1 to 2 to 4.

我正在考虑一个动态编程解决方案，它将在 dp[start][end] 中存储 start 和 end< 之间的最少步数。我们将使用 start...mid1, mid1...mid2, mid2...mid3, ..., midn...end 构建数组。但我无法让它工作。你如何解决这个问题？

说明:

1. 火车只能从编号较低的站点前进到编号较高的站点。
2. 火车可以从它停靠的任何车站开始。
3. 可以按任何顺序登上火车。第n=1列火车可以在登上第n=3列火车之前或之后登上。
4. 可以多次登上火车。例如允许登上n=1次列车，下一次登上n=2次列车，最后再次登上n=1次列车。

Answer 1

我认为您根本不需要动态规划来解决这个问题。基本上可以用二进制计算来表示。

如果您将车站编号转换为二进制，它会立即告诉您如何从车站 0 到达那里，例如，

station 6 = 110

告诉你，你需要乘坐n=3次火车和n=2次火车各坐一站。所以 popcount二进制表示形式告诉您需要多少步。

下一步是弄清楚如何从一个车站到达另一个车站。 我将通过示例再次展示这一点。假设您想从第 7 站到第 23 站。

station 7 = 00111

station 23 = 10111

您要做的第一件事是中途 parking 。此站点由

指定

(highest bits that are equal in start and end station) + (first different bit) + (filled up with zeros)

在我们的示例中，中间停止点是 16 (10000)。您需要进行的步骤可以通过该数字与起始站(7 = 00111)之差来计算。在我们的示例中，这会产生

10000 - 00111 = 1001

现在您知道了，从 7 站到 16 站需要 2 站(n=1 列火车和 n=4)。 剩下的任务是从 16 到 23，同样这可以通过相应的差异来解决

10111 - 10000 = 00111

因此，从 16 到 23(n= 3、n= 2、n= 1)还需要 3 个停靠点。这总共给你 5 站，只使用两个二进制差异和 popcount。可以从位表示中提取结果路径 7 -> 8 -> 16 -> 20 -> 22 -> 23

编辑:

为了进一步说明中间停靠点，我们假设我们要从

station 5 = 101 to

station 7 = 111

在这种情况下，中间止损将是 110，因为

highest bits that are equal in start and end station = 1

first different bit = 1

filled up with zeros = 0

我们需要一步才能到达那里 (110 - 101 = 001)，从那里到终点站还需要一步 (111 - 110 = 001)。

关于中途停留

中间停止的概念有点笨拙，但我找不到更优雅的方法来让位操作工作。中间停止是开始和结束之间的停止，最高级别位切换(这就是它按原样构建的原因)。在这方面，它是最快的火车(在起点和终点之间)运行的站点(实际上您可以搭乘的所有火车都停在那里)。

通过从终点站(位表示)中减去中间站(位表示)，您可以将问题简化为从站 0 开始的简单情况(参见我的回答的第一个示例)。

通过从中间站减去起点站，您也可以将问题简化为简单情况，但假设您从中间站到起点站，这相当于反过来。