新鲜谷歌Onsite面经

Josh 发表于 2016-9-9 12:59
记得之前面经见过一道题跟楼主第二题很像：给n堆硬币，每次只能从堆顶拿一枚，问拿k个硬币最大数额是多少。 ...

求解。。能想到用记忆化搜索来剪枝，但复杂度不会分析

Josh 发表于 2016-9-9 12:59
记得之前面经见过一道题跟楼主第二题很像：给n堆硬币，每次只能从堆顶拿一枚，问拿k个硬币最大数额是多少。 ...

在哪里看到的？

diff那个是类似于edit distance吗

superbeet 发表于 2016-9-9 13:59
在哪里看到的？

http://www.1point3acres.com/bbs/ ... read&tid=189741

第一题

火火火bit 发表于 2016-9-9 13:51
求解。。能想到用记忆化搜索来剪枝，但复杂度不会分析

你的记忆化搜索打算纪录哪些状态呢？

有坛友了解碰到"面试官迟到很久面试很仓促"这种情况，应该怎么处理呢？

mingzhou1987 发表于 2016-9-9 13:44
贪心应该不行吧，假设某个stack底有一个超大的数，顶端是一个超小的数，不是永远选不到这个。

你说的没错。关键是这个“使取出的值总和最大”怎么理解。因为STL API对于stack只提供查询top的值，在没有pop之前永远不知道地下的元素值。所以我对这道题的假设是提前不能知道除stack top之外的元素值。那么在没有额外信息的条件下就只有贪心算法了。
事实上，可以很容易举反例说明无论怎么pop都不可能保证取出的值总和最大。例如N=2，每个stack只有2个元素，所有top元素都是1, 但只有一个stack底的元素很大。理论上pop的最优方式是就pop光这个stack的2个元素，但初始状态下无法确定这个stack在array中的哪一个。

楼主可以再具体澄清一下“N次操作后能拿到的数字和最大是多少” 是怎么定义的吗？在初始状态下我们是否可以知道每个stack中所有元素的值？还是只能通过stack::peek只知道顶端的值？

dp啦
dp[i][j]表示前i个栈取j个数字的最大值
显然dp[i][j] = max{dp[i-1][k] + sum[i][0..(j-k-1)]}
边界条件就是dp[0][j] = 0

OK. I see. 用DP就相当于可以不断地用前i个stack用不同的pop方式来查看stack top下面的若干值，而且可以将pop出来的元素再push回去复原，之前计算dp[i][j]用的pop不计入最终的N次操着（这样的确是可以保证策划出最大总和的）。我以为是面对M个stack就一共只给N次pop的机会，一旦用过不可以后悔（这样是不可能0风险的）。如果的这样的话可以用array重新叙述题目更清楚：给一个vector<vector<int>> arr, 其中M = arr.size(), 但arr[i].size()对不同的i可以不同。要求取一个arr的二维总size为N的子集，限制每个arr[i]只能取连续的前几个（也允许根本不取）。 这样就明确说明所有arr中的元素是都可以预知的，个人感觉这样就比较明确。当然也许真正面试中可以真正澄清这些问题，呵呵，只是个人看法而已。