小编Kel*_*ndy的帖子

许多编码挑战在同一行中有多个数字，通常第一行告诉多数字行中有多少个数字：

4
31 415 9 26

通常我只是读取整行，然后.split()将字符串映射到数字。

但是有没有一种好方法可以不一次读取整行，而是一次读取一个数字呢？为了节省内存，要么因为我不能或不想将整行读入内存。我只想使用 O(1) 空间（假设数字很小/有界，所以它们的大小是 O(1) ）。不必绝对最小，例如，如果解决方案在内部一次读取完整的 4 KB 内存页，那没关系，仍然是 O(1) 并且相对较小。对于用例，请考虑一行上有数百万个数字，并且内存限制比方说低于 1 MB。

在 C++ 中我会这样做：

4
31 415 9 26

我编写了这个生成器，它接受一个文件对象并为我提供一个字符串迭代器。对于上面的示例，它生成字符串'4'、'31'、'415'和'9'。'26'它一次读取一个字符，并按照以下确定的空格字符进行分割.isspace()：

def split(file):
    value = []
    while char := file.read(1):
        if char.isspace():
            if value:
                yield ''.join(value)
            value.clear()
        else:
            value.append(char)
    if value:
        yield ''.join(value)

但这当然是极其复杂和缓慢的，我什至不知道这种str.isspace用法是否等同于str.split空白。它只是说明了实现我想要的目标的一种方法。

编辑：这是一种更简单的方法，但仍然比我想要的更复杂和缓慢。我正在寻找一些内置的方法，以 …

我以 3 种不同的方式创建列表，并且该__sizeof__()方法为每种方式返回不同的值：

>>> l1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> print(l1.__sizeof__())
120
>>> l2 = list(i for i in range(10))
>>> print(l2.__sizeof__())
136
>>> l3 = [i for i in range(10)]
>>> print(l3.__sizeof__())
168

创建方式是否影响尺寸计算？我的假设是，数据结构应该相同。

对元组的类似测试返回相同的大小值：

>>> t1 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
>>> print(t1.__sizeof__())
104
>>>
>>> t2 = tuple(i for i in range(10))
>>> print(t2.__sizeof__())
104

我正在尝试解决这个 hackerrank 问题https://www.hackerrank.com/challenges/xor-subsequence/problem

from functools import reduce\n\ndef xor_sum(arr):\n    return reduce(lambda x,y: x^y, arr)    \n\ndef xorSubsequence(arr):\n    freq = {}\n    max_c = float("-inf") # init val\n    min_n = float("inf") # init val\n    \n    for slice_size in range(1, len(arr)+1):\n        for step in range(0, len(arr)+1-slice_size):\n            n = xor_sum(arr[i] for i in range(step,step+slice_size))\n            \n            freq[n] = freq.get(n,0)+1\n            if freq[n] >= max_c and (n < min_n or freq[n]> max_c):\n                min_n = n\n                max_c = freq[n]\n\n    return  min_n, freq[min_n]\n

但它超时了，因为它是 ~O(n^3)。\n我觉得有一些数学技巧，有人可以向我解释解决方案吗？我尝试阅读讨论中的一些解决方案，但我不太明白。

问题副本：

我遇到了以下算法问题，该问题对运行时间有严格的限制（<10s并且没有大的内存占用），我被难住了。我的方法一半的测试用例都失败了。

问题

一个盒子包含许多物品，一次只能取出 1 个或 3 个。

盒子可以有多少种方式被清空？答案可能非常大，因此将其返回为 10^9+7 的模。

例如，最初有n=7个项目。可以通过九种方式删除它们，如下所示：

1.(1,1,1,1,1,1,1)
2.(1.1.1.1.3)
3.(1,1,1,3,1)
4.(1,1,3,1,1)
5.(1,3,1,1,1)
6.(3,1,1,1,1)
7.(1,3,3)
8.(3,1,3)
9.(3,3,1)

所以该函数应该返回 9。

函数描述：您的函数必须接受一个参数，n表示项目的数量，并返回一个整数，表示清空盒子的方式数。

限制条件：1<=n<=10^8

案例示例：

Input: 1
Sample OutPut: 1
Explanation: There is only 1 way to remove 1 item. Answer=(1%1000000007)=1

Input: 7
Sample OutPut: 9
There is only 9 ways to remove 7 items

我的方法

这导致了一个标准的递归关系，其中f(n) = f(n-3) + f(n-1)n > 2，所以我这样做如下

def memoized_number_of_ways(dic, n):
    if n not in dic:
        dic[n] = memoized_number_of_ways(dic, n-3) …

我正在寻找一个将坐标存储为复数的 Advent of Code 谜题的解决方案：

 heightmap = {
    complex(x, y): c
        for y, ln in enumerate(sys.stdin.read().strip().split("\n"))
        for x, c in enumerate(ln)
}

然后稍后访问它们，如下所示：

for xy, c in heightmap.items():
    for d in (1, -1, 1j, -1j):
        if ord(heightmap.get(xy + d, "{")) <= ord(c) + 1:
            G.add_edge(xy, xy + d)

我可以看到这段代码使“获取邻居”行易于编写/思考，但我不认为值得增加复杂性（没有双关语）。

有人可以解释为什么将网格坐标存储为复数很有用吗？

（摘自另一个问题。）像这样逐个删除该集合的 200,000 个元素需要 30 秒（在线尝试！）：

s = set(range(200000))
while s:
    for x in s:
        s.remove(x)
        break

为什么这么慢？删除集合元素应该很快。

给定一个数组，我应该在线性时间内计算以下总和：

我最幼稚的实现是 O(n ³ )：

sum_ = 0

for i in range(n):
    for j in range(n, i, -1):
        sum_ += max(arr[i:j]) * (j-i)

我不知道该怎么做。我尝试过很多算法，但它们最多是 O(n*log(n))，但我应该在线性时间内解决它。另外，我不明白，是否有一种数学方法可以只查看数组并告诉上面总和的结果？