一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 918|回复: 13
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
cc11328 发表于 2015-11-10 01:24:11 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
Given k stack of coins, take n conins, what is the max sum of the n coins.
eg. stack1: 1, 4, 700, 3
        stack2: 5, 10, 6
        if n = 2, then the max sum should be 5+10
        if n = 3, then the max sum should be 1+4+700
宝贝忆彼岸 发表于 2015-11-10 02:17:15 | 显示全部楼层
本帖最后由 宝贝忆彼岸 于 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

使用道具 举报

xiaozhuxiaozhu 发表于 2015-11-10 01:54:17 | 显示全部楼层
本帖最后由 xiaozhuxiaozhu 于 2015-11-10 02:28 编辑

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

使用道具 举报

z928czzc 发表于 2015-11-10 02:05:38 | 显示全部楼层
感觉像是NP问题,只能用recusrion去try所有取法的combination? 是不是还有别的条件。。。
回复 支持 反对

使用道具 举报

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

使用道具 举报

z928czzc 发表于 2015-11-10 02:16:30 | 显示全部楼层
hu4 发表于 2015-11-10 02:11
n等于2的时候不是700+10吗

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

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

使用道具 举报

xiaozhuxiaozhu 发表于 2015-11-10 02:23:39 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-10 02:17
public  int findMaxSum(Stack stack1,Stack stack2,int n){
                if(n == 0 || (stack1.isEmpty() && stack ...

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

使用道具 举报

sxh53 发表于 2015-11-10 02:27:03 | 显示全部楼层
本帖最后由 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...求楼下支招。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-10 02:55:51 | 显示全部楼层

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

使用道具 举报

leilater 发表于 2015-11-30 11:49:08 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-10 02:55
哦哦,对,看错了,不过k个也是一样的解法,回复里面改正了

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

使用道具 举报

leilater 发表于 2015-11-30 11:51:58 | 显示全部楼层
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)中方法。具体怎么做请大神支招
回复 支持 反对

使用道具 举报

cptcpt 发表于 2015-11-30 13:55:02 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-10 02:17
public  int findMaxSum(Stack stack1,Stack stack2,int n){
                if(n == 0 || (stac ...

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

使用道具 举报

Linzertorte 发表于 2015-11-30 14:13:29 | 显示全部楼层
DP吧
dp(k,i) = 前k个stack,一共取i个coin得到的最大值。
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-11-30 14:15:01 | 显示全部楼层
  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)...)
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 20:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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