c# - 完成给定场景的最短路径

Question

我在面试中被要求编写以下场景的代码

一台电视有 0-450 个 channel ，但 Remote 按钮 2、5、8、9 出现故障，所以写一个从用户那里获取输入并通过最短路径遍历该 channel 的程序

示例:

47 -> no need to traverse button 4,7 is available

45 -> 44+1 output from which channel to traverse and how many traversal required to reach 45.

55 -> 55 can be reached from 47 only coz 54 has 5. |||ly (50-55) has 5 in it so again 48 and 49 has 8 and 9 respectively.

我已经尝试了我的逻辑，但甚至无法以这样一种方式进行编码，它是所有输入的最佳最短路径请帮助我理解逻辑或向我展示程序。

Answer 1

换一种方式思考。一个有效的解决方案只能由有效数字组成。

---

1. 通过从所有可能的按钮中删除故障按钮来构建有效的按钮集

   0,1,3,4,6,7

2. 从左到右查找 channel 号的第一个无效数字。 如果找到，转到第 3 步。否则，无需遍历按钮。

3. 仅在设置了有效按钮的情况下，在两侧生成最接近 channel 号的两个数字。

   For example: channel number = 189

   Blind all digits on the right of first invalid digit -> 18x

   Upper bound: Look for a slightly bigger digit of 8 from valid set, but not found. In such case, we look for a bigger valid digit of 1, we get 3. Then pad smallest valid digit for the rest. We get 300.

   Lower bound: Look for a slightly smaller digit of 8 from valid set, we get 7. Then pad largest valid digit for the rest. We get 177.

4. 如果无法形成下限或上限( channel 号 450 应获得 0 作为有效解)且超出上限，则考虑边界情况

5. 将两个数字与 channel 号进行比较，得到最接近的一个。

6. 格式和输出

---

时间复杂度:所有情况下都是 O(log(n))