arrays - Python代码查找其总和与特定值匹配的最小行数

Question

我正在参加一个代码挑战测试，该测试需要编写一个函数，该函数返回用于照亮多条街道的最少交通信号灯数量。

街道编号表示为一条直线，范围为 0:n，其中可以在 n 的任何位置添加灯光，以及一个称为灯光的二维数组，表示灯光的位置及其强度，强度定义范围光（将是左右）[位置+强度，位置-强度]，例如。[3,5] 灯位于位置 3，可点亮范围为 (-2 : 8 )。我们需要检查照亮整个街道所需的最小灯并将其返回，如果不可能，则返回 -1

例子

n=10 , lights= [[0,5],[1,3],[5,4],[8,3]]

result=2 因为 [0,5] & [8,3] 可以匹配条件。

我的问题

现在我需要帮助如何在数组上循环并找到它们的联合达到特定条件的最小行数[范围（0，n + 1），我需要一个循环来尝试单行然后如果条件不是匹配然后尝试每 2 行的并集，如果不匹配则尝试每三行的并集，直到最大限制为 no。数组中的行数，如果条件匹配则返回匹配条件所需的最小行数，如果条件不满足则返回 -1 注意：我需要知道如何执行循环，我可以编写代码但是我并没有想到通用方程的想法

详细示例

Array =[[0,4],[0,5],[5,10],[1,9]] n=10 

那么范围将是 (0:11) 将是 [0:10]

1. 检查行 (0,1,2,3) 如果它们中的任何一个可以覆盖整个范围，则返回 1
2. 如果上面不匹配，检查行 [[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]] 的并集，如果有的话它们覆盖了整个范围，然后返回 2
3. 如果以上不匹配，请检查数组中 3 行 [[0,1,2],[0,1,3],[1,2,3]] 的行的并集
4. 如果所有条件都不匹配，则返回 -1

我试图编写一个代码，但我找不到一种方法如何使它简单和递归，我的方法是使用 for 循环进行第一次迭代，然后使用 2 个 for 循环进行迭代 2，然后使用 3 个循环，依此类推，效率不高如果矩阵尺寸很大，则不可能

# check if only 1 light can light up all the streets 
for i in range (arr2.shape[0]):
    for j in range (arr2.shape[1]-1):
        lights_up=[0,0,0,0,0,0,0,0,0,0,0]
        for z in range (arr2[i][j], arr2[i][j+1]+1):
            print 'z= ',z
            lights_up[z]=1
        print ("iteration_",i,j,lights_up)  
        if lights_up==[1,1,1,1,1,1,1,1,1,1,1]:
            Min_lights=1
            print lights_up  # to be hashed
            break
    if Min_lights != -1:
        break 
    
print Min_lights
#check if 2 light can ligh up 

标签： arrayspython-3.x

Answer 1

我的初步做法如下：

注意：我使用 numpy 数组来保存覆盖图，因为它使按 cols 对一组行进行切片更容易。

import numpy as np
def minLights(n: int, l : list) -> int:
    # Create a street coverage map for each light
    cm = []
    for i, v in enumerate(l):
        k = [False] * n
        k[v[0]] = True
        for x in range(-v[1], v[1]+1):
            if v[0] + x >= 0 and v[0] + x < n:
                k[v[0] + x] = True                    
        cm.append(k)
    cm = np.array(cm)
    cnt = 0
    # Walk coverage map looking for a combination covering all
    while cnt < len(l):
        for row in range(len(l)):
            covered = True
            for col in range(n):
                # Testing for all False Coverage in Col
                if not cm[row:row+cnt+1, col].any():
                    covered = False 
                    break
            if covered:
                return cnt +1
        cnt += 1
    return -1        

在对初始方法进行了一些更广泛的测试后，我发现在最佳解决方案涉及非序列灯的情况下，该方法无法确定最佳解决方案。这促使创建了下面的第二种方法，该方法使用优先级队列来保存增量解决方案。优先权重被选择为未覆盖的街道段数 * 使用的灯数。该解决方案如下：

改进的解决方案

import heapq as hq

class Coverage:
    def __init__(self, n, rw, lt):
        self.n = n
        self.map = buildCoverage(self.n, lt)     
        self.includes = {rw}
        self.w = len(self.includes)*self.map.count(False)
        
    def add(self, rw, lt):
        if rw not in self.includes:
            lmap = buildCoverage(self.n, lt)
            self.merge(lmap)
            self.includes.add(rw)
            self.w = len(self.includes)* self.map.count(False)
            return self.weight
        return -1
    
    def merge(self, ltmap):
        for i in range(len(self.map)):
            if ltmap[i] or self.map[i]:
                self.map[i] = True
    
    @property
    def weight(self):
        return self.w
    
    @property
    def solution(self):
        return len(self.includes)
    
    def __lt__(self, other):
        return self.weight < other.weight
      
def buildCoverage(n, lt):
    rslt = [False]*n
    rslt[lt[0]] = True
    for x in range(-lt[1], lt[1] +1):
        if lt[0] + x >= 0 and lt[0] + x < n:
            rslt[lt[0] + x ] = True
    return rslt

def minLightsq(n: int, l : list) -> int:
    q = []
    for rw, lt in enumerate(l):
        nd = Coverage(n, rw, lt)
        #q.append((nd.weight, nd))
        hq.heappush(q,  nd)

    while len(q) > 0:
        # q = sorted(q, key= lambda x: x[0], reverse= True)
        # nd = q.pop()[1]
        nd = hq.heappop(q)
        if nd.weight == 0:
            return nd.solution
        for rw, lt in enumerate(l):
            w = nd.add(rw, lt)
            if w >= 0:
                if w == 0:
                    return len(nd.includes)
                #q.append((w, nd))
                hq.heappush(q, nd)
    return -1