要回国了,写个简单的总结吧。

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
把贵司招聘信息放这里
查看: 1268|回复: 13
收起左侧

[算法题] google 面试一道 求大神帮忙解解

[复制链接] |试试Instant~ |关注本帖
头像被屏蔽
我的人缘0
cc11328 发表于 2015-11-10 01:24:11 | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽

上一篇:Amazon OA 2 视频非常卡 怎么办?
下一篇:关于binary tree level order traversal的变形题
我的人缘0
宝贝忆彼岸 发表于 2015-11-10 02:17:15 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
本帖最后由 宝贝忆彼岸 于 2015-11-10 02:55 编辑

        public  int findMaxSum(Stack<Integer> stack1,Stack<Integer> stack2,int n){
                if(n == 0 || (stack1.isEmpty() && stack2.isEmpty())){
                        return 0;
                }
                int res = 0;
                if(!stack1.isEmpty()){
                        int temp = stack1.pop();
                        int sum = temp + findMaxSum(stack1,stack2,n-1);
                        if(res < sum){
                                res = sum;
                        }
                        stack1.push(temp);
                }
                if(!stack2.isEmpty()){
                        int temp = stack2.pop();
                        int sum = temp + findMaxSum(stack1,stack2,n-1);
                        if(res < sum){
                                res = sum;
                        }
                        stack2.push(temp);
                }
                return res;
        }
用递归写了一个,不知道有没有DP的解法
看错了,是k个stack,上面的做法是2个的,k个的一样的思路
public static int findMaxSum(List<Stack<Integer>> stacks,int n){
                if(n == 0){
                        return 0;
                }
                int length = stacks.size();
                int res = Integer.MIN_VALUE;
                for(int i=0;i<length;i++){
                        Stack<Integer> cur = stacks.get(i);
                        if(!cur.isEmpty()){
                                int temp = cur.pop();
                                int sum = temp + findMaxSum(stacks,n-1);
                                if(sum > res){
                                        res = sum;
                                }
                                cur.push(temp);
                        }
                }
                return res;
        }

回复 支持 1 反对 0

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
xiaozhuxiaozhu 发表于 2015-11-10 01:54:17 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
本帖最后由 xiaozhuxiaozhu 于 2015-11-10 02:28 编辑

理解错题了。
回复 支持 反对

使用道具 举报

我的人缘0
z928czzc 发表于 2015-11-10 02:05:38 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
感觉像是NP问题,只能用recusrion去try所有取法的combination? 是不是还有别的条件。。。
回复 支持 反对

使用道具 举报

我的人缘0
hu4 发表于 2015-11-10 02:11:12 | 显示全部楼层
n等于2的时候不是700+10吗
回复 支持 反对

使用道具 举报

我的人缘0
z928czzc 发表于 2015-11-10 02:16:30 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
hu4 发表于 2015-11-10 02:11
n等于2的时候不是700+10吗

stack 是说要先取出上面的coin,之后才能拿下面的。

题意大概就是有k堆coin,拿n个,但是是最上面的n个(可以是不同堆)
回复 支持 反对

使用道具 举报

我的人缘0
xiaozhuxiaozhu 发表于 2015-11-10 02:23:39 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
宝贝忆彼岸 发表于 2015-11-10 02:17
public  int findMaxSum(Stack stack1,Stack stack2,int n){
                if(n == 0 || (stack1.isEmpty() && stack ...

原题是k stacks吧
回复 支持 反对

使用道具 举报

我的人缘0
sxh53 发表于 2015-11-10 02:27:03 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
本帖最后由 sxh53 于 2015-11-9 13:29 编辑

一个简单解法是:
假设我从stack1里面取A个数 stack2里取B个数。 A+B=n 求怎么去解这个A和B。
再仔细想,就首先算出如果都从A取的sum数组 比如这个题是[0,1, 5, 705, 708] 然后再算出都从B取i个数的sum的数组。[0,5, 15,21]
然后根据n的值 two pointers。互相移动 然后keep track max就好了。

For k stacks...求楼下支招。
回复 支持 反对

使用道具 举报

我的人缘0
宝贝忆彼岸 发表于 2015-11-10 02:55:51 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

哦哦,对,看错了,不过k个也是一样的解法,回复里面改正了
回复 支持 反对

使用道具 举报

我的人缘0
leilater 发表于 2015-11-30 11:49:08 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
宝贝忆彼岸 发表于 2015-11-10 02:55
哦哦,对,看错了,不过k个也是一样的解法,回复里面改正了

这个方法太好了!想了半天没弄明白时间复杂度该怎么分析呢?
回复 支持 反对

使用道具 举报

我的人缘0
leilater 发表于 2015-11-30 11:51:58 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
sxh53 发表于 2015-11-10 02:27
一个简单解法是:
假设我从stack1里面取A个数 stack2里取B个数。 A+B=n 求怎么去解这个A和B。
再仔细想, ...

对于k stack,按照答主的思路的话应该就是讲n拆分成k个整数的问题了吧,等价于将n个相同的球放入k个不同的盒子的问题,总共有C(n+k-1, k-1)中方法。具体怎么做请大神支招
回复 支持 反对

使用道具 举报

我的人缘0
cptcpt 发表于 2015-11-30 13:55:02 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
宝贝忆彼岸 发表于 2015-11-10 02:17
public  int findMaxSum(Stack stack1,Stack stack2,int n){
                if(n == 0 || (stac ...

你这是从stack1取一个,然后从stack2取下一个吧?楼主取的N个是不是都必须出自同一个stack?而且是stack顶部?
回复 支持 反对

使用道具 举报

我的人缘0
Linzertorte 发表于 2015-11-30 14:13:29 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
DP吧
dp(k,i) = 前k个stack,一共取i个coin得到的最大值。
回复 支持 反对

使用道具 举报

我的人缘0
Linzertorte 发表于 2015-11-30 14:15:01 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
  1. dp(k,i) =max( dp(k-1,i),dp(k-1,i-1)+sum(k,1),dp(k-1,i-2)+sum(k,2)...)
复制代码
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-27 21:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表