一亩三分地论坛

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

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

[算法题] k sum和Best time to buy and sell stock

[复制链接] |试试Instant~ |关注本帖
金妮韦崽 发表于 2014-9-3 12:04:39 | 显示全部楼层 |阅读模式

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

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

x
想请教两道leetcode题目的变体:

一个是k sum,就是leetcode里面的2 sum, 3 sum, 4 sum普遍化。 http://cs.stackexchange.com/ques ... -3sum-k-sum-problem <---这里有个算法,但是我看来看去不知道怎么用代码实现。

还有就是Best time to buy and sell stocks,允许k次交易。这题我死活想不出来。

求高人指点,谢谢!能直接贴代码的话我感激不尽TAT
1guangnian 发表于 2014-9-3 13:34:49 | 显示全部楼层
k次交易可以dp呀,dp[i][k][s],到i天的时候,已经交易了k次,处于状态s最多赚多少钱,s=1表示已经买入,s=0表示没有买入
回复 支持 反对

使用道具 举报

1guangnian 发表于 2014-9-3 13:37:56 | 显示全部楼层
回复 支持 反对

使用道具 举报

movefast 发表于 2014-9-4 07:15:33 | 显示全部楼层
LS已经说的很好了,我就在补充几句顺便mark下复习用了:P 对lz quote的那个算法我看了下觉得有可能是因为跟leetcode里的题不太一样,那里的算法应该默认target是0,也就是他的3Sum实际是Leetcode里的4Sum。 对Ksum我的体会是总之就两种方法(hashmap或者用pointer),2sum哪种都行,反正都是Onlog(n);3sum可以sort+3pointer implement起来比较简单space还小然后两种都是O(n^2),4Sum用hashmap runtime更好可以到O(n^2),就是扫两边O(n^2)。下面是我4Sum的code,用的是hashmap的方法,很草,凑合看哈:

public class Solution {
            public static List<List<Integer>> fourSum(int[] num, int target) {
            if(num.length < 4) return new ArrayList<List<Integer>>();
        // Arrays.sort(num);
        // for(int i = 0; i < num.length; i++) System.out.print(num[i]+" ");
        // System.out.println();
        HashMap<Integer, HashSet<ArrayList<Integer>>> dict = new HashMap<Integer, HashSet<ArrayList<Integer>>>();
        HashSet<ArrayList<Integer>> res = new HashSet<ArrayList<Integer>>();
        for(int i = 0; i < num.length-1; i++) {
            for(int j = i+1; j < num.length; j++) {
//                    System.out.println(num[i]+num[j]+" "+i+" "+j);
                if(!dict.containsKey(num[i]+num[j])) {
                        ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(i, j));
                        HashSet<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>();
                        set.add(list);
                        dict.put(num[i]+num[j],set);
                }
                else{
                        ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(i, j));
                        if(!dict.get(num[i]+num[j]).contains(list)) {
                                dict.get(num[i]+num[j]).add(list);
//                                System.out.println(dict.get(num[i]+num[j]));
                        }
                }
            }
        }
        
        for(int i = 0; i < num.length-1; i++) {
//            while(num[i+1] == num[i]) i++;
            for(int j = i+1; j < num.length; j++) {
//                while (j != num.length-1 && num[j+1] == num[j]) {
//                    j++;
//                }
                if(dict.containsKey(target-num[i]-num[j])) {
                        HashSet<ArrayList<Integer>> set = dict.get(target-num[i]-num[j]);
                        for(ArrayList<Integer> list : set) {
                                int a = list.get(0);
                                int b = list.get(1);
                                int[] ids = new int[]{a,b,i,j};
                                Arrays.sort(ids);
                                boolean flag = true;
                                for(int x = 0; x < 3; x++) {
                                        if(ids[x] == ids[x+1]) flag = false;
                                }
                                if(flag) {
                                        ArrayList<Integer> comb = new ArrayList<Integer>(Arrays.asList(num[i],num[j],num[a],num[b]));
                                        Collections.sort(comb);
                                        if(!res.contains(comb)) {
                                                res.add(comb);
        //                                        System.out.print(num[i]+num[j]-target+" ");
        //                                        System.out.print(a+" "+b+" "+i+" "+j);
        //                                        System.out.println();
                                            }
                                } else continue;
                        }
                }
               
            }
        }
        // List<List<Integer>> result = new ArrayList<List<Integer>>(res);
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        for(List<Integer> list : res) {
            result.add(list);
        }
        return result;
    }
}



作为对比,下面是我写3Sum的code,用的是3pointer:
public class Solution {
    public List<List<Integer>> threeSum(int[] num) {
        Arrays.sort(num);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for(int i = 0; i < num.length-1; i++) {
            if(i > 0 && num[i] == num[i-1]) continue;
            int start = i+1;
            int end = num.length-1;
            while(start < end) {

                if(num[start]+num[end]==-num[i]) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(num[i]);
                    list.add(num[start]);
                    list.add(num[end]);
                    res.add(list);
                    start++;
                    end--;
                    while (start < end && num[end] == num[end + 1])
                                                end--;

                                        while (start < end && num[start] == num[start - 1])
                                                start++;

                } else if(num[start]+num[end]>-num[i]) {
                    end--;
                } else start++;
               
            }
        }
        return res;
    }
}



Buy stocks K次这个问题是不是有点太generalize了,我感觉这种问题要不就问你没有次数限制要不就是1,2次的,现场做K次是不是有点太难了,尤其考这题的都是bank,这难度他们犯不着吧:P不过我觉得LS的思路是很对的,ls要是有这题的link我可以试着implement一下给你看。我比较水,说的不对请指正哈哈
回复 支持 反对

使用道具 举报

 楼主| 金妮韦崽 发表于 2014-10-14 09:21:19 | 显示全部楼层
movefast 发表于 2014-9-3 18:15
LS已经说的很好了,我就在补充几句顺便mark下复习用了:P 对lz quote的那个算法我看了下觉得有可能是因为跟 ...

我也觉得事实上这两题真正考的概率都不大,毕竟面试时间还是有限的。但是嘛这两题我觉得一旦学会了,就可以增加对算法的感觉,那其他各种DP不就小CASE了
回复 支持 反对

使用道具 举报

迷茫的考拉 发表于 2014-10-23 09:21:17 | 显示全部楼层
话说k次交易不是贪心就可以了吗?~~
只要找出各个极值点不就好了嘛?~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 14:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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