我的遞歸實現有什麼問題？

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))