我的递归实现有什么问题？

Question

我最近开始学习编程，刚刚完成了edX课程。我正试图解决HackerRank上的this问题，并且在每种情况下都耗尽了时间。我究竟做错了什么？

n,k = input().strip().split(' ') 
n,k = [int(n),int(k)] 
x = [int(x_temp) for x_temp in input().strip().split(' ')] 
x.sort() 
def transmitter(aList=[], target=0): 
    ''' 
    accepts a list of house location, and a target location for the transmitter 
    returns the optimal number of transmitters required to cover all the houses 
    ''' 
    List = aList[:] 
    start = target - k 
    end = target + k + 1 

    for i in range(start, end): 
     if i in List: 
      List.remove(i) 
    if not List: 
     return 1 
    m = max(List) 
    for e in List: 
     if transmitter(List, e) < m: 
      m = transmitter(List, e) 

    return 1 + m 

m = max(x) 
for e in x: 
    if transmitter(x, e) < m: 
     m = transmitter(x, e) 

print(m) 

我对此很新颖。对不起，有任何明显的错误，或在这里发布这里，以防这不适合的网站。在这种情况下，如果你能推荐一个我可以问这样的问题的网站，这将会非常有帮助。

the screenshot of the question

Answer 1

我敢肯定贪心算法在短短O(N)最佳时间解决了这个问题。不需要任何递归。只要将每台发射器依次放置在最右侧，而不会在左侧露出任何房屋。当最后一栋房屋被遮盖时停止。

以下是我想代码：

def hackerland(houses, k): # houses should be sorted list of locations 
    first = None # location of first uncovered house 
    last = 0  # last location covered by a previous transmitter 
    prev = None 
    count = 0 # transmitters = [] 

    for x in houses: 
     if first is not None and x > first + k: 
      first = None 
      count += 1 # transmitters.append(prev) 
      last = prev + k 

     if last is not None and x > last: 
      last = None 
      first = x 

     prev = x 

    if first is not None: 
     count += 1 # transmitters.append(prev) 

    return count # return transmitters 

我已经包括注释说明如何这段代码可以很容易地修改，以返回发射位置的列表，而不是有多少的计数是必要的。

Answer 2

没有必要采用递归方法。事实上，你可以继续前进，迭代房屋，放置发射器时，先前放置的发射器没有达到足够的覆盖当前的房子等。

这是比这更复杂一点，但并不多。看到这个代码：

# input 
n,k = input().strip().split(' ') 
n,k = [int(n),int(k)] 
x = [int(x_temp) for x_temp in input().strip().split(' ')] 

# eliminate duplicate house x-xoordinates, they don't influence the result 
houses = list(set(x)) 
houses.sort() 
# add extreme far dummy house (will make the loop easier) 
houses.append(100000) 
reachedX = 0 # coordinate until where the previously placed transmitter reaches 
unreachedX = -1 # coordinate that the next one needs to cover (to the left) 
lastHouseId = -1 # index where previous transmitter was placed 
transmitters = [] # coordinates of the placed transmitters 
for houseId, houseX in enumerate(houses): 
    if reachedX > unreachedX: # we might still be in range of last transmitter 
     if houseX > reachedX: # we just went out of reach 
      unreachedX = houseX # this house must be covered by next one 
    elif houseX - k > unreachedX: # transmitter here wouldn't reach far enough back 
     lastHouseId = houseId - 1 # place it on previous house 
     reachedX = houses[lastHouseId] + k 
     transmitters.append(houses[lastHouseId]) 

print(transmitters) 
print(len(transmitters))