Pocket Gem 新版OA（有design）

sxhexe 发表于 2017-10-30 10:27
谢大米！我第一题是用DP做的。这题其实和house robber很像。先把数组排序，然后用house robber的办法做。 ...

求问层主，第一个如果用dp，递推方程是啥？
因为同一个元素可能有很多重复值，我觉得是不是要先用hashmap去重一下？

水浅王八多 发表于 2017-11-10 09:56
不过话说你第一题有什么思路吗？
楼主提的dp思路是可行，可是很不好做啊，因为可能一个元素有很多重复值 ...

还是用DP做，简单来说，每次循环前先把相同的元素加起来，然后做。
比如变量有四种，pre和cur，presum和cursum
pre就是前一个是多少，presum就是前一个的和（重复的）,
cur类似。
举个例子：
1,1,5,5,5,7

index为2的时候，pre为1，presum为2，cur为5，cursum为15，算完cursum的时候index已经变为4了

补充内容 (2017-11-11 00:13):
然后思路就是dp的思路，相加的时候用sum去加，比较的时候用不带sum的比较

第一题和akuna一样，参考house robber

撕勿删，第二题类似house rob

jiayi411 发表于 2017-11-11 00:12
还是用DP做，简单来说，每次循环前先把相同的元素加起来，然后做。
比如变量有四种，pre和cur，presum和 ...

清晰易懂，多谢
话说你做oa了吗

水浅王八多 发表于 2017-11-11 06:43
清晰易懂，多谢
话说你做oa了吗

昨天刚做完，我发了面经了

水浅王八多 发表于 2017-11-10 10:05
求问层主，第一个如果用dp，递推方程是啥？
因为同一个元素可能有很多重复值，我觉得是不是要先用hashm ...

你好，请问你收到 pocket gem的oa了么？求面经啊

chenzhoy 发表于 2017-11-23 16:40
你好，请问你收到 pocket gem的oa了么？求面经啊

我的两题都是地理面经里面的，两道都是dp，挺好做的。。虽然做完oa收了拒信。。

水浅王八多 发表于 2017-11-24 03:53
我的两题都是地理面经里面的，两道都是dp，挺好做的。。虽然做完oa收了拒信。。

谢谢，还想问下，design难么？昨天收到的OA，一直没敢做

楼主后来电面了嘛