2015年10月22日 google MTV onsite

marthew777 发表于 2015-10-23 15:05
G家的题有意思，2是rob cutting的变形，4是matrix multiplication

高人。。rob cutting 是啥？ 我觉得像Palindrome Partitioning II

returning 发表于 2015-10-27 08:12
50 penalty 这个题有意思，一时想不出。求三角形那个应该是lintcode原题吧。

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

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

douya 发表于 2015-10-27 10:50
lintcode原题？没看到啊，题目叫什么名字？ 50 penalty我觉得可以类似Palindrome Partitioning II

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

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

5 有什么好想法？

returning 发表于 2015-10-27 10:57
lintcode有道题是给定一堆数组，求其中多少个triple可以构成三角形。

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

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

douya 发表于 2015-10-27 12:11
所以这个题是要暴力解了？ matrix 乘法可以求个数，但是不好求出是哪几个点吧？

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

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), ....);

3Gdesigner 发表于 2015-10-26 14:30
我觉得3可以用ugly numberＩＩ的方法吧，用dp
用三个指针指向２，３，５，然后每次从 首位加2，3，5的新数 ...

不行的，如果target是1000， 235任意排列都可以了，加上允许重复，这结果都是指数级的了，还能O（N）？

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];
        }

写了下第三题，不过没看到单个字符的条件，数组里字符可以重复或者超长。有问题请指正，感谢！这题复杂度应该是指数级的吧。。应该还能再做点优化。。
        第四题找三角形就记录一下前两个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;
                }