所有城市旅行所需的最少天数 [英] Minimum window of days required to travel all cities

问题描述

这是我在编码挑战中遇到的一个有趣的问题：

This is an interesting question that I came across in a coding challenge:

有k个城市和n天。旅行社将在第n天向您显示城市k。您应该找到可以访问所有城市的最少天数。您还可以多次访问城市，但理想情况下您不希望这样做，因为您希望将天数减至最少。

There are k cities and n days. A travel agent is going to show you city k on day n. You're supposed to find the minimum number of days in which you can visit all cities. You're also allowed to visit cities more than once, but ideally you wouldn't want to do that since you want to minimize the number of days.

输入：您将得到一系列天和城市，其中天是指数，城市是值。
A = [7,4,7,3,4,1,7]因此A [0] = 7意味着旅行社将在0天向您显示城市7，在1天向您显示城市4，等等。

Input :You're given an array of days and cities where days are indices and cities are values. A=[7,4,7,3,4,1,7] So A[0]=7 means travel agent will show you city 7 on day 0, city 4 on day 1 etc.

因此，如果您从第0天开始，那么您将在第5天访问过所有城市，但也可以从第2天开始并在第5天结束。

So Here if you start out on day 0, you'll have visited all cities by day 5, but you can also start on day 2 and finish up on day 5.

输出：4因为您花了至少4天的时间才能访问所有城市

Output:4 Because it took you 4 days to visit all the cities at least once

我的解决方案：我确实有一个O（N ^ 2）解决方案，可以尝试所有城市组合。但是测试表明理想的时间和空间复杂度应为O（N）。我该怎么做？

My solution : I do have an O(N^2) solution that tries out all combinations of cities. But the test said that the ideal time and space complexity should be O(N). How do I do this?

def findmin(A):
    hashtable1={}
    locationcount=0
    #get the number of unique locations
    for x in A:
        if A[x] not in hashtable1:
            locationcount+=1

    index1=0
    daycount=sys.maxint
    hashtable2={}
    #brute force
    while index1<len(A):
        index2=index1
        prevday=index2
        ans=0
        count1=0
        while index2<len(A):
            if A[index2] not in hashtable2:
                count1+=1
                ans+=(index2-prevday)
                hashtable2[A[index2]]=1
            index2+=1
        if count1==count:
            daycount=min(ans,daycount)
        hashtable2.clear()
        index1+=1
    return daycount+1

推荐答案

可以使用两指针方法解决此问题。

This problem might be solved with two-pointer approach.

S ome数据结构应在当前窗口中包含元素计数。也许您的哈希表是合适的。

Some data structure should contain element counts in current window. Perhaps your hash table is suitable.

设置左右指针到列表的开始。

Set left and right pointer to the start of list.

移动右指针，增加像这样的元素的表项：

Move right pointer, incrementing table entries for elements like this:

  hashtable2[A[rightindex]] = hashtable2[A[rightindex]] + 1

全部（ locationcount ）表条目变为非零，停止向右移动指针。您具有覆盖所有城市的左右间隔。记住间隔长度。

When all (locationcount) table entries become non-zero, stop moving right pointer. You have left-right interval covering all cities. Remember interval length.

现在向左移动指针，减少表项。当某些表条目变为零时，停止向左移动指针。

Now move left pointer, decrementing table entries. When some table entry becomes zero, stop moving left pointer.

再次移动右指针。重复直到列表结束。

Move right pointer again. Repeat until the list end.

请注意，索引只对列表运行一次，并且复杂度是线性的（如果表条目更新为O（1），则如哈希映射所提供）平均）

Note that indexes run the list only once, and complexity is linear (if table entry update is O(1), as hash map provides in average)

这篇关于所有城市旅行所需的最少天数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！