2015年10月22日 google MTV onsite

hj867955629 发表于 2015-10-27 16:23
写了下第三题，不过没看到单个字符的条件，数组里字符可以重复或者超长。有问题请指正，感谢！这题复杂度应 ...

你再看看LZ的提示，第三题就是subsets。。不用这么复杂的。。不过我再次震惊了，你码代码我擦真快啊。。

hj867955629 发表于 2015-10-27 16:11
public int minPenalty(int[] nums) {
                int[] dp = new int[nums.length];
                for (int i = 1; i < num ...

50 penalty这个，关键是看能不能比n^2好吧

marthew777 发表于 2015-10-27 23:36
你再看看LZ的提示，第三题就是subsets。。不用这么复杂的。。不过我再次震惊了，你码代码我擦真快啊。。

subsets还要permutation吧，23可以，32也行呀？

returning 发表于 2015-10-28 00:51
50 penalty这个，关键是看能不能比n^2好吧

dp已经最优了吧感觉。。

你再想想。。其实就是经典dfs的一个小变形。。多加一行就ok。。easy。。

marthew777 发表于 2015-10-28 02:24
你再想想。。其实就是经典dfs的一个小变形。。多加一行就ok。。easy。。

你是说分别加前面和加后面？

hj867955629 发表于 2015-10-28 02:30
你是说分别加前面和加后面？

恩，前入和后入,两种姿势都要做。。。。但注意，前入的时候要注意安全，检查是不是0

marthew777 发表于 2015-10-28 02:35
恩，前入和后入,两种姿势都要做。。。。但注意，前入的时候要注意安全，检查是不是0

那确实代码量少了不少，不过复杂度还是指数级的，谢啦！

LZ请问第5题思路。。。