一亩三分地论坛

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

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

脸家店面

[复制链接] |试试Instant~ |关注本帖
wzs9988 发表于 2016-8-17 03:52:23 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Other在职跳槽

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

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

x
刚电面完的脸家,估计要挂。
听着像一个老中面的,Find longest arithmetic subsequence in an unsorted array.
没做过,现场想的思路。DP relation死活没想出来。对方也没有给什么hint。

于是刚刚研究了一下,
http://www.geeksforgeeks.org/len ... -in-a-sorted-array/
https://prismoskills.appspot.com ... tic_progression.jsp


原来是个二维DP……而且我没想到可以用这个关系:(sortedArr + sortedArr[k] ) - 2*sortedArr[j]
不过,这些方法貌似是只有sort之后才能用?unsorted array是什么思路呢…….鐣欏璁哄潧-涓浜-涓夊垎鍦


补充内容 (2016-8-16 14:54):
排版有点错,我是想说:
(sortedArr + sortedArr[k]) - 2*sortedArr[j];

补充内容 (2016-8-16 14:56):.鐣欏璁哄潧-涓浜-涓夊垎鍦
好吧,不知道为啥编辑不了……更新之后还是错的

评分

1

查看全部评分

喜马拉雅疯子 发表于 2016-8-29 00:59:41 | 显示全部楼层
我的思路和@Lilian1109 一样的。
  1. // The idea is to maintain a 2d array. Called length[input.length][input.length]
  2. // length[i][j] means the length of the arithmetic that ends with input[i] and input[j]
  3. // And a hashMap to record the index of every number
  4. // We traverse the input from index 1 to the end.
  5. // Everytime we meet a number, fix this as the end of sequence
  6. // Then traverse back and try to make every number as second last number
  7. // When we fix one as second last one number, we calculate the gap as input[last] - input[secondLast]
  8. // look into hashmap to find is there a number in the input equals to input[secondLast].
  9. // And check its index whether it is smaller than secondLast.. 1point 3acres 璁哄潧
  10. // If it is. Then this is the third last number. And we should already have length[thridLast][secondLast]
  11. // Then length[secondLast][last] = length[thridLast][secondLast] + 1
  12. // If it is not. We make length[secondLast][last] = 2 -- those two number are the only numbers in the arithmetic
  13. 'Time complexity: O(n^2), space complexity: O(n^2) -- for only return length'
  14. public int findLongest(int[] input) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  15.         if (input.length <= 2) {
  16.             return 2;
  17.         }
  18.         int maxLen = 2;
  19.         int[][] length = new int[input.length][input.length];-google 1point3acres
  20.         HashMap<Integer, List<Integer>> valueToIndex = new HashMap<>();
  21.         for (int i = 0; i < input.length; i++) {
  22.             if (!valueToIndex.containsKey(input[i])) {
  23.                 valueToIndex.put(input[i], new ArrayList<Integer>());
  24.             }
  25.             valueToIndex.get(input[i]).add(i);
  26.         }
  27.         for (int index = 1; index < input.length; index++) {
  28.             for (int secondLast = index - 1; secondLast >= 0; secondLast--) {
  29.                 int gap = input[index] - input[secondLast];
  30.                 int next = input[secondLast] - gap;
  31.                 if (valueToIndex.containsKey(next)) {
  32.                     int nextIndex = -1;
  33.                     for (int j = valueToIndex.get(next).size() - 1; j >= 0; j--) {
  34.                         if (valueToIndex.get(next).get(j) < secondLast) {
  35.                             nextIndex = valueToIndex.get(next).get(j);
  36.                             break;
  37.                         }
  38.                     }. From 1point 3acres bbs
  39.                     if (nextIndex != -1) {. 1point 3acres 璁哄潧
  40.                         length[secondLast][index] = length[nextIndex][secondLast] + 1;
  41.                         maxLen = Math.max(maxLen, length[secondLast][index]);
  42.                     }. 1point 3acres 璁哄潧
  43.                 }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  44.                 if (length[secondLast][index] == 0) {
  45.                     length[secondLast][index] = 2;
  46.                 }
  47.             }
  48.         }
  49.         return maxLen;
  50.     }
复制代码

. From 1point 3acres bbs
如果要打印出来的话,吧length 换成List<Integer>[][]即可

补充内容 (2016-8-29 01:04):
测试了几个test case 都没问题
比如输入 {5,4,2,6,6,-1,-2,6,-4,6,-4} return 4
回复 支持 2 反对 0

使用道具 举报

WL928 发表于 2016-8-17 05:06:39 | 显示全部楼层
这就是个一维DP吧,回头看之前的,如果满足 array[j] < array[i], 0<j<i, dp[i] = max(dp[i], dp[j] + 1)
回复 支持 1 反对 0

