新鲜Google Onsite~~

manman1990 发表于 2015-9-6 17:44
”rearrange array，使得相邻两个字符是不一样的。 “这题楼主是怎么做的呢？

见sdu的回复哦~我也是这么做的~

wzhwawhxm 发表于 2015-9-6 01:33
楼主第二题，加或者乘的运算必须按照从头到尾的顺序，还是可以像加括号那样结合律？

加括号的结合律。其实就是从头到尾循环下，每次循环递归求左边最大的和右边最大，这两个最大值选择相加还是相乘。就是divide&conquer。

确定吗，这个感觉这个timecomplexity好高啊，你知道这个方法的时间复杂度吗，感觉都晕了，不会算了。。。

wzhwawhxm 发表于 2015-9-8 08:01
确定吗，这个感觉这个timecomplexity好高啊，你知道这个方法的时间复杂度吗，感觉都晕了，不会算了。。。

是的，这是最直白的想法，之后在小哥的提示下改成了二维dp的方法。

是不是先正着从0到n来一遍，然后反着来一遍那种？总共O(n)复杂度?

wzhwawhxm 发表于 2015-9-8 10:16
是不是先正着从0到n来一遍，然后反着来一遍那种？总共O(n)复杂度?

嗯？不太懂你的意思耶。我做的是先初始化对角线，然后沿对角线填表，最后复杂度大概是n^3

wzhwawhxm 发表于 2015-9-8 03:58
你每次选择加或者减，都要去和前一次的最大值和最小值比较，得到这次的最大值和最小值，最后结束的时候， ...

不是不能用减法吗?

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies