V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
sextoybie
V2EX  ›  程序员

想请教下一道面试题

  •  
  •   sextoybie · 2020-12-02 06:47:06 +08:00 · 2970 次点击
    这是一个创建于 1212 天前的主题,其中的信息可能已经有所发展或是发生改变。
    请教下 共享电动车, 小明和小华住同一街上 相隔 X 米。 从小明到小华的路上 有 n 辆电动车 分别在 p1, p2, ...pn 点上。

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

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

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

    身为刚毕业的小明 如何最低成本从他家开始出发到小华家 同时必须使用电动车作为工具呢?
    34 条回复    2020-12-02 20:22:50 +08:00
    yzbythesea
        1
    yzbythesea  
       2020-12-02 07:25:11 +08:00
    这图是个 DAG ?这不是拓扑排序吗?
    Herobs
        2
    Herobs  
       2020-12-02 07:27:32 +08:00 via iPhone
    动态规划,状态是每一辆选择骑或者不骑。
    sextoybie
        3
    sextoybie  
    OP
       2020-12-02 07:31:17 +08:00
    @yzbythesea 是的,DAG. 该如何跑呢?
    sextoybie
        4
    sextoybie  
    OP
       2020-12-02 07:34:13 +08:00
    当然每当小明遇到一辆电动车, 小明都选择换骑。
    改为
    当然每当小明遇到一辆电动车, 小明都可以选择换骑。
    sextoybie
        5
    sextoybie  
    OP
       2020-12-02 07:35:57 +08:00
    @Herobs 可以说的详细点吗? 是的 基本的理解题目 和需要 都明白点, 就是写不出来。
    dartabe
        6
    dartabe  
       2020-12-02 07:46:19 +08:00
    好简单的动态规划 如果我没理解错

    当前价格 = 到达前一点的最低价格 + min(所有可用的车从前一点到当前一点的价格)
    dartabe
        7
    dartabe  
       2020-12-02 07:51:41 +08:00
    我错了 好像不对
    dartabe
        8
    dartabe  
       2020-12-02 07:53:34 +08:00
    可能是 dfs 直接算
    sextoybie
        9
    sextoybie  
    OP
       2020-12-02 07:55:18 +08:00
    @dartabe dfs 直接算 不能吧, 需要动态规划(吧)
    dartabe
        10
    dartabe  
       2020-12-02 07:57:21 +08:00
    @sextoybie 动规好像不行 前面的选择会影响后面的状态
    dartabe
        11
    dartabe  
       2020-12-02 08:02:58 +08:00
    类似于 leetcode 全排列 截止条件不一样 当然我就 leetcode 100 题水平 高手来看下
    sextoybie
        12
    sextoybie  
    OP
       2020-12-02 08:05:11 +08:00
    @dartabe 动态规划 是可以的, 面试时的提示。还是谢谢大佬的点击和分享
    yzbythesea
        13
    yzbythesea  
       2020-12-02 08:08:30 +08:00
    @sextoybie DFS 可以吧,只是比较笨。

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

    当然我现在觉得这可能不是一个 DAG,那你也可以用 Dijkstra 做
    yzbythesea
        14
    yzbythesea  
       2020-12-02 08:09:19 +08:00
    好奇下这是哪家的面试题,难度有点爆炸。
    youngzy
        15
    youngzy  
       2020-12-02 08:24:42 +08:00 via Android
    记录到每个节点时的最小花费,用到当前节点的花费更新后续可到达节点的最小花费。最终结果即为最终节点记录的最小花费。
    sextoybie
        16
    sextoybie  
    OP
       2020-12-02 08:27:08 +08:00
    @youngzy 嗯 也是这样想的, 就是需要先跑 DP 算出到每个节点时的最小花费。 然后当图是 DAG, 在跑一次?
    xuanbg
        17
    xuanbg  
       2020-12-02 08:31:53 +08:00
    小明能够确保的是每两辆相隔的车,都有充足的电量从上一辆到达下一辆 ,所以必须选择换骑啊。最低成本有得选吗?无非就是自己家里的车尽量骑远一点呗。
    sextoybie
        18
    sextoybie  
    OP
       2020-12-02 08:37:59 +08:00
    @xuanbg 小明能够确保的是 上辆车至少有足够电量到下辆车, 是否能到下下辆 / 下下下辆 因车而异。
    futou
        19
    futou  
       2020-12-02 08:41:41 +08:00
    如果我没理解错的话,题目指的是车可以从 p1 骑到 p2 或 p3,以此类推。p0 貌似一定要骑到 p1,不过无论怎样不影响解题。
    如果是这样的话,这种结构太简单了都用不上 DAG...

    if 终点是奇数
    遍历计算两个相邻奇数点之间的最短路径
    求和
    else
    1. 同奇数处理,然后奇数最短路径+最后一段距离
    2. 判断相邻偶数点两两最短路径+p1 到 p2 距离
    比较 1. 2.取最短
    ilunny
        20
    ilunny  
       2020-12-02 08:41:45 +08:00 via Android
    感觉有点像路由寻址
    xuanbg
        21
    xuanbg  
       2020-12-02 08:42:42 +08:00
    这题目命题不够明确,没说小明到小华家不是一条路。。。真是令人头秃

    每个相邻点都相同,只是代价不同。这不就是求最短路径吗? A*算法就是最简单的实现了。
    xuanbg
        22
    xuanbg  
       2020-12-02 08:44:14 +08:00
    @sextoybie 当然每当小明遇到一辆电动车, 小明都选择换骑。 这是题目里面的。
    futou
        23
    futou  
       2020-12-02 08:44:25 +08:00
    #19 回复完看到了#18 补充信息 2333,参照#15 吧
    xuanbg
        24
    xuanbg  
       2020-12-02 08:46:12 +08:00
    @xuanbg 这题目命题不够明确,没说小明到小华家不是一条路。。。真是令人头秃

    每个相邻点都相通,只是代价不同。这不就是变相的求最短路径吗?两点间的代价就是启动费+里程费,这个代价等同距离。A*算法就是最简单的实现了。
    misdake
        25
    misdake  
       2020-12-02 09:44:14 +08:00
    骑到 i 点下车的最小代价 cost[i] = min { cost[j] + 骑 j 车到 i 点的代价 },j 从电量骑到 i 点的车里选,把每个点选择的 j 存下来最后反查
    hejw19970413
        26
    hejw19970413  
       2020-12-02 09:45:20 +08:00
    贪心就可以
    youngzy
        27
    youngzy  
       2020-12-02 09:47:32 +08:00
    @sextoybie
    可以在 dp 的时候同时记录转移到该节点的节点编号(也就是当前的最优解是从哪个节点转移过来的),这样在 dp 结束的时候你就有了一个反向的路径链,有需要的话可以进一步处理
    zifangsky
        28
    zifangsky  
       2020-12-02 10:01:32 +08:00
    先假设从 P(m) 到其后的某一个点 P(n) 都可以连通,画出一个有向无环图,然后根据「不同导致每辆车可走的米数不同」中的 d1 d2 ... dn 把不可行的边去掉,最后就变成求 最短路问题 了(其中每个边的边长由 C1 C2 ... Cn 和 m1 m2 ... mn 确定)
    yazoox
        29
    yazoox  
       2020-12-02 10:08:20 +08:00
    这个题目有难度,有意思。学习一下。
    看看有没有大神帖代码出来。
    dartabe
        30
    dartabe  
       2020-12-02 10:23:55 +08:00
    我又想了下 dp 可以做 不过要维护一个 dp 数组就可以了

    j = 车辆数目
    dp 数据长度 j
    从尾到头遍历所有车:
    dp[当前地点] = min(当前车能到达的所有点 + dp[当前车能到达的所有点])
    jsun
        31
    jsun  
       2020-12-02 10:56:50 +08:00
    动态规划,先维护一个二维数组表示能到达该点电动车,例如能骑到 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
        32
    newtype0092  
       2020-12-02 11:17:28 +08:00
    有 test case 么?有点思路但是还需要调试一下,上面几位的解法也不太好验证。
    hitmanx
        33
    hitmanx  
       2020-12-02 11:22:34 +08:00
    @jsun 我的思路和你一样。
    shunconf
        34
    shunconf  
       2020-12-02 20:22:50 +08:00
    由于要换车,小明选择公交车直达
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   956 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 21:47 · PVG 05:47 · LAX 14:47 · JFK 17:47
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.