楼主: domofeng
跳转到指定楼层
上一主题 下一主题
收起左侧

2015年10月22日 google MTV onsite

🔗
douya 2015-10-27 08:59:31 | 只看该作者
全局:
marthew777 发表于 2015-10-23 15:05
G家的题有意思,2是rob cutting的变形,4是matrix multiplication

高人。。rob cutting 是啥? 我觉得像Palindrome Partitioning II
回复

使用道具 举报

🔗
douya 2015-10-27 10:50:46 | 只看该作者
全局:
returning 发表于 2015-10-27 08:12
50 penalty 这个题有意思,一时想不出。求三角形那个应该是lintcode原题吧。

补充内容 (2015-10-27 08:34) ...

lintcode原题?没看到啊,题目叫什么名字? 50 penalty我觉得可以类似Palindrome Partitioning II
回复

使用道具 举报

🔗
returning 2015-10-27 10:57:26 | 只看该作者
全局:
douya 发表于 2015-10-27 10:50
lintcode原题?没看到啊,题目叫什么名字? 50 penalty我觉得可以类似Palindrome Partitioning II

lintcode有道题是给定一堆数组,求其中多少个triple可以构成三角形。

补充内容 (2015-10-27 10:58):
我去,仔细一看,你的题不是,我错了。
回复

使用道具 举报

🔗
douya 2015-10-27 11:50:16 | 只看该作者
全局:
5 有什么好想法?
回复

使用道具 举报

🔗
douya 2015-10-27 12:11:33 | 只看该作者
全局:
returning 发表于 2015-10-27 10:57
lintcode有道题是给定一堆数组,求其中多少个triple可以构成三角形。

补充内容 (2015-10-27 10:58):

所以这个题是要暴力解了? matrix 乘法可以求个数,但是不好求出是哪几个点吧?
回复

使用道具 举报

🔗
returning 2015-10-27 13:07:28 | 只看该作者
全局:
douya 发表于 2015-10-27 12:11
所以这个题是要暴力解了? matrix 乘法可以求个数,但是不好求出是哪几个点吧?

给一个graph求三角形,我不知道怎么弄,我估计就是做depth为3的dfs,暴力弄。
回复

使用道具 举报

🔗
Mr.Sagemaker 2015-10-27 15:02:37 | 只看该作者
全局:
douya 发表于 2015-10-27 08:59
高人。。rob cutting 是啥? 我觉得像Palindrome Partitioning II

打错字了,不过估计你能猜出来。。教科书上的经典DP-rod cutting,这题就是变形加了一个penalty而已,很简单,方程改改就行, A=0, B=m, S={i~j}; T(0, m) = min(P(m-j, 50)+T(0,j), P(m-(j-1), 50)+T(0,j-1), ....);
回复

使用道具 举报

🔗
hj867955629 2015-10-27 16:10:13 | 只看该作者
全局:
3Gdesigner 发表于 2015-10-26 14:30
我觉得3可以用ugly numberII的方法吧,用dp
用三个指针指向2,3,5,然后每次从 首位加2,3,5的新数 ...

不行的,如果target是1000, 235任意排列都可以了,加上允许重复,这结果都是指数级的了,还能O(N)?
回复

使用道具 举报

🔗
hj867955629 2015-10-27 16:11:29 | 只看该作者
全局:
returning 发表于 2015-10-27 08:12
50 penalty 这个题有意思,一时想不出。求三角形那个应该是lintcode原题吧。

补充内容 (2015-10-27 08:34) ...

public int minPenalty(int[] nums) {
                int[] dp = new int[nums.length];
                for (int i = 1; i < nums.length; i++) {
                        int tmp = Integer.MAX_VALUE;
                        for (int j = i-1; j >= 0; j--) {
                                tmp = Math.min(tmp, (int)(dp[j]+Math.abs(50-(nums[i]-nums[j]))));
                        }
                        dp[i] = tmp;
                }
                return dp[nums.length-1];
        }
回复

使用道具 举报

🔗
hj867955629 2015-10-27 16:23:13 | 只看该作者
全局:
写了下第三题,不过没看到单个字符的条件,数组里字符可以重复或者超长。有问题请指正,感谢!这题复杂度应该是指数级的吧。。应该还能再做点优化。。
        第四题找三角形就记录一下前两个dfs节点,然后第三个dfs的时候,如果next和上上个一样,并且不等于上一个节点,就是一个三角形了吧

                private String deleteHeadZero(String s) {
                        int i = 0;
                        while (i < s.length() && s.charAt(i) == '0') {
                                i++;
                        }
                        if (i == s.length()) {
                                return "0";
                        }
                        return s.substring(i);
                }
               
                private void combination(List<String> allCombination, StringBuilder cur, int target, int[] nums, int pos) {
                        if (deleteHeadZero(cur.toString()).length() > (""+target).length()) {
                                return;
                        }
                        if (cur.length() != 0) {
                                allCombination.add(cur.toString());
                        }
                        if (pos == nums.length) {
                                return;
                        }
                        int curLen = cur.length();
                        for (int i = pos; i < nums.length; i++) {
                                cur.append(""+nums[i]);
                                combination(allCombination, cur, target, nums, i);
                                cur.delete(curLen, cur.length());
                        }
                }
               
                private void getPermutation(List<String> res, HashSet<String> vis, int target, char[] s, boolean[] visited, StringBuilder cur, int cnt) {
                        if (cnt == s.length) {
                                String tmp = deleteHeadZero(cur.toString());
                                if (tmp.length() <= (""+target).length()) {
                                        if (Integer.parseInt(tmp) <= target && !vis.contains(tmp)) {
                                                vis.add(tmp);
                                                res.add(tmp);
                                        }
                                }
                                return;
                        }
                        for (int i = 0; i < visited.length; i++) {
                                if (visited[i]) {
                                        continue;
                                }
                                visited[i] = true;
                                cur.append(s[i]);
                                getPermutation(res, vis, target, s, visited, cur, cnt+1);
                                visited[i] = false;
                                cur.deleteCharAt(cur.length()-1);
                        }
                }
               
                public List<String> getNumSmallerOrEqualTarget(int[] nums, int target) {
                        List<String> res = new ArrayList<>(), allCombination = new ArrayList<>();
                        HashSet<String> vis = new HashSet<>();
                        combination(allCombination, new StringBuilder(), target, nums, 0);
                        for (String combination: allCombination) {
                                boolean[] visited = new boolean[combination.length()];
                                getPermutation(res, vis, target, combination.toCharArray(), visited, new StringBuilder(), 0);
                        }
                        Collections.sort(res, new Comparator<String>(){
                                public int compare(String a, String b) {
                                        return Integer.parseInt(a) - Integer.parseInt(b);
                                }
                        });
                        return res;
                }
回复

使用道具 举报

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

本版积分规则

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