由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 询问cracking the coding interview上面一道题
相关主题
请教一个cracking coding interview书上的问题关于DP的问题
Longest Increasing Subsequence O(NLOG(N)) 解法Cracking上一道题求教
g公司面试问Longest increasing subsequence,意义在哪里?准备面试准备的很郁闷
数组里找最大集合,该集合排序后是序列,有漂亮解法么?如果面试主要就是algo+ coding
Longest Increasing Subsequence要掌握nlogn的解法吗?T家要人, 有没有兴趣?
关于什么时候可以用贪心算法求找零问题大家帮我分析一下问题在哪?
数独有啥好解法?难道stanford, CMU之类毕业的PHD去这几大公司也要过做题这关?
Crack the coding interview 是不是就是新版的 careercup 150?请版上大牛推荐类似LeetCode的网站
相关话题的讨论汇总
话题: cracking话题: 道题话题: dp话题: coding话题: 解法
进入JobHunting版参与讨论
1 (共1页)
r*******g
发帖数: 1335
1
9.7题,是不是它的解法有问题,step2明显应该用dp,他怎么就那么草率的找unfit
item?
谢了
l*********8
发帖数: 4642
2
你转帖一下题目和解答,可能会有更多人回复你。

【在 r*******g 的大作中提到】
: 9.7题,是不是它的解法有问题,step2明显应该用dp,他怎么就那么草率的找unfit
: item?
: 谢了

P**********c
发帖数: 3417
3
书上的解法是O(n^2)吧。DP比它快么?

【在 r*******g 的大作中提到】
: 9.7题,是不是它的解法有问题,step2明显应该用dp,他怎么就那么草率的找unfit
: item?
: 谢了

r*******g
发帖数: 1335
4
题目见此:
http://stackoverflow.com/questions/4424586/find-the-largest-pos
http://stackoverflow.com/questions/6893041/dynamic-programming-
书上的解法可能得到的不是最长的,比如第二个链接里面有人指出来了。

【在 P**********c 的大作中提到】
: 书上的解法是O(n^2)吧。DP比它快么?
d****z
发帖数: 53
5
这个应该用贪心就能得到最优解, 比如如果先用weight排序,然后做hight的时候先找
height最低,然后次低,然后。。。
证明跟introduction to algo书上,task scheduling的那个例子应该类似

【在 r*******g 的大作中提到】
: 9.7题,是不是它的解法有问题,step2明显应该用dp,他怎么就那么草率的找unfit
: item?
: 谢了

r*******g
发帖数: 1335
6
贪心不一定最优吧,假设先weight排序好,我们只看height,假设如下的hight
1,2,3,6,5,5.5,5.8
这个用贪心怎么求?明显结果是可选6个,但是如果简单把5设为unfit然后重新开始就
有问题。

【在 d****z 的大作中提到】
: 这个应该用贪心就能得到最优解, 比如如果先用weight排序,然后做hight的时候先找
: height最低,然后次低,然后。。。
: 证明跟introduction to algo书上,task scheduling的那个例子应该类似

x****1
发帖数: 118
7
我也和你想法一样,当时觉得有问题,跳过这道题了。

【在 r*******g 的大作中提到】
: 9.7题,是不是它的解法有问题,step2明显应该用dp,他怎么就那么草率的找unfit
: item?
: 谢了

P**********c
发帖数: 3417
8
恩,貌似是有问题。DP解法是longest increasing subsequence吗?

【在 r*******g 的大作中提到】
: 贪心不一定最优吧,假设先weight排序好,我们只看height,假设如下的hight
: 1,2,3,6,5,5.5,5.8
: 这个用贪心怎么求?明显结果是可选6个,但是如果简单把5设为unfit然后重新开始就
: 有问题。

1 (共1页)
进入JobHunting版参与讨论
相关主题
请版上大牛推荐类似LeetCode的网站Longest Increasing Subsequence要掌握nlogn的解法吗?
找cs工作总结关于什么时候可以用贪心算法求找零问题
L 家第二轮电面考什么?数独有啥好解法?
报个上周L家的onsite,已挂。继续为第6个onsite准备Crack the coding interview 是不是就是新版的 careercup 150?
请教一个cracking coding interview书上的问题关于DP的问题
Longest Increasing Subsequence O(NLOG(N)) 解法Cracking上一道题求教
g公司面试问Longest increasing subsequence,意义在哪里?准备面试准备的很郁闷
数组里找最大集合,该集合排序后是序列,有漂亮解法么?如果面试主要就是algo+ coding
相关话题的讨论汇总
话题: cracking话题: 道题话题: dp话题: coding话题: 解法