qwsqwa 最近的时间轴更新 qwsqwa 最近的时间轴更新 | qwsqwaV2EX 第 83092 号会员，加入于 2014-11-22 23:30:12 +08:00 |
| [北京][字节跳动]直播团队校招专属内推-实习&正式，急招，欢迎咨询 酷工作 qwsqwa 2020-04-03 11:00:56 AM 最后回复来自 qwsqwa | 2 |
| TeXstudio 如何取消全屏 设计 qwsqwa 2015-03-03 13:03:10 PM 最后回复来自 qwsqwa | 2 |
qwsqwa 最近回复了
2023-01-05 12:21:48 +08:00 回复了 Grocker 创建的主题 游戏 玩原神最正确的姿势是？ |
手机串流 PS5 （ doge ）
2020-04-03 11:00:56 +08:00 回复了 qwsqwa 创建的主题 酷工作 [北京][字节跳动]直播团队校招专属内推-实习&正式，急招，欢迎咨询 |
招
2018-03-28 13:58:20 +08:00 回复了 fov6363 创建的主题 程序员 [面试][算法] 昨天面试碰到了一个算法题,比较有难度,放上来看各位 v 友有没有办法和思路? |
@vegito2002 感觉可行，可以优化到 O(n*min(m,n))。
2018-03-28 13:35:51 +08:00 回复了 fov6363 创建的主题 程序员 [面试][算法] 昨天面试碰到了一个算法题,比较有难度,放上来看各位 v 友有没有办法和思路? |
@contmonad 修改次数就是最长递减子序列。
2018-03-28 13:21:08 +08:00 回复了 fov6363 创建的主题 程序员 [面试][算法] 昨天面试碰到了一个算法题,比较有难度,放上来看各位 v 友有没有办法和思路? |
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)
原链表为 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)，但没有用到有序这个条件。所以感觉可能会有时间复杂度更低的算法。
但又感觉没法再降低复杂度了。比如一个数正好等于数组所有数之和，则必须遍历整个数组。
但又感觉没法再降低复杂度了。比如一个数正好等于数组所有数之和，则必须遍历整个数组。
2017-05-24 22:44:12 +08:00 回复了 achilleo 创建的主题 Stack Overflow StackOverflow 骄傲地宣布：已帮助 100 万不知如何从 VIM 退出的程序员 |
@paloalto 好吧，我的错。。。
2017-05-24 22:42:48 +08:00 回复了 achilleo 创建的主题 Stack Overflow StackOverflow 骄傲地宣布：已帮助 100 万不知如何从 VIM 退出的程序员 |
@paloalto 可是文章里用的是百分比
@DT27 这个有问题，这里“-”只能出现一次。
2017-03-18 12:30:06 +08:00 回复了 boluoshu 创建的主题 程序员 说说你们面试的时候觉得最难的题。 |
Select Language