求合理路径

今天在群里看到有人问了这么一道题，如下图所示。瞬间让我大呼这不就是我之前想出的一道面试题么，不过有可能是我当时没有表达清楚，发现小伙伴们理解的不是很透彻。

那我的方法就是基于每个元素的position，构成一个有向图即可。

代码如下（也方便未来自己再重新写😂）

# -*- coding: utf8 -*-
#
import math
from typing import List


def trace_path(vec, pathes):
    if not vec:
        return pathes
    valid_pathes = []
    for item in vec[0]:
        for path in pathes:
            if item > path[-1]:
                valid_pathes.append([*path, item])

    return trace_path(vec=vec[1:], pathes=valid_pathes)


def get_all_valid_path(vec: List[List[int]]) -> List[List[int]]:
    if not vec: return []
    for v in vec:
        if not v:
            return []
    return trace_path(vec=vec[1:], pathes=[[i] for i in vec[0]])


def _sub_sum(path: List[int]) -> int:
    _sum = 0
    for index, item in enumerate(path):
        try:
            next_item = path[index + 1]
            _sum += (next_item - item)
        except IndexError:
            pass
    return _sum


def get_shortest_path(vec: List[List[int]]) -> List[int]:
    """
    输出最短的那个路径
    :param vec:
    :return:
    """
    pathes = get_all_valid_path(vec=vec)
    short_path, short_sum = [], math.inf

    for path in pathes:
        _sum = _sub_sum(path=path)
        if short_sum > _sum:
            short_path = path
            short_sum = _sum
    return short_path


if __name__ == '__main__':
    # 结果
    # 1, 2, 6
    # 1, 2, 7
    # 1, 4, 6
    # 1, 4, 7
    # 3, 4, 6
    # 3, 4, 7
    # 我这里的vec代表元素的position～
    vec = [
        [1, 3, 5],
        [2, 4],
        [6, 7]
    ]
    print(get_all_valid_path(vec))

赏

谢谢你请我吃糖果

支付宝