V2EX qwsqwa 的所有回复第 1 页 / 共 2 页

DP：
原链表为 a ；
dp[n][m]，表示前 n 个数最小值大于等于 m 时需要的最小△值。
'''
def f(a):
ma = max(a)
dp = [[0] * (ma + 1) + [float("inf")] for _ in range(len(a) + 1)]

for i in range(1, len(a) + 1):
for j in range(ma, -1, -1):
dp[i][j] = min(dp[i][j + 1], dp[i - 1][j] + abs(a[i - 1] - j))

return dp[len(a)][0]
'''
时间复杂度 O(n*m)

2018 年 3 月 26 日

回复了 gbin 创建的主题算法 2018026 今日算法

这道题基本算法就是双指针，复杂度 O(n)，但没有用到有序这个条件。所以感觉可能会有时间复杂度更低的算法。
但又感觉没法再降低复杂度了。比如一个数正好等于数组所有数之和，则必须遍历整个数组。

2017 年 5 月 24 日

回复了 achilleo 创建的主题 Stack Overflow StackOverflow 骄傲地宣布：已帮助 100 万不知如何从 VIM 退出的程序员

@paloalto 好吧，我的错。。。

2017 年 5 月 24 日

回复了 achilleo 创建的主题 Stack Overflow StackOverflow 骄傲地宣布：已帮助 100 万不知如何从 VIM 退出的程序员

@paloalto 可是文章里用的是百分比

2017 年 4 月 13 日

回复了 dadazhang 创建的主题问与答求正则表达式！！！

@DT27 这个有问题，这里“-”只能出现一次。

2017 年 3 月 18 日

回复了 boluoshu 创建的主题程序员说说你们面试的时候觉得最难的题。

https://zh.m.wikipedia.org/zh-hans/梅森素数

2016 年 12 月 26 日

回复了 lxiange 创建的主题程序员来看看这个函数的时间复杂度是多少

伪多项式时间： https://zh.wikipedia.org/wiki/%E4%BC%AA%E5%A4%9A%E9%A1%B9%E5%BC%8F%E6%97%B6%E9%97%B4

2016 年 1 月 16 日

回复了 TonySheva 创建的主题职场话题老大让我回去了解市场价，然后下周给他报期望薪资

我现在也在实习，不过正式工资已经定了。当时是直接发来的 offer ，没有谈薪资，感觉少了点，不过还好。我觉得既然是谈工资就一定往你想要的说，不行再降，否则以后肯定会后悔的。

2016 年 1 月 16 日

回复了 TonySheva 创建的主题职场话题老大让我回去了解市场价，然后下周给他报期望薪资

2015 年 11 月 25 日

回复了 KenGe 创建的主题问与答今天的百度云 1 一分钱 bug 你买了多少年？

@Vicer @KenGe 上个月买的，现在已经找不到了，好像涨价了，不好意思。

2015 年 11 月 25 日

回复了 KenGe 创建的主题问与答今天的百度云 1 一分钱 bug 你买了多少年？

@KenGe 淘宝有 50 多一年的，你可以看看。

2015 年 10 月 8 日

回复了 luoway 创建的主题程序员循环调用的函数，将函数变量声明提升到全局以缓存，是否能提高性能？

java 和 C#中好像也有，其他语言就不清楚了。

2015 年 10 月 8 日

回复了 luoway 创建的主题程序员循环调用的函数，将函数变量声明提升到全局以缓存，是否能提高性能？

C/C++中有静态局部变量， static 关键字。静态局部变量保存在全局数据区，而不是保存在栈中，每次的值保持到下一次调用，直到下次赋新值。

2015 年 7 月 20 日

回复了 meteor2013 创建的主题程序员用什么算法，最快算出两个时间段的重叠部分呢

@yuankui 是正解。
楼主给的数据不是时间段，是时间点，只是几个时间点连起来就是时间段了。
如果给的是若干时间段，比如原问题中
A： 3,4,5, 7,8,910, 18,19
B: 4,5, 16,17,18,19,20
写成
A：3,5,7,10,18,19
B：4,5,16,20
的话才会用到线段树。

2015 年 6 月 11 日

回复了 judgingwoo 创建的主题分享发现蛮有意思的解谜网站，你能玩到第几关？

@zrw93 搜一下QQ号

1 2