qwsqwa 最近的时间轴更新
qwsqwa

qwsqwa

V2EX 第 83092 号会员,加入于 2014-11-22 23:30:12 +08:00
qwsqwa 最近回复了
@vegito2002 感觉可行,可以优化到 O(n*min(m,n))。
@contmonad 修改次数就是最长递减子序列。
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-03-26 10:36:56 +08:00
回复了 gbin 创建的主题 算法 2018026 今日算法
这道题基本算法就是双指针,复杂度 O(n),但没有用到有序这个条件。所以感觉可能会有时间复杂度更低的算法。
但又感觉没法再降低复杂度了。比如一个数正好等于数组所有数之和,则必须遍历整个数组。
@paloalto 好吧,我的错。。。
@paloalto 可是文章里用的是百分比
2017-04-13 13:54:31 +08:00
回复了 dadazhang 创建的主题 问与答 求正则表达式!!!
@DT27 这个有问题,这里“-”只能出现一次。
2017-03-18 12:30:06 +08:00
回复了 boluoshu 创建的主题 程序员 说说你们面试的时候觉得最难的题。
2016-12-26 12:46:37 +08:00
回复了 lxiange 创建的主题 程序员 来看看这个函数的时间复杂度是多少
关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1898 人在线   最高记录 5497   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 26ms · UTC 15:59 · PVG 23:59 · LAX 08:59 · JFK 11:59
Developed with CodeLauncher
♥ Do have faith in what you're doing.