Python代码2020第9天的到来

Question

这是“2020年守则”的出现第9天第1&2部分的解决方案。

给定示例输入sample.txt：

35
20
15
25
47
40
62
55
65
95
102
117
150
182
127
219
299
277
309
576

第1部分:查找列表中的第一个数字(在序言之后)，它不是前面n个数字中的两个之和。N是序言。

例如，在5-数字前导之后，几乎每个数字都是前5个数字中的两个之和；唯一不遵循这一规则的数字是127。

第2部分:在列表中找到至少两个数字的连续集合，该集合与第1部分中的无效数字相加。

例如，在这个列表中，将15到40之间的所有数字相加会产生第1,127部分中的无效数字。将这个连续范围中最小和最大的数字相加在一起；在本例中，它们是15和47，产生62。

码

def not_in_preamble(nums, preamble):
    diff = set()
    for i in range(preamble, len(nums)):
        current = nums[i]
        found = False
        for j in range(i - preamble, i):
            if nums[j] in diff:
                found = True
                break
            diff.add(current - nums[j])
        if not found:
            return current
        diff.clear()


def sub_array_with_sum(nums, n):
    i, j = 0, 1
    partial_sum = nums[i] + nums[j]
    while j < len(nums):
        if partial_sum == n:
            return nums[i: j + 1]
        if partial_sum < n or i == j - 1:
            j += 1
            partial_sum += nums[j]
        else:
            partial_sum -= nums[i]
            i += 1


# Part 1
preamble = 5
with open('sample.txt') as f:
    nums = [int(l) for l in f.read().splitlines()]
pt1_result = not_in_preamble(nums, preamble)
print(f'PT 1 result: {pt1_result}')

# Part 2
n = pt1_result
sub_array = sub_array_with_sum(nums, n)
print(f'PT 2 result {min(sub_array) + max(sub_array)}')

守则输出：

PT 1 result: 127
PT 2 result 62

这是样本输入的正确结果。

将sample.txt更改为拼图输入并设置preamble=25，将为挑战提供正确的结果。

代码能变得更紧凑和高效吗？欢迎任何其他反馈或替代解决方案。

Answer 1

第1部分

对于not_in_preamble，我将使用一个for-else而不是您的found变量，而不是重复使用相同的集合(我认为这不值得)：

def not_in_preamble(nums, preamble):
    for i in range(preamble, len(nums)):
        current = nums[i]
        diff = set()
        for j in range(i - preamble, i):
            if nums[j] in diff:
                break
            diff.add(current - nums[j])
        else:
            return current

由于您的“任何其他反馈或替代解决方案都是受欢迎的”也允许效率较低的解决方案，下面是我如何亲自解决这个问题:-)

from itertools import combinations

def not_in_preamble(nums, preamble):
    for i in range(preamble, len(nums)):
        if nums[i] not in map(sum, combinations(nums[i-preamble : i], 2)):
            return nums[i]

前导尺寸25和nums大小1000很容易小到足以快速运行。

第2部分

您的sub_array_with_sum很好，尽管它确实依赖于输入是非负数，这在问题语句中没有保证(但是对于固定的输入文件是这样的)。

我只想和PEP 8一起去，把nums[i: j + 1]换成nums[i : j + 1]或nums[i : j+1]。也许我会和while True:一起去，依靠答案的存在。

您的算法几乎只占用O(1)空间。它占用更多的唯一原因是复制子数组(或者更确切地说，子列表，因为这是Python，问题从来没有说“数组”，所以真的没有必要调用它数组)。可以在O(1)空间中进行，使算法不仅具有时间最优(O(n))，而且具有空间最优性。虽然这需要更多的代码，但不值得(除非你有一个坚持的面试官)。

输入

我会将[int(l) for l in f.read().splitlines()]改为list(map(int, f))，或者至少改为[int(line) for line in f]。

输出

我会改变

print(f'PT 1 result: {pt1_result}') to

print('PT 1 result:', pt1_result)。稍微短一点，它在早期版本的Python中工作。至少在空闲状态下，f-字符串只被格式化为string，整件事都是绿色的，包括变量。我不喜欢那样。