use*_*787 39 algorithm dynamic-programming
我收到了这个面试问题,并坚持下去:
从0号站开始有无数的火车站.
有无数的火车.第n列火车在所有k*2 ^(n-1)站停靠,其中k在0和无穷大之间.
当n = 1时,第一列火车停在0,1,2,3,4,5,6等站点.
当n = 2时,第二列火车在0,2,4,6,8等站停止.
当n = 3时,第三列火车在0,4,8,12等站停靠.
给定起始站号和终端站号,返回它们之间的最小停靠点数.您可以使用任何列车从一站到另一站.
例如,start = 1和end = 4之间的最小停靠次数为3,因为我们可以从1到2到4.
我正在考虑一个动态编程解决方案,它将存储在和dp[start][end]之间的最小步数.我们使用构建数组.但我无法让它发挥作用.你是如何解决这个问题的？startendstart...mid1, mid1...mid2, mid2...mid3, ..., midn...end
澄清:
Sai*_*Bot 27
我认为你根本不需要动态编程来解决这个问题.它基本上可以用二进制计算表示.
如果您将电台号码转换为二进制,它会立即告诉您如何从电台0到达,例如,
站6 = 110
告诉你,你需要乘坐n = 3列车和n = 2列车各一站.因此,二进制表示的交叉总和会告诉您需要多少步骤.
下一步是弄清楚如何从一个站到另一个站.我会再举例说明这一点.假设你想从7号站到23号站.
站7 = 00111
站23 = 10111
你要做的第一件事是进入中间站.此停止由指定
(开始和结束站点相同的最高位)+(第一个不同的位)+(用零填充)
在我们的例子中,中间停止是16(10000).您需要进行的步骤可以通过该数字与起始站的差值来计算(7 = 00111).在我们的例子中,这产生了
10000 - 00111 = 1001
现在你知道,你需要2站(n = 1列车和n = 4)从7到16.剩下的任务是从16到23,再次这可以通过相应的差异来解决
10111 - 10000 = 00111
所以,你需要另外3站从16到23(n = 3,n = 2,n = 1).这总共给出了5个停靠点,只使用了两个二进制差值和交叉求和运算符.可以从比特表示7-> 8-> 16-> 20-> 22-> 23中提取所得到的路径
编辑:
为了进一步澄清中间停止,让我们假设我们想要去
站5 = 101到
站7 = 111
在这种情况下,中间站将是110,因为
在起始站和结束站中相等的最高位= 1
第一个不同的位= 1
用零填充= 0
我们需要一步到那里(110 - 101 = 001),还有一步从那里到终点站(111 - 110 = 001).
关于中间站
中间停止的概念有点笨拙,但我找不到更优雅的方式,以使位操作工作.中间停止是在开始和结束之间的停止,其中最高级别位切换(这就是为什么它以它的方式构造).在这方面,它是最快的列车(开始和结束之间)运行的停靠点(实际上所有能够捕获的列车都停在那里).
通过从终端站(位表示)中减去中间停止(位表示),您可以将问题简化为从站0开始的简单情况(参见我的答案的第一个示例).
通过从中间停止减去起始站,您也可以将问题简化为简单情况,但假设您从中间站到达起始站,这相当于相反的方向.
use*_*ica 23
首先,问你是否可以倒退.这听起来像你不能,但正如这里所呈现的那样(可能没有反映你收到的问题),问题从未给出任何这些列车的明确方向.(我看到你现在编辑了你的问题,说你不能倒退.)
假设您不能倒退,策略很简单:始终使用最高编号的可用列车,不会超出您的目的地.
假设您处于停靠状态s,并且在当前位置停靠并且没有超调的最高编号列车是火车k.在火车上旅行一次k会让你停下来s + 2^(k-1).没有更快的方法可以到达那个站点,也没有办法跳过那个站点 - 没有列车编号的列车超过列车k的任何站点,没有更高编号的列车停在列车k的站点之间,所以你不能在到达之前乘坐更高编号的火车.因此,火车k是您最好的直接行动.
考虑到这一策略,剩下的大部分优化都是有效的比特技巧,以计算停靠次数,而无需明确确定路线上的每个停靠点.
我将尝试证明我的算法是最优的.
该算法是"采用不超过目的地的最快火车".
这有多少停止有点棘手.
将两个停靠点编码为二进制数.我声称可以忽略相同的前缀; 从去的问题a,以b相同的距离去的问题a+2^n来b+2^n,如果2^n > b,因为之间的停止2^n和2^(n+1)仅仅之间的停止0和2^n转向过度.
由此,我们可以减少跳闸a,b以确保b设置高位,a并且不设置相同的"高"位.
要解决从5(101)到7(111)的问题,我们只需要解决从1(01)到3(11)的问题,然后将停止数字向上移动4(100).
从去x到2^n + y,在那里y < 2^n(因此x是),我们首先要去2^n,因为没有火车是跳过2^n不也跳过2^n+y < 2^{n+1}.
因此,任何一组之间停止的x和y必须停止2^n.
因此停止从最佳数目x以2^n + y从停止的次数x来2^n,随后停止的从数2^n到2^n+y(含)(或从0到y,这是相同的).
我建议从得到的算法0来y与高阶位设置入手,采取让你有车,然后继续在列表中向下.
声明:为了使用k 1s 生成数字,您必须至少k乘坐火车.作为证明,如果你坐火车并且它不会导致你的停止号码,它会设置1位.如果您乘坐火车并确实导致进位,则结果数字最多比开始时多1个.
从获得x到2^n是有点麻烦,但可以进行通过跟踪你坐火车简单的倒退.
映射s_i到s_{2^n-i}和扭转列车步骤,用于从获得的任何解决方案x来2^n描述了一种用于从得到的溶液中0以2^n-x.对于前向解决方案而言,任何最佳解决方案对于后向解决方案都是最佳的,反之亦然.
使用从得到的结果0来y,我们就得到从最佳路由a到b哪里b最高位集2^n和a不具有位设置为#b-2^n+# 2^n-a,这里#的意思是"在二进制表示法设置的位数".通常,如果a并且b有一个公共前缀,只需删除该公共前缀即可.
产生上述步数的本地规则是"在当前位置乘坐不超出目的地的最快列车".
对于来自的部分2^n,2^n+y我们在上面的证明中明确地做了.对于从那里x开始的部分,2^n这很难看.
首先,如果设置了低位x,显然我们必须采取我们可以采用的第一个也是唯一一个列车.
其次,想象一下x有一些未设置的低阶位集合,比如说m.如果我们打车从游戏要x/2^m到2^(n-m),然后乘以缩放停止编号2^m我们会得到一个解决方案,从去x到2^n.
#(2^n-x)/2^m=#2^n - x.因此,这种"缩放"解决方案是最佳的.
由此,我们总是在这个最优解决方案中使用与我们的低阶设置位相对应的列车.这是可用的最长列车,并没有超调2^n.
QED