使用道具 举报

feifly2009 发表于 2016-8-17 04:19:45 | 显示全部楼层
请问LZ, 没有sort的数组,允许自己sort一下不?
回复 支持 反对

使用道具 举报

 楼主| wzs9988 发表于 2016-8-17 04:29:51 | 显示全部楼层
feifly2009 发表于 2016-8-16 15:19
请问LZ, 没有sort的数组,允许自己sort一下不?
.鏈枃鍘熷垱鑷1point3acres璁哄潧
面试官没说不行。.鐣欏璁哄潧-涓浜-涓夊垎鍦
但是sort之后结果不就变了么?比如input [1,0,2,3] 最长等差子序列是[1,2,3],sort之后就变成[0,1,2,3]是最长的了?
回复 支持 反对

使用道具 举报

 楼主| wzs9988 发表于 2016-8-17 05:23:21 | 显示全部楼层
WL928 发表于 2016-8-16 16:06. 鍥磋鎴戜滑@1point 3 acres
这就是个一维DP吧,回头看之前的,如果满足 array[j] < array, 0
. From 1point 3acres bbs
他要求是longest等差数列,不是求longest increasing subsequence
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-8-18 02:50:45 | 显示全部楼层
请问lz什么叫arithmetic subsequence?
回复 支持 反对

使用道具 举报

WL928 发表于 2016-8-18 02:52:54 | 显示全部楼层
wzs9988 发表于 2016-8-17 05:23
他要求是longest等差数列,不是求longest increasing subsequence

啊。。。好吧,。。看得粗心了
回复 支持 反对

使用道具 举报

lll_2013 发表于 2016-8-18 03:57:11 | 显示全部楼层
你们想的是不是想的太复杂了?我就是从头到尾扫一遍找到adjacent distance diff, 在找一遍这个distance diff的array,找到最多那个,再扫一遍,把index找到就好了-google 1point3acres
复杂度O(n)
回复 支持 反对

使用道具 举报

求内退求offer 发表于 2016-8-18 08:03:59 | 显示全部楼层
为什么最近都是这么难的题目啊
回复 支持 反对

使用道具 举报

 楼主| wzs9988 发表于 2016-8-18 08:52:40 | 显示全部楼层
lll_2013 发表于 2016-8-17 14:57
你们想的是不是想的太复杂了?我就是从头到尾扫一遍找到adjacent distance diff, 在找一遍这个distance di ...

这样求出来是相邻元素的最长吧,但是未必是相邻的?还是我理解错你的意思了……
回复 支持 反对

使用道具 举报

 楼主| wzs9988 发表于 2016-8-18 08:54:49 | 显示全部楼层
pawprinter 发表于 2016-8-17 13:50
请问lz什么叫arithmetic subsequence?

其实就是等差数列的意思。
不过不是指subarray,是指subsequence,就是组成等差数列的数字们在原数组未必是相邻的。
回复 支持 反对

使用道具 举报

dashuaiding 发表于 2016-8-18 09:15:58 | 显示全部楼层
用两个一维数组纪录就可以了,. 1point 3acres 璁哄潧
M[i] represents longest arithmetic progress ended at i
N[i] represents longest arithmetic prgress ended at i, the gap is what.

M[i] = max(M[k]) + 1   if(input[i] - input[k] = N[k])  (0 <= k < i)

int longest(vector<int> input) {. 1point 3acres 璁哄潧
        int M[input.size()];
        int N[input.size()];.1point3acres缃
        M[0] = 1;
        int result = 0;.1point3acres缃
        for(int i = 1; i < input.size(); i++) {
                M[i] = 0;
                for(int j = 0; j < i) {
                        if(j == 0) {
                                M[i] = 2;
                                N[i] = input[i] - input[0];
                                continue;
                        }
                        if(input[i] - input[j] == N[j]) {. more info on 1point3acres.com
                                if(M[j] + 1 > M[i]) {
                                        M[i] = M[j] + 1;
                                        N[i] = N[j];
                                }
-google 1point3acres
                        }
                }
                result = max(result, M[i]);-google 1point3acres
        }
        return result;
}
回复 支持 反对

使用道具 举报

 楼主| wzs9988 发表于 2016-8-18 11:26:31 | 显示全部楼层
dashuaiding 发表于 2016-8-17 20:15
用两个一维数组纪录就可以了,
M represents longest arithmetic progress ended at i
N represents long ...

感觉还是不太对,如果input是[0,13,3,12,6,11,10,9],这个方法会返回[0,3,6,9]的长度,而不是[13,12,11,10,9],因为一开始的算的公差3其实在后来turns out不是最优的了,最优的公差是之后出现的-1,而我们并没有存这一个信息。

我把中间的状态print出来看了看:.鏈枃鍘熷垱鑷1point3acres璁哄潧
M: 1 2 2 2 3 2 2 4
N: 0 13 3 12 3 11 10 3 . 鍥磋鎴戜滑@1point 3 acres
result = 4
回复 支持 反对

使用道具 举报

dashuaiding 发表于 2016-8-18 11:45:57 | 显示全部楼层
wzs9988 发表于 2016-8-18 11:26
感觉还是不太对,如果input是[0,13,3,12,6,11,10,9],这个方法会返回[0,3,6,9]的长度,而不是[13,12,11,1 ...

. 1point3acres.com/bbs我这里做的是递增的,你在maintain 一个 K,表示的是递减的,最后结果这两个再比较一下,就可以了
回复 支持 反对

使用道具 举报

lll_2013 发表于 2016-8-18 12:22:15 | 显示全部楼层
wzs9988 发表于 2016-8-17 19:52
这样求出来是相邻元素的最长吧,但是未必是相邻的?还是我理解错你的意思了……

是我理解错题意了,抱歉
回复 支持 反对

使用道具 举报

sedernet 发表于 2016-8-18 12:43:42 | 显示全部楼层
使用一個map紀錄所有的數字,定住開頭前兩個,查找是否有接下來吻合的數字,複雜度O(n^2)
程式碼如下:
int longest(vector<int>& nums) {
        std::unordered_set<int> set(nums.begin(),nums.end());
        int size=nums.size();
        int longest=0;
        
        for(int i=0;i<size;i++){
            for(int j= i+1; j<size; j++){. more info on 1point3acres.com
                int diff = nums[j] - nums;
                if(set.find(nums-diff)==set.end()){
                    int m=nums;
                    int cnt=1;. visit 1point3acres.com for more.
                    while(set.find(m+diff)!=set.end()){
                        m+=diff;
                        cnt++;
                    }
                    longest=max(longest,cnt);.鏈枃鍘熷垱鑷1point3acres璁哄潧
                }
               
            }
        }
        . Waral 鍗氬鏈夋洿澶氭枃绔,
        return longest;
    }

补充内容 (2016-8-18 13:32):. 1point3acres.com/bbs
定住前兩個外,還要再考慮誰前誰後,需要再修改一下程式碼
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-8-19 10:47:52 | 显示全部楼层
dashuaiding 发表于 2016-8-18 11:45
我这里做的是递增的,你在maintain 一个 K,表示的是递减的,最后结果这两个再比较一下,就可以了

你的代码哪里显示只记录递增数列?我感觉递增递减都包括了?能解释下吗?多谢啦
回复 支持 反对

使用道具 举报

dashuaiding 发表于 2016-8-19 12:14:53 | 显示全部楼层
更新一下,我前面的算法有误,N应该是一个2D array而不是现在这样一维的,记录了之前所有的M[i]相等的gap,这样的话以后才可能去check
回复 支持 反对

使用道具 举报

dashuaiding 发表于 2016-8-19 13:02:40 | 显示全部楼层
int longest(vector<int> input) {
    int M[input.size()];
    vector<vector<int>> N(input.size(), vector<int>(0));
    M[0] = 1;
    int result = 0;
    for(int i = 1; i < input.size(); i++) {
        M[i] = 0;
        for(int j = 0; j < i; j++) {
            if(j == 0) {
                M[i] = 2;
                N[i].push_back(input[i] - input[0]); ;
                continue;
            }
            for(int k = 0; k < N[j].size(); k++) {
                if(input[i] - input[j] == N[j][k]) {
                    if(M[i] < M[j] + 1) {
                        M[i] = M[j] + 1;
                        N[i].clear();
                        N[i].push_back(input[i] - input[j]);
                    } else if(M[i] == M[j] + 1) {
                        N[i].push_back(input[i] - input[j]); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                    }
                } else {
                    if(M[i] == 2) {
                        N[i].push_back(input[i] - input[j]);
                    }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                }
            }
        }
        result = max(result, M[i]);
    }
   
    return result;
}
回复 支持 反对

使用道具 举报

hunter12345654 发表于 2016-8-19 17:34:44 | 显示全部楼层
dashuaiding 发表于 2016-8-18 11:45
我这里做的是递增的,你在maintain 一个 K,表示的是递减的,最后结果这两个再比较一下,就可以了

感觉两个数组存的信息还是不够呀。 1,3,5,7,9,13,17,21  。你这程序输出的是5? 但是结果应该是6
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 18:16

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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