见路不走

V1

2022/11/10阅读:11主题:红绯

【每日一题】环形加油站

N 个加油站组成一个环形,给定两个长度都是 N 的非负数组 oil 和 dis(N > 1),oil[i] 表示第 i 个加油站存的油可以跑多少千米,dis[i] 代表第 i 个加油站到环中下一个加油站相隔多少千米。

假设你有一辆邮箱足够大的车,初始时车里没有油。如果车从第 i 个加油站出发,最终可以回到这个加油站,那么第 i 个加油站就算良好出发点,否则就不算。请返回长度为 N 的 boolean 数组 res,res[i] 代表第 i 个加油站是不是良好出发点。

解法一:暴力算法

分析:

如果下图绿色节点顺利走完一圈,它就是良好出发点。

其实我们可以将 oil - dis 得到纯能数组。那么原问题就转化为:在纯能数组组成的环上,从起始点出发,累加纯能数组上的数值,累加和始终不为负数,那么起始点就是良好起点。

时间复杂度:

空间复杂度:

def stations(dis, oil):
    if not dis or not oil or len(dis) < 2 or len(dis) != len(oil): return
    res = [False] * len(dis)
    n = len(dis)
    # 起始点(大于 0)
    init = -1
    # 生成纯能数组
    for i in range(n):
        dis[i] = oil[i] - dis[i]
        if dis[i] > 0: init = i

    if init == -1return res

    # 尝试以每个加油站为出发点
    for i in range(n):
        res[i] = circular(dis, i) >= 0

    return res

# 以 i 为出发点,尝试走完一圈。如果累计和为 0 ,退出
def circular(dis, i):
    if dis[i] < 0return dis[i]
    n = len(dis)
    sum_value = dis[i]
    j = i + 1
    while j % n != i:
        sum_value += dis[j % n]
        if sum_value < 0break
        j += 1
    return sum_value

解法二:滑动窗口

连通区(窗口)伸缩规则:使用 [ start, end ) 表示连通区,前闭后开。

start 初始值为 init(初始点:在纯能数组中选择一个值大于 0 的数据作为初始点)

end = next_index( init , n)

如果 end 能扩展连通区:rest >= 0,就逆时针走,一直走到 rest 小于或者走到 start 位置;否则就顺时针移动 start,将所需的油累计在 need 变量上,在 end 扩展时使用 need,使用完毕后将 need 还原成 0。

跑完一圈后会出现两种情况:

  • 没找到良好出发点
  • 找到了一个良好出发点(start)

情况一:没找到良好出发点

当走完一圈,如果 start 对应加油站不是一个良好出发点,就表明所有加油站不都不是良好出发点。

如下图:连通区是:【G,H,I,A,B】,start 在 G 位置,不是一个良好出发点,那么【H,I,A,B】 也不是良好出发点。因为在连通区内 G 是可以到达【H,I,A,B】任何位置。G 带着剩余油(rest>=0) 到达【H,I,A,B】都没走通,那么以【H,I,A,B】为起始点(rest==0) 更不可能走完一圈。

连通图的 start 没有扩展到【F,E,D,C】说明,【F,E,D,C】无法达到 G 位置,所以【F,E,D,C】也不是良好出发点。

综上所述所此种情况下,所有的加油站都不是良好出发点。

情况二:找到了一个良好出发点(start)

当走完一圈,如果 start 对应加油站是一个良好出发点(rest >= 0),我们需要寻找其他良好出发点。

如下图:连通区是:【G,H,I,A,B,C,D,E,F】,start 所在的 G 位置是一个良好出发点,那么从 start 上一个加油站 start1 出发到一路追溯到 init ,任何一个能到 G 的加油站都是良好出发点。

时间复杂度:

空间复杂度:

def stations2(dis, oil):
    if not dis or not oil or len(dis) < 2 or len(dis) != len(oil): return
    n = len(dis)
    # 起始点(大于 0)
    init = -1
    # 生成纯能数组
    for i in range(n):
        dis[i] = oil[i] - dis[i]
        if dis[i] > 0: init = i

    return [False] * len(dis) if init < 0 else enlarge_area(dis, init)

def enlarge_area(dis, init):
    n = len(dis)
    res = [False] * n
    # 连通区起始点
    start = init
    # 连通区终点
    end = next_index(init, n)
    # 突破 start 需要油量
    need = 0
    # 剩余油量
    rest = 0

    # 以 init 为起始点,跑一圈
    while True:
        # 连通区 start 扩展(如果 end 无法突破,就扩展 start,所需的油都累计在 need 中)
        if dis[start] < need:
            # 如果 dis[start] 为负数,need 值增加
            # 如果 dis[start] 为正数,need 值减少
            need -= dis[start]
        else:
            # 将 need 的累积的油计算到 rest
            rest += dis[start] - need
            # 重置 need
            need = 0
            # end 连续突破
            while rest >= 0 and end != start:
                rest += dis[end]
                end = next_index(end, n)

            # 如果 end 连续突破后,rest 还有剩余,说明是 end == start 的条件跳出循环的,已经跑了一圈了。
            # 跑过一圈后,rest >= 0 油有剩余,说明以 start 是良好起始点
            # 跑过一圈后,rest < 0 油没有剩余,说明没有一个良好起始点,直接返回
            if rest >= 0:
                res[start] = True
                # 寻找其他的良好起始点
                # 所有能正常能达到 start 的加油站都是良好起始点
                # 所有从 start 上一个节点开始一路向上寻找能正常穿过 start 的加油站,并将对应 res 设置为 True
                connect_good(dis, last_index(start, n), init, res)
                # 已经跑了一圈了,其他良好起始点也寻找完毕,任务完成,跳出。
                break
        start = last_index(start, n)
        if start == init or start == last_index(end, n):
            break
    return res

def connect_good(dis, start, init, res):
    need = 0
    n = len(dis)
    while start != init:
        # 如果当前节点 start 无法穿越,用 need 记录所需要油,继续向上寻找
        if dis[start] < need:
            need -= dis[start]
        else:
            # 成功穿越
            res[start] = True
            need = 0
        start = last_index(start, n)

      
# 数组需要循环访问,需要在两个端点做特殊处理
# 获取 index 前一个索引
def last_index(index, size):
    return size - 1 if index == 0 else index - 1

# 获取 index 后一个索引
def next_index(index, size):
    return 0 if index == size - 1 else index + 1

对数器

import random

def check():
    for _ in range(100):
        n = int(random.random() * 5) + 1
        oil = [int(random.random() * 5) + 1 for _ in range(n)]
        dis = [int(random.random() * 5) + 1 for _ in range(n)]

        res = stations(dis[:], oil[:])
        res2 = stations2(dis[:], oil[:])

        if res != res2:
            print("ERROR""res=", res, "res2=", res2, "oil=", oil, "dis=", dis)
    print("Nice")

check()

分类:

后端

标签:

数据结构与算法

作者介绍

见路不走
V1