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

前两轮难是因为有工作经验吗

liurudahai 发表于 2016-10-3 01:21
好像和PALINDROM PERMUTATION还是不一样，但是应该可以修改得到答案

第一题是所有轮最难的好吗。。。。你改给我看看

1015 那个食堂巨难吃

zyoppy008 发表于 2016-10-3 03:07
第一题是所有轮最难的好吗。。。。你改给我看看

palidnrome permutation是n个字母组成n长度的palindrome，这个题是n个字母组成长度为1-n之间的palindrome，palindrome permutation的网上的方法是从空字符串开始，或者只有一个的那个字符开始，从两边对称的插入其他字符，用遍历和递归，我觉得可以改成从空字符开始或者任意一个已有的字符开始，从两边遍历+递归对称插入其他字符，因为这样得到的都是PALINDROME，所以每次插入都塞到结果里，不需要用完所有字符

补充内容 (2016-10-3 04:02):
这样应该可以得到所有不重复的组合，不过看楼主的答案是重复的也要算，比如abac的结果aba和aca的结果要出现两次，那么首先，我们按permutation palindrome那题得到hashmap，a,2, b, 1, c, 1，然后从空字符开始

补充内容 (2016-10-3 04:03):
对称插入，得到aa，然后因为不同index的组合算两个，所以这里需要输出2个aa，然后从一个字符开始，就是a b c，因为a有两个，我们可以查HASHMAP里a还有几个，就输出几个，所以这一轮输出a, a, b, c

补充内容 (2016-10-3 04:05):
然后再下一轮从一个字符的permutation开始对称插入，对于a, a那两个，剩下的是a 1, b 1, c1没法对称两边插入，就直接结束了，对于b和c那两个组合，还剩下2个a，然后对称在两边插入两个a，得到aba, aca，当然了因...

补充内容 (2016-10-3 04:05):
为这两个a算的两个不同的，所以要输出两次aba, aca

补充内容 (2016-10-3 04:06):
再进一步扩展如果是aaabc这样的，在a单独那一步要输出3个a，在从b到aba这一步的时候，要考虑有3个index不同的a，那么这里就有A32，六种组合，要输出6个aba

补充内容 (2016-10-3 04:11):
我这个方法就是back tracking可以输出所有的结果，但如果楼主的题是只需要输出有多少个组合这个数字的话，可能可以用DP，但暂时我不确定要怎么用

liurudahai 发表于 2016-10-3 04:00
palidnrome permutation是n个字母组成n长度的palindrome，这个题是n个字母组成长度为1-n之间的palindrome ...

我的方法是参看了一个印度人 写的Longest Palindrome Subsequence. dp[n][n] 是表示 string 长度，然后从左上角开始check 当length  = 1 的时候 ，如果length = 1 那么就有的dp[0][0] dp[1][1] dp[2][2]....以此类推 这时候每个都是dp[i][j] = [i - 1][j - 1] + 1 先初始化得到开始的状态，也就是说对角线是个递增数列。
然后再看lenth = 2 的状态，如果是2 那么就判断 dp[0][1] dp[1][2], dp[2][3] dp[3][4] 以此类推当前 第二个字母跟第一是不是一样的，如果是一样的那么就 dp[0][0] + dp[1][1] + 1 , 转移方程就是dp[i][j] = dp[i][j - 1] + dp[i+ 1][j] + 1, 如果不等就是看每次这个 length = i 这个string 的 第一个字母跟最后一个字母是不是一样的。 以此类推，然后 最后答案是 dp[0][n-1] 。然后老印让我证明，我最困惑的是，如果，位置不一样也要算不一样的pattern 我怎么在 dp【】【】记重复 ，难道要逆序再找一遍么？ 因为只用了一般的订票【】【】 就是对角线以上区域，是不是直接x2 关系就可以，我就是这个没明白。所以老印让我证明我就慌了。没写出来，其实。

我再说Hashmap 全排这种，这个我也跟印度哥哥说了。
他不满意，因为我出了 DFS 找全戒外还说了。先挑出所有字母的以及其重复次数，开始做全排。
例如：length 为 1 怎么全排，2 怎么全排，一直到n， 老印说你不觉得这个计算量很大么？因为你排了length 2 之后，就可以在这个基础上，继续 排了，我说那不就是dp 么？ 他说，那你写dp 呗。我去，然后我就站白板变一个劲的想转移方程。就想成上面那样，于是我实在不知道怎么处理重复的问题，就是pattern 一样的 pal，字母来自不同index 的排列。
坑爹……

cicean 发表于 2016-10-3 05:09
我再说Hashmap 全排这种，这个我也跟印度哥哥说了。
他不满意，因为我出了 DFS 找全戒外还说了。先挑出所 ...

你写的DP那个我也不是很知道，不过全排肯定不用对每种长度重新全排了，比如我之前说的那个解法，只有5个起始点，分别是"", "b", "c"和2个"a"，然后再再此基础上排出2个"aa", 2个"aba", 2个"aca" ，也就是每种需要输出的组合，只会构造一次，不会重复构造，应该也不会出现构造了不能输出的invalid的结构，我只是觉得如果只要输出组合数，不需要输出所有的组合的话，或许可以用DP

补充内容 (2016-10-3 05:22):
你如果想完全套用palindrome permutation那个题，从n个字符中挑1个，挑2个...挑n个，来用那个题的解法全排permutation确实计算量会很大，而且重复计算的会很多

liurudahai 发表于 2016-10-3 05:17
你写的DP那个我也不是很知道，不过全排肯定不用对每种长度重新全排了，比如我之前说的那个解法，只有5个 ...

aaaabbbccd这种怎么排。。。长度为1的时候 就10种 根据中间那个不一样可能是不一样的。。。比如b作为中间的，就只剩两个b 中间为a就只剩3个a了。 每次你拍完 加入剩下4个a 两个b  你是两边加上bb 还是两边加上aa 剩余情况又不同。。。你每次做不同选择 会导致后后面排序结果不同 就不能单纯的排了。

liurudahai 发表于 2016-10-3 05:17
你写的DP那个我也不是很知道，不过全排肯定不用对每种长度重新全排了，比如我之前说的那个解法，只有5个 ...

计算量大并不是因为要再全排一遍，其实他的意思就是说你写全排公式数学计算，万一这个n 很大，你的排列组合公式计算量就大了，例如 大数加减乘除，这么多位的计算。我当时心说，谁让你非要重复pattern。本来这个组合数就不会很小。
我 dp length 解法只能解决，当前，无重复状态下，有多少种，因为我判断length 移动的时候 例如 length = 2的情况 是 dp[0][1] dp[1][2]....三的情况是 dp[0][2], dp[1][3],dp[2][4]这样的也就是说 只连续的往后找pattern 永远也不会出现 第一个字母和倒数第三个 组成length 2 的情况，这其实不是全排，虽然是subsecquence.例如 abac 我会判断 length = 2 时 ab, ba, ac, 但是 bc ,和 aa 怎么在 dp 二维数组表示，我很困惑如果想判断 aa 我只能等 length 等于 3 的时候 aba 和 bac 的时候去判断，最后两个字母相等，算一个，同时这个中间又有一个 b 的pal 所以 dp[i][j - 1], dp[i+1][j] ，如果 第一个字母和最后一个字母相等 也要加1.当时就晕了。当然这还不是重点，重点是 index 不同的组合我怎么表现出来，例如 aba index 排列可以是（012）or（201）可是我的dp 怎么展现这一点？ 如果abba （0123）（0213）（3120）（3210） 这四种我怎么在dp 反应在过程存储中？ 当时就懵逼了。只能找到pattern 在写个help 弄个全排结果输入回来、

liurudahai 发表于 2016-10-3 01:10
第一题是LC原题PALINDROME PERMUTATION吧

如果能是这个题的话，我就不会跪的脆脆的。我想可能是 印度小伙伴，记错题，我安慰自己说他本来想出这道题，但自己忘记了这题是啥，结果说了一道，他以为特别容易。或者是他本来想让我写longest palindrome substring 后来，自己又没记住题，就随口说了一个subsecquence ， 又或者他觉得这题太容易，马上就能写出来，就说，统计下重复吧。