未分類
24 11 月 2020

想请教下一道面试题

想请教下一道面试题

資深大佬 : sextoybie 2

请教下 共享电动车， 小明和小华住同一街上 相隔 X 米。 从小明到小华的路上 有 n 辆电动车 分别在 p1, p2, …pn 点上。

每一电动车的电量 不同导致每辆车可走的米数不同，d1, d2, … dn. (从 P* 点开始算） 小明可以确保的是 每两辆相隔的车，都有充足的电量从上一辆到达下一辆 ， 小华可以确保最靠近小华家的那辆车 有足够的电 量到他家从那点出发.

每辆车都有不同的启动金 C1, C2, …Cn 和每米的价钱 m1, m2, m3…mn. (就是如果小明 启动 电动车 2 ,骑了 4 米 那么小明就是消费了 C2+ 4 * m2 。

当然每当小明遇到一辆电动车， 小明都选择换骑。
小明家里有一辆电动车了， 小明为他冲电的，所以没有启动费， 它可以让小明骑到 P0 米 以每米 m0 的价格

身为刚毕业的小明 如何最低成本从他家开始出发到小华家 同时必须使用电动车作为工具呢？

大佬有話說 (34)

  • 資深大佬 : yzbythesea

    这图是个 DAG ？这不是拓扑排序吗？

  • 資深大佬 : Herobs

    动态规划，状态是每一辆选择骑或者不骑。

  • 主 資深大佬 : sextoybie

    @yzbythesea 是的，DAG. 该如何跑呢？

  • 主 資深大佬 : sextoybie

    当然每当小明遇到一辆电动车， 小明都选择换骑。
    改为
    当然每当小明遇到一辆电动车， 小明都可以选择换骑。

  • 主 資深大佬 : sextoybie

    @Herobs 可以说的详细点吗？ 是的 基本的理解题目 和需要 都明白点， 就是写不出来。

  • 資深大佬 : dartabe

    好简单的动态规划 如果我没理解错

    当前价格 = 到达前一点的最低价格 + min(所有可用的车从前一点到当前一点的价格)

  • 資深大佬 : dartabe

    我错了 好像不对

  • 資深大佬 : dartabe

    可能是 dfs 直接算

  • 主 資深大佬 : sextoybie

    @dartabe dfs 直接算 不能吧， 需要动态规划（吧）

  • 資深大佬 : dartabe

    @sextoybie 动规好像不行 前面的选择会影响后面的状态

  • 資深大佬 : dartabe

    类似于 leetcode 全排列 截止条件不一样 当然我就 leetcode 100 题水平 高手来看下

  • 主 資深大佬 : sextoybie

    @dartabe 动态规划 是可以的, 面试时的提示。还是谢谢大佬的点击和分享

  • 資深大佬 : yzbythesea

    @sextoybie DFS 可以吧，只是比较笨。

    先拓扑排序，然后必经点得选，凡非必经点儿之间，选最短的组合。

    当然我现在觉得这可能不是一个 DAG，那你也可以用 Dijkstra 做

  • 資深大佬 : yzbythesea

    好奇下这是哪家的面试题，难度有点爆炸。

  • 資深大佬 : youngzy

    记录到每个节点时的最小花费，用到当前节点的花费更新后续可到达节点的最小花费。最终结果即为最终节点记录的最小花费。

  • 主 資深大佬 : sextoybie

    @youngzy 嗯 也是这样想的， 就是需要先跑 DP 算出到每个节点时的最小花费。 然后当图是 DAG， 在跑一次？

  • 資深大佬 : xuanbg

    小明能够确保的是每两辆相隔的车，都有充足的电量从上一辆到达下一辆 ，所以必须选择换骑啊。最低成本有得选吗？无非就是自己家里的车尽量骑远一点呗。

  • 主 資深大佬 : sextoybie

    @xuanbg 小明能够确保的是 上辆车至少有足够电量到下辆车， 是否能到下下辆 / 下下下辆 因车而异。

  • 資深大佬 : futou

    如果我没理解错的话，题目指的是车可以从 p1 骑到 p2 或 p3，以此类推。p0 貌似一定要骑到 p1，不过无论怎样不影响解题。
    如果是这样的话，这种结构太简单了都用不上 DAG…

    if 终点是奇数
    遍历计算两个相邻奇数点之间的最短路径
    求和
    else
    1. 同奇数处理，然后奇数最短路径+最后一段距离
    2. 判断相邻偶数点两两最短路径+p1 到 p2 距离
    比较 1. 2.取最短

  • 資深大佬 : ilunny

    感觉有点像路由寻址

  • 資深大佬 : xuanbg

    这题目命题不够明确，没说小明到小华家不是一条路。。。真是令人头秃

    每个相邻点都相同，只是代价不同。这不就是求最短路径吗？ A*算法就是最简单的实现了。

  • 資深大佬 : xuanbg

    @sextoybie 当然每当小明遇到一辆电动车， 小明都选择换骑。 这是题目里面的。

  • 資深大佬 : futou

    #19 回复完看到了#18 补充信息 2333，参照#15 吧

  • 資深大佬 : xuanbg

    @xuanbg 这题目命题不够明确，没说小明到小华家不是一条路。。。真是令人头秃

    每个相邻点都相通，只是代价不同。这不就是变相的求最短路径吗？两点间的代价就是启动费+里程费，这个代价等同距离。A*算法就是最简单的实现了。

  • 資深大佬 : misdake

    骑到 i 点下车的最小代价 cost[i] = min { cost[j] + 骑 j 车到 i 点的代价 }，j 从电量骑到 i 点的车里选，把每个点选择的 j 存下来最后反查

  • 資深大佬 : hejw19970413

    贪心就可以

  • 資深大佬 : youngzy

    @sextoybie
    可以在 dp 的时候同时记录转移到该节点的节点编号（也就是当前的最优解是从哪个节点转移过来的），这样在 dp 结束的时候你就有了一个反向的路径链，有需要的话可以进一步处理

  • 資深大佬 : zifangsky

    先假设从 P(m) 到其后的某一个点 P(n) 都可以连通，画出一个有向无环图，然后根据「不同导致每辆车可走的米数不同」中的 d1 d2 … dn 把不可行的边去掉，最后就变成求 最短路问题 了（其中每个边的边长由 C1 C2 … Cn 和 m1 m2 … mn 确定）

  • 資深大佬 : yazoox

    这个题目有难度，有意思。学习一下。
    看看有没有大神帖代码出来。

  • 資深大佬 : dartabe

    我又想了下 dp 可以做 不过要维护一个 dp 数组就可以了

    j = 车辆数目
    dp 数据长度 j
    从尾到头遍历所有车:
    dp[当前地点] = min(当前车能到达的所有点 + dp[当前车能到达的所有点])

  • 資深大佬 : jsun

    动态规划，先维护一个二维数组表示能到达该点电动车，例如能骑到 P6 的是 P3 和 P5，则 A[6]=[3,5]。然后列 dp 公式，dp[6]=Min((P6-P5)*m5+C5+dp[5],(P6-P3)*m3+C3+dp[3]) 。dp[n]=遍历 A[n],求最小值 min

  • 資深大佬 : newtype0092

    有 test case 么？有点思路但是还需要调试一下，上面几位的解法也不太好验证。

  • 資深大佬 : hitmanx

    @jsun 我的思路和你一样。

  • 資深大佬 : shunconf

    由于要换车，小明选择公交车直达