小编Kel*_*ndy的帖子

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

我最幼稚的实现是 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))，但我应该在线性时间内解决它。另外，我不明白，是否有一种数学方法可以只查看数组并告诉上面总和的结果？

约束：

1 \xe2\x89\xa4 \xe2\x89\xa4 \xe2\x89\xa4 10^1000000

输入：

1000211 1000299\n

输出：

2000510\n

运行时间必须小于 4 秒。

我已经尝试过了，但还是太慢：

x, y = input().split()\nprint(int(x) + int(y))\n

它是一个算法编码：x = a^2 + b^2，a,b 为正整数。求 f(n)，第 n 个最小的 x。

我们知道 f(1) = 1^2 + 1^2；f(2) = 1^2 + 2^2; f(3) = 2^2 + 2^2....

我的想法是通过比较 (a+1)^2 + b^2 与 a^2 + (b+1)^2 来更新 a,b。但事实并非如此，f(4) = 1^2 + 3^3，它不是从 2^2 + 2^2 更新的。

我们能找到一种比暴力枚举（O(n^2)）更好的算法吗？

寻找使用 3 个 python 列表创建字典的帮助

a = ['alpha','bravo','charlie']
b = ['a','b','c']
c = [1,2,3]

output:
{'alpha': {'letter': 'a', 'number': 1},
 'bravo': {'letter': 'b', 'number': 2},
 'charlie': {'letter': 'c', 'number': 3}}

我尝试过这样的事情。这可能很接近，但需要一些调整：

{k: dict(v) for k,v in zip(a, zip(('letter', b),('number', c)))}

我正在尝试移动列表中的元素，以便前两个元素始终以相反的顺序附加到最后一个元素，直到列表与我开始使用的列表相同。例如对于

l = [1,2,3,4,5]

我应该得到

[1,2,3,4,5]
[3,4,5,2,1]
[5,2,1,4,3]
[1,4,3,2,5]
[3,2,5,4,1]
[5,4,1,2,3]
[1,2,3,4,5]

所以六次迭代就可以了。

目前我有以下代码

[1,2,3,4,5]
[3,4,5,2,1]
[5,2,1,4,3]
[1,4,3,2,5]
[3,2,5,4,1]
[5,4,1,2,3]
[1,2,3,4,5]

我试图做的是循环两个连续的元素并弹出它们并以相反的顺序将它们作为列表中的最后两个附加到它们。这似乎不起作用，因为在每个步骤返回打印列表

l = [1,2,3,4,5] 
for i, j in zip(l, l[1:]): 
   l.append(l.pop(l.index(j)))  
   l.append(l.pop(l.index(i))) 

所以只有第一次迭代似乎有效。我应该在这里修改什么？

使用r = range(1500, 2500)，我x in r对x低于/在/高于范围进行了基准测试：

1000 in r :   58 ns \xc2\xb1 0 ns\n2000 in r :  101 ns \xc2\xb1 1 ns\n3000 in r :   58 ns \xc2\xb1 0 ns\n

检查1000比检查2000快？这是有道理的，对于 1000，Python 仅在检查范围的下限后就知道结果，而对于 2000，它需要检查两个边界。

检查3000比检查2000快？这是有道理的，对于 3000，Python 仅在检查范围的上限后就知道结果，而对于 2000，它需要检查两个边界。

嘿...等一下...

它如何知道首先检查哪个边界？1000和3000怎么能比2000检查得快呢？

基准代码（在线尝试！）：

from timeit import repeat\nfrom statistics import mean, stdev\n\nsetup = \'r = range(1500, 2500)\'\n\nn …

假设您想要处理 0 到 n-1 的所有数字对，例如n = 4这六对：

[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]\n

创建这些对的三种方法：

list(combinations(range(n), 2))\n\n[(i, j) for i, j in combinations(range(n), 2)]\n\n[(i, j) for i in range(n) for j in range(i+1, n)]\n

基准测试结果n = 1000：

44.1 ms \xc2\xb1 0.2 ms  f_combinations_pure\n57.7 ms \xc2\xb1 0.3 ms  f_combinations\n66.6 ms \xc2\xb1 0.1 ms  f_ranges\n

请注意，我对仅存储对并不真正感兴趣(i, j)。这只是i和的一个最小示例用法j，以便我们可以比较不同的方法而无需太多开销。实际上，您想要使用和做一些事情，例如获取子字符串（ …

我正在尝试解决 Leetcode 上的“二的幂”问题。

我的想法是，要使 n>=2 成为 2 的幂，2 必须整除 n，并且 n 不能被任何素数 2<= p<= sqrt(n) 整除。因此，首先检查 n 是否能被 2 整除，如果不能，则它不是 2 的幂。如果可整除，找到素数 2<= p<= sqrt(n) 并检查其中是否有一个能整除 n，如果至少有一个能整除，则它不是 2 的幂，如果没有则 n 是一个幂两个。

这是我的代码。

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n == 1:
            return True
        else:
            if n % 2 != 0:
                return False
            else:
                for i in range(3, round(math.sqrt(n)) + 1):
                    for j in range(2, round(math.sqrt(i)) + 1):
                        if i % j == 0:
                            break
                        else:
                            continue
                    if …

我有一个购物清单：

items = [\n    [\'Aspirin\', \'Walgreens\', 6.00],\n    [\'book lamp\', \'Amazon\', 2.87],\n    [\'popsicles\', \'Walmart\', 5.64],\n    [\'hair brush\', \'Amazon\', 6.58],\n    [\'Listerine\', \'Walmart\', 3.95],\n    [\'gift bag\', \'Target\', 1.50]\n]\n

我想将商品从最便宜到最高的价格排序，并删除价格。（那么我就不再需要它们了，我会从上到下购买，直到我用完钱为止）。目标是：

items = [\n    [\'gift bag\', \'Target\'],\n    [\'book lamp\', \'Amazon\'],\n    [\'Listerine\', \'Walmart\'],\n    [\'popsicles\', \'Walmart\'],\n    [\'Aspirin\', \'Walgreens\'],\n    [\'hair brush\', \'Amazon\']\n]\n

一种有效但看起来笨拙的方法（demo/template）：

import operator\nitems = sorted(items, key=operator.itemgetter(2))\nfor i in range(len(items)):\n    items[i] = items[i][:2]\n

有更短的路吗？