HackerRank中的“服务车道”

Question

问题陈述：

卡尔文在101高速公路上开着他最喜欢的车。他注意到，他的车辆的检查引擎灯开着，他想立即维修，以避免任何风险。幸运的是，一条服务车道与高速公路平行行驶。高速公路和服务车道的长度为N个单位。服务车道由单位长度的N段组成，每个区段可以有不同的宽度。卡尔文可以进入和退出任何部分。让我们将入口段称为索引i，将退出段称为索引j，假设出口段位于入口段(j>i)和i≥0之后。Calvin必须遍历从索引I到索引j的所有段(都包括在内)。卡尔文有三种类型的车辆-自行车，汽车和卡车，分别代表1，2和3。这些数字也表示车辆的宽度。给出了一个长度为N的数组width[]，其中宽度K表示服务车道的kth段的宽度。保证在维修过程中，他最多可以通过1000段，包括进出段。

• 如果宽度K是1，只有自行车可以通过kth段。
• 如果宽度K为2，自行车和汽车可以通过kth段。
• 如果宽度K为3，则任何自行车、汽车或卡车都可以通过kth段。

给定卡尔文车辆在服务车道上的入口和出口点，输出通过服务车道(包括出入口段)的最大车辆类型输入格式--第一行输入包含两个整数-N& T，其中N是高速公路的长度，T是测试用例的数量。下一行有N个分隔整数，表示宽度数组。测试用例紧随其后。每个测试用例包含两个整数-I& j，其中i是Calvin进入服务车道的段的索引，j是他退出的车道段的索引。输出每个测试用例的格式，打印代表通过服务车道的最大车辆类型的号码。注: Calvin必须通过从索引I到索引j的所有段(都包括在内)。约束:2 <= N <= 100000 1 <= T <= 10 0 0 <= i

解决方案：

N, T = map(int, input().split())
widths = list(map(int, input().split()))
for _ in range(T):
    i, j = map(int, input().split())
    vehicle = 3
    for x in range(i, j+1):
        width = widths[x]
        if width == 1:
            vehicle = 1 # Only a bike can pass
            break
        elif width == 2:
            vehicle = 2 # Only a car or bike can pass
    print(vehicle)

我正在寻找任何方法使这个更短，更简单或更毕达通。

Answer 1

您最多有1000个测试用例，每个服务通道最多有1000个部分，所以这种方法是可行的，但是我们可以做得更好。

考虑服务车道宽度为1的索引数组，以及宽度为2的索引数组。

N, T = map(int, input().split())

ones = []
twos = []

for i, width in enumerate(map(int, input().split())):
    if width == 1:
        ones.append(i)
    elif width == 2:
        twos.append(i)

然后，可以使用二进制搜索来查看每个段是否包含1或2。

for _ in range(T):
    start, end = map(int, input().split())
    if segment_search(ones, start, end) != -1:
        print(1)
    elif segment_search(twos, start, end) != -1:
        print(2)
    else:
        print(3)

我们的指数已经很好了。当索引位于[start, end]范围内时，我们的搜索停止：

def segment_search(xs, start, end):
    low = 0
    high = len(xs) - 1
    while low <= high:
        mid = (low + high) // 2
        x = xs[mid]
        if start <= x and x <= end:
            return mid
        if end < x:
            high = mid - 1
        else:
            low = mid + 1
    return -1

由于ones和twos不能有超过10万个元素，所以每次调用segment_search最多需要17个步骤。

Answer 2

更短、更简单和更Pythonic的是：

N, T = map(int, input().split())
widths = list(map(int, input().split()))
for _ in range(T):
    i, j = map(int, input().split())
    vehicle = min(widths[segment] for segment in range(i, j + 1))
    print(vehicle)

不过，当你遇到自行车专用路段时，你可能会错过捷径。

为了清晰起见，我还将x重命名为segment。

Answer 3

我对这个问题的解决方案，只要你不介意时间的复杂性，而更喜欢一个琵琶(精确)代码-

def serviceLane(n, cases):
    for i,j in cases:
        return min(width[i:j+1])