LinkedIn一面攒人品

readman 发表于 2014-8-1 08:37
https://gist.github.com/gaoyike/40df1e0ec5a6c95e0014

做出来了

great, but seems do not meet the follow-up at 18th floor.

北美农民 发表于 2014-8-1 22:31
great, but seems do not meet the follow-up at 18th floor.

什么是不相同?
{1,2,3}
[[1, 1, 1], [1, 2, 2], [1, 3, 3], [2, 2, 2], [2, 2, 3], [2, 3, 3], [3, 3, 3]]
这个都不相同吧..
你的意思是不能同一个数取值?
{1,2,3} = [[1,2,3]] ?

补充内容 (2014-8-1 23:15):
是..{1,2,3} = null..

补充内容 (2014-8-1 23:19):
在加入前, 添加条件 if (l != i && j != i && j != l)
{5, 2, 4, 8, 0} =>[[2, 4, 5], [4, 5, 8]]

北美农民 发表于 2014-8-1 22:31
great, but seems do not meet the follow-up at 18th floor.

   public HashSet<ArrayList<Integer>> valid2(int[] A) {
        HashSet<ArrayList<Integer>> result = new HashSet<ArrayList<Integer>>();
        Arrays.sort(A);
        for (int i = 0; i < A.length; ++i) {
            int k = i;
            for (int j = i; j < A.length; ++j) {
                while (k < A.length && A[i] + A[j] > A[k])
                    ++k;
                for (int l = j; l < k; l++) {
                        if (A[i] != A[j] && A[j] != A[l] && A[i] != A[l]) {
                            ArrayList<Integer> tmp = new ArrayList<Integer>();
                            tmp.add(A[i]);
                            tmp.add(A[j]);
                            tmp.add(A[l]);
                            result.add(tmp);
                        }
                }
            }
        }
        return result;
    }


Hashset - =

readman 发表于 2014-8-1 10:53
public HashSet valid2(int[] A) {
        HashSet result = new HashSet();
        Arrays.sort( ...

Sry cannot type CN in company.

Still not correct. An extreme example is, {{2, 2, 2}} will be returned if the input is {2. 2. 2. ...., 2}.
All solutions should be unique.

北美农民 发表于 2014-8-2 00:09
Sry cannot type CN in company.

Still not correct. An extreme example is, {{2, 2, 2}} will be re ...

如果
{2. 2. 2. ...., 2} => {{2, 2, 2}}
那么不就是说, 3个数字, 每一个都可以pick任何不重复的Index上的数字, 但是无所谓结果是否是相同字符.

那么
{2, 2, 3, 3, 4, 4} =>  {2, 3, 4} 为什么只有 一个? {2,3,3} 为什么没有...

readman 发表于 2014-8-1 11:15
如果
{2. 2. 2. ...., 2} => {{2, 2, 2}}
那么不就是说, 3个数字, 每一个都可以pick任何不重复的Index ...

I just listed {2, 3, 4} because of simplicity,

if the input is {2, 2, 3, 3, 4, 4}, the result should be {{2,2,2}, {2,3,3}, {2, 3, 4}, {3,3,3},{3,3,4}, {3,4,4}, {4,4,4}}. Each solution has to be unique.

北美农民 发表于 2014-8-1 21:25
为啥c始终是b后面的一个？ 必须找到c' 使得 a + b

嗯，你说得对，面的时候没让考虑重复的情况，所以排完序后是递增的而且只要返回一个。。。各位发散得好~这样以后碰到就轻松啦

qshen1989 发表于 2014-8-1 12:34
嗯，你说得对，面的时候没让考虑重复的情况，所以排完序后是递增的而且只要返回一个。。。各位发散得好~ ...

no, even we have 发散ed, the time complexity does not become better than brute-force. Just some trvial constant time optimization.

北美农民 发表于 2014-8-2 01:37
no, even we have 发散ed, the time complexity does not become better than brute-force. Just some tr ...

{2,3,7,8,9,10} 这样， i=0:length-3; j=i+1: length-2; k=j+1;
i=0 j=1 k=2时
2+3<7, 就不用考虑后面的8,9,10了，++j;
i=0 j=2 k=3
2 + 7 > 8 满足

补充内容 (2014-8-2 02:53):
刚出去买饭了= =要返回所有解的话的确是 O(n^3)，只要第一个的话是O(n^2)吧？

北美农民 发表于 2014-8-2 01:37
no, even we have 发散ed, the time complexity does not become better than brute-force. Just some tr ...

http://stackoverflow.com/questio ... gles-from-n-numbers