📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3410| 回复: 5
跳转到指定楼层
上一主题 下一主题
收起左侧

k sum和Best time to buy and sell stock

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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

上一篇:讨论一下10.3
下一篇:【已解决】请教Java Comparable接口问题
🔗
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次交易不是贪心就可以了吗?~~
只要找出各个极值点不就好了嘛?~
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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