Ｇｏｏｇｌｅ 09/26 onsite 挂经

第二轮 有没有lc 上类似的题目,  你说是 leetcode file game,但是lc上没这道题目啊?

第一题是个什么意思啊？

楼主能把第一题第二题仔细讲一下吧，还是没搞懂题目要求

我怎么觉得第一题很难。。。

第一题我也觉得 挺难的 求 楼主第一 第二题 具体面经

qiuxuxing007 发表于 2016-10-1 09:17
第二轮 有没有lc 上类似的题目,  你说是 leetcode file game,但是lc上没这道题目啊?

sorry ，类似 flip game 笔误，就 sweet candy 那个游戏，消糖果那个一模一样…

ggwzjhgsq 发表于 2016-10-1 08:00
请问楼主 三哥是想要什么？DP? 。。。

我觉得是Dp， 三哥不告诉我，临走说了一句 DP 比你的bfs 好。

houqingniao 发表于 2016-10-1 09:39
第一题是个什么意思啊？

第一题就是 把 geekforgeeks 那道 longest paladrom subsquence 改成多少种，我数学方法把所有的不同 character 用 hash 弄出来。然后做 按 长度 从1 到string length 做全排。是的很难…绝对不是可以最优解45分钟秒，即使Geek for geeks 那题，我看了下代码。也没那么简单。主要转移方程一时想不到

统一回复下第一题第二题。

第一题 我回来自己google 了下没找到原题 http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/
感觉是这个，但是要找有多少种 palindromic-subsequence 例如 abac， 有 a, b, c, a, aa, aa, aba, aba, aca, aca, 有重复的原因是index 不一样的character 也要算一种， 所以其实就是P（4,1）+P（2,2） + P（2，2）*P（2.1） 全排 。我用DP 做的，但状态转移方程没写对，也就是条件转移方程没写出来。当然楼主给出的是暴利 bfs  全排2^N, 想尝试n^3 dp 失败。 dp[s.lengfth()][s.lengfth()] 根据 length = 1,2,3,4 ……一直到N 判断。

第二题 就是简化版 Candy Crush ，如何初始化 board 如何swap 之后消除，然后上面的要落下来填满，再消。其实，面完上午，楼主就想回家了。我真心觉得没意义。肯定过不了了。我之前看了，其他拿 offer 的面筋 LC340 LC347 这种还有 308 这种 楼主因为练过都可以随手写。而且说实在话。如果这题没见过，我figure 想法，加implement 至少得一个小时，Hard 难度，45 肯定 写不出bug free。我已经看出来了老印不想让我过，当然也怪楼主写代码速度一般。

cicean 发表于 2016-10-1 12:51
第一题就是 把 geekforgeeks 那道 longest paladrom subsquence 改成多少种，我数学方法把所有的不同 cha ...

所以说是subsequence还是不是subsequence？  acbcab 这种  abba 算不算。？