google面经求人品

谢谢楼主！请问第一轮第三题的解法是求所有这些点y轴的平均值吗？如何证明啊求思路~

不高兴 发表于 2015-10-31 04:21
第二天就回复了吗？好迅速啊

嗯，是的。

liuyue952 发表于 2015-10-31 06:56
谢谢楼主！请问第一轮第三题的解法是求所有这些点y轴的平均值吗？如何证明啊求思路~

不是平均值，是中位数的那个点。证明：你可以把点按照y轴排序好，把所有点group成pair，比如（－1，0，3，6，7）, 然后－1和7一组，0和6一组，3一组。  然后就好证明了。

请问楼主，第二题是用dfs 产生非递减的几个数，然后求乘积最大值吗？

A30041839 发表于 2015-11-1 13:20
请问楼主，第二题是用dfs 产生非递减的几个数，然后求乘积最大值吗？

这个太慢了吧，我用的DP

kakaChen 发表于 2015-11-1 23:43
这个太慢了吧，我用的DP

是太慢了。。我写了个dp, dp[i]表示把i分解后最大的乘积
int maxProduct(int n) {
    vector<int> dp(n + 1, 0);
    dp[1] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= i / 2; ++j) {
            dp[i] = max(dp[i], dp[j] * dp[i - j]);
        }
        dp[i] = max(dp[i], i);
    }
    return dp[n];
}
感觉很像leetcode total count of bst那个题。。是这样做的吧，楼主？

补充内容 (2015-11-2 00:18):
更正下:dp[i]表示把i分解后最大乘积。。

补充内容 (2015-11-2 00:20):
左边方括号都没了。。好诡异，是dp(i)

A30041839 发表于 2015-11-2 00:16
是太慢了。。我写了个dp, dp表示把i分解后最大的乘积
int maxProduct(int n) {
    vector dp(n + 1, 0 ...

对，大概是这么的。

A30041839 发表于 2015-11-2 00:16
是太慢了。。我写了个dp, dp表示把i分解后最大的乘积
int maxProduct(int n) {
    vector dp(n + 1, 0 ...

这个代码有问题。
第二个循环应该j ＝ 1 －》i。
vector<long> P(n+1, 1);
  P[1] = 1;
  for(int i = 2; i <= n; i++)
  {
    long res = i;
    for(int j = 1; j < i; j++)
    {
      res = max(res, (i-j)*P[j]);
    }
    P[i] = res;
  }
  return P[n];

kakaChen 发表于 2015-10-30 21:23
我是用的字典树，然后逐个往下找，如果有一个不match，就拿别的替换继续向下找。

应该是不管是否找到对应的字符都需要把其他子节点走at least一层吧， 因为可能cur这个不符合但是下面的全部一样。

yjfox 发表于 2015-11-2 01:15
应该是不管是否找到对应的字符都需要把其他子节点走at least一层吧， 因为可能cur这个不符合但是下面的全 ...

不是啊，只有找不到对应的时候才把当前的走一遍，你再想想？