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

zyoppy008 发表于 2016-10-3 05:31
aaaabbbccd这种怎么排。。。长度为1的时候 就10种 根据中间那个不一样可能是不一样的。。。比如b作为中间 ...

是一样的，你想清楚就行了，用DFS，一条一条路径来，相同的字符串可以归并为一条路径，只要算有多少个重复需要计算的就行了，比如我们从a开始，a有4种情况，所以从空串到a是有4种情况，然后我们再从a到三个字符的字符串，这时候如果用过一个a之后还剩下3个a,3个b，2个c, 1个d,可以得到aaa, bab, cac，aaa是新加的两个a是3个中间取两个，就是六种情况，bab也是六种，cac是两种情况，也就是说对于任意一个a为起始点，涨到3个字符的PALIN是有14种情况，那么我们有4个不同的a作为起始，所以一共就是56种情况，然后再继续对于其中一条路DFS，一直到不能再加所有字符了，然后回溯

cicean 发表于 2016-10-3 05:35
计算量大并不是因为要再全排一遍，其实他的意思就是说你写全排公式数学计算，万一这个n 很大，你的排列组 ...

如果像LC的N皇后计算解法数，每次要算出一种解法，总解法+1，或者跟CC150那个多少个硬币组成一个TARGET，每发现一种解法，总解法+1，那我那个应该是最快的了，我那个就是列出所有的解法，每出现一次解法+1，而且重复性的解法比如aba, aba aba这样我不用重复列出，仅用数学计算。但DP可能会更加快，看能不能从当前字符串是n长度，就直接通过什么递推公式推出字符串是n+1长度的PALIND个数。你写的那个DP，我也看得比较懵，不确定是不是对的也不确定怎么能改对，期待地里大牛

liurudahai 发表于 2016-10-3 05:46
是一样的，你想清楚就行了，用DFS，一条一条路径来，相同的字符串可以归并为一条路径，只要算有多少个重 ...

你说的这就是把所有情况考虑，暴力求解啊。。。就是看剩下的多少个，然后每种字符取出来有多少种，然后回溯，这种暴力求解肯定是可以的。我的意思是有没有像dp那种，不需要暴力求解，可以利用某种规律或已经算数出来的结果递推下去的。

zyoppy008 发表于 2016-10-3 05:56
你说的这就是把所有情况考虑，暴力求解啊。。。就是看剩下的多少个，然后每种字符取出来有多少种，然后回 ...

我说的就是暴力求解，其实所谓的DFS+BACKTRACKING都是暴力求解，但暴力求解的优化就是最好保证每次解出来都是VALID的答案，而且每个答案以及每个中间过程只计算一次，省去无意义的中间重复计算过程，我这个解法应该做到了

DP的话，我觉得可能会有更加简单的仅通过数学公式得到比如n长度的字符串的PALIN个数和n+1长度的字符串的palin个数的关系，但感觉有点难想到，期待地里的大牛

liurudahai 发表于 2016-10-3 06:00
我说的就是暴力求解，其实所谓的DFS+BACKTRACKING都是暴力求解，但暴力求解的优化就是最好保证每次解出来 ...

我觉得你答案不太可能每个答案及中间过程只算一次，只算一次就几乎最大利用数据了，就是dp了，肯定有多次计算。这题所谓两边加肯定是valid，肯定不能随便排，然后去查看valid不valid这个过程不算优化。肯定有很多重复的计算，backtracking很难把这些优化了

lz第一轮题目是什么意思呀？

楼主有消息没？我同一天面的。。。hr理都不理我

patpat，同跪，不是原题的话还是写不了很快，onsite的时候分析能力比线下也下降了

gaocan1992 发表于 2016-10-3 09:39
patpat，同跪，不是原题的话还是写不了很快，onsite的时候分析能力比线下也下降了

蛋人哥加油

zyoppy008 发表于 2016-10-2 19:08
蛋人哥加油

谢谢！！