主页 / 问题 / 1283936
Accepted
bdc1
Asked:2022-05-20 03:48:42 +0000 UTC2022-05-20 03:48:42 +0000 UTC

python中的算法任务

  • 772

大家好！最近我开始研究 Python 中的算法问题，遇到了一个我无法以任何方式解决的问题。我请求你的帮助（如果不难，你可以有更多的解释）：

Timofey 想要居住的街道长度为 n，也就是说，它由 n 个相同的连续路段组成。要么已经在每个地块上建造了房子，要么地块是空的。Timofey 正在寻找一个地方来建造他的房子。他非常善于交际，不想离住在这条街上的其他人太远。为了最佳地选择施工地点，Timofey 想知道每个地块到最近的空地的距离。（对于空白区域，此值将等于零 - 到自身的距离）。你的任务是帮助蒂莫西计算所需的距离。为此，您有一张街道地图。提摩太城的房屋是按照建造顺序编号的，所以地图上的编号并没有以任何方式排列。空白区域用零标记。

输入格式 第一行包含街道的长度——n (1 ≤ n ≤ 106)。下一行包含 n 个非负整数——房屋数量和地图上空地的名称（零）。保证序列中至少有一个零。门牌号（正数）是唯一的，不超过 109。

输出格式 对于每个段，输出到最接近零的距离。在一行上输出数字，用空格分隔。

示例 1：

输入：

5

0 1 4 9 0

结论：

0 1 2 1 0

示例 2：

输入：

6

0 7 9 4 8 20

结论：

0 1 2 3 4 5

蟒蛇 | 时间限制：3 秒 | 内存限制：256 MB

根据我的猜测，我们需要找到左边最近的地段的距离，然后对于右边最近的地段，下一步：最近的空房子要么是最近的左边，要么是最近的右边。

编码：

n = int(input())
numbers = input().split()
for i in range(n):
    if numbers[i] != '0':
        l = 10**6
        for a in range(n):
            if numbers[i - a] == '0':
                if a <= i and l > a:
                    l = a
                if a > i and l > n - a:
                    l = n - a
            numbers[i] = l
print(*numbers)
python

2 个回答

  1. Best Answer

    您的算法适用于网站数量的平方。你需要一个线性算法。

    计算左边到零的距离。始终如一地做到这一点很容易。如果在上一节中距离是d，那么在下一节中它将是d + 1或零。我们在序列的开头写入大数，直到第一个零。

    右边到零的距离也是计算出来的，只需要翻转部分的序列，然后翻转结果。

    从两个序列中，我们逐个元素地取最小元素。

    准备好：

    def zero_dists(start, seq):
    d = start
    for n in seq:
        if n == '0':
            d = 0
        else:
            d += 1
        yield d


input()
numbers = input().split()

to_left = zero_dists(len(numbers), numbers)
to_right = reversed(tuple(zero_dists(len(numbers), reversed(numbers))))

print(*map(min, zip(to_left, to_right)))

    $ echo -e "5\n0 1 4 9 0" | python nearest_zeros_2.py 
0 1 2 1 0

$ echo -e "6\n0 7 9 4 8 20" | python nearest_zeros_2.py 
0 1 2 3 4 5
    • 2

  2. 这个问题可以在线性时间内用两个额外的数组来解决。

    例如，如果您首先从左到右，并将最接近的零的值存储在数组 1 中。

    然后从右到左，将最靠近右边的零的值存储在数组 2 中。

    然后，在结果数组中，取前两个中的最小值。

    C# 中的示例代码

    int[] GetDisctance(int[] input)
{
    var ltor = new int[input.Length];
    var rtol = new int[input.Length];
    var result = new int[input.Length];

    for (int i = 0; i < input.Length; i++)
    {
        ltor[i] = input[i] == 0 ? 0 : input.Length;
        rtol[i] = input[i] == 0 ? 0 : input.Length;
    }   

    for (int i = 1; i < input.Length; i++)
        ltor[i] = input[i] == 0 ? 0 : ltor[i - 1] + 1;

    for (int i = input.Length - 2; i >= 0; i--)
        rtol[i] = input[i] == 0 ? 0 : rtol[i + 1] + 1;

    for (int i = 0; i < input.Length; i++)
        result[i] = Math.Min(ltor[i], rtol[i]);

    return result;
}

    在此处输入图像描述

    您也可以这样做，但只需要 1 个额外的数组。如果我们可以在输入端改变数组，那么我们就可以完全不用额外的数组。例子

    int[] GetDisctance(int[] input)
{       
    for(int i=0; i<input.Length; i++)   
        if (input[i] != 0) input[i] = input.Length;
        
    for(int i=1; i<input.Length; i++)
        input[i] = input[i] == 0 ? 0 : input[i-1]+1;

    for (int i = input.Length-2; i > 0; i--)
        input[i] = input[i] == 0 ? 0 : Math.Min(input[i + 1] + 1, input[i]);
        
    return input;
}

    在此处输入图像描述

    • 1

相关问题