一亩三分地论坛

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

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

[算法题] G家面试 Longest Increasing Subarray 请问有没有更优解

[复制链接] |试试Instant~ |关注本帖
atwoodwang0918 发表于 2016-1-13 13:10:49 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 atwoodwang0918 于 2016-1-13 13:12 编辑

在地里看到一个同学最近的Google面经里有这个题 就自己写了一下
题目是: 找到一个subarray里最长的递增子序列 Ex. {1,2,3,2,1,4,3} 里面最长的递增子序列是{1,2,3} 则返回3. Follow up是一个2D的array数组 可以上下左右的走 求最长的递增子序列。
一维的很简单 DP遍历一遍就可以了 O(n) time O(n) space.
  1. public class Solution{
  2.     public int LIS(int[] array){
  3.         if(array==null) return 0;
  4.         if(array.length<=1) return array.length;
  5.         int max = 0;
  6.         int[] dp = new int[array.length];
  7.         dp[0]=1;
  8.         for(int i=1;i<array.length;i++){
  9.             if(array[i]>array[i-1]) dp[i]=dp[i-1]+1;
  10.             else dp[i]=1;
  11.             max = Math.max(max,dp[i]);
  12.         }
  13.         return max;<span style="line-height: 1.5;"><blockquote>public class Solution{</span>
复制代码
 楼主| atwoodwang0918 发表于 2016-1-13 13:13:10 | 显示全部楼层
本帖最后由 atwoodwang0918 于 2016-1-13 13:20 编辑

关键是Follow up 我对每一个点求最长递增序列 用一个数组来保存中间值 但是我不确定这个方法的时间复杂度是多少 有没有大神解答下 而且请问有没有更优化的方法?谢谢!!!
public class Solution{
        int[][] matrix;int[][] longest;
        int row,col;
        public int LIS(int[][] matrix){
            if(matrix==null) return 0;
            if(matrix.length==0) return 0;
            this.matrix = matrix;
            row = matrix.length;
            col = matrix[0].length;
            longest = new int[row][col];
            int max = 0;
            for(int i=0;i<row;i++){
                for(int j=0;j<col;j++){
                    int cur = findMax(i,j);
                    max = Math.max(cur,max);
                }
            }
            return max;
        }

        //Find the longest increasing subarray starting at point (i,j)
        public int findMax(int i,int j){
            if(longest[j]==0){
                int max=0;
                int[][] dir ={{0,1},{0,-1},{1,0},{-1,0}};//4 directions.
                for(int[] d:dir){
                    if(i+d[0]>=0&&i+d[0]<row&&j+d[1]>=0&&j+d[1]<col&&matrix[i+d[0]][j+d[1]]>matrix[j]){
                        int cur = findMax(i+d[0],j+d[1]);
                        max = Math.max(cur,max);
                    }
                }
                longest[j]=max+1;
            }
            return longest[j];
        }
}


回复 支持 反对

使用道具 举报

 楼主| atwoodwang0918 发表于 2016-1-13 13:22:12 | 显示全部楼层
代码粘贴有问题 Follow up的代码在下面~
回复 支持 反对

使用道具 举报

epochou 发表于 2016-1-13 13:41:52 | 显示全部楼层
第一题为什么要用DP,如果index连续的话,直接扫一遍就可以了吧。
第二题复杂度是M*N, 因为每个点只过了一遍。
回复 支持 反对

使用道具 举报

luofeidream 发表于 2016-1-15 11:37:12 | 显示全部楼层
二维的用DFS,加个visited标记就可以了吧,O(M * N)
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-1-16 08:27:32 | 显示全部楼层
本帖最后由 dietpepsi 于 2016-1-16 08:29 编辑

1D的扫一遍就可以了,O(n)时间O(1)空间.
2D的最简单就是DFS加Memoization。因为每一个cell只计算一次,所以是O(mn)

2D的问题整个Matrix可以看成一个m x n个节点的有向图。相邻节点如果a > b则存在一条边 a 指向 b。那么实际上就是问这个有向无环图里面最长的路径是多少。
所以即可以用DFS加Memo来做,也可以拓扑排序加DP来做。
无论哪种都是每个节点只计算一次,所以复杂度都是O(mn).
回复 支持 反对

使用道具 举报

 楼主| atwoodwang0918 发表于 2016-1-16 09:39:30 | 显示全部楼层
本帖最后由 atwoodwang0918 于 2016-1-16 09:41 编辑
dietpepsi 发表于 2016-1-16 08:27
1D的扫一遍就可以了,O(n)时间O(1)空间.
2D的最简单就是DFS加Memoization。因为每一个cell只计算一次,所 ...

请问用拓扑排序的话具体怎么做呢??怎么构造图结构呢呢??
回复 支持 反对

使用道具 举报

luofeidream 发表于 2016-1-16 09:49:28 | 显示全部楼层
atwoodwang0918 发表于 2016-1-16 09:39
请问用拓扑排序的话具体怎么做呢??怎么构造图结构呢呢??

楼上说的很清楚了呀,a > b 就建立a -> b 的edge
回复 支持 反对

使用道具 举报

dietpepsi 发表于 2016-1-16 12:27:51 | 显示全部楼层
atwoodwang0918 发表于 2016-1-16 09:39
请问用拓扑排序的话具体怎么做呢??怎么构造图结构呢呢??

是这样,不用实际构造图,对于每一个节点你都可以在O(1)的时间内找到他的父和子,所以这个matrix本身就包含图的信息了。

你需要的是一个记录出度的matrix。先过一遍,计算所有节点的出度。然后将出度为零的节点(即叶子)放到一个队列里,这是第一层叶子。

循环,将队列里的节点拿出来,减少它的父(就是有边指向它)的节点的出度,即相当于删除此叶子。
删的时候,如果父的出度为零了, 将它放入一个新的队列里,它是下一层的叶子。

直到没有新的叶子为止。

一共有多少层就是答案。

你可以参考LeetCode上Minimum Height Tree那道题,思想是一样滴。
回复 支持 反对

使用道具 举报

ninacc 发表于 2016-1-16 12:52:23 | 显示全部楼层
第二题其实就是经典的滑雪问题,做记忆化搜索,可以搜POJ 1088
回复 支持 反对

使用道具 举报

 楼主| atwoodwang0918 发表于 2016-1-18 03:39:05 | 显示全部楼层
dietpepsi 发表于 2016-1-16 12:27
是这样,不用实际构造图,对于每一个节点你都可以在O(1)的时间内找到他的父和子,所以这个matrix本身就包 ...

懂了 太感谢了!!讲解的很详细!!
回复 支持 反对

使用道具 举报

 楼主| atwoodwang0918 发表于 2016-1-18 03:39:23 | 显示全部楼层
ninacc 发表于 2016-1-16 12:52
第二题其实就是经典的滑雪问题,做记忆化搜索,可以搜POJ 1088

谢谢!!!
回复 支持 反对

使用道具 举报

niel_hu 发表于 2016-2-17 08:03:51 | 显示全部楼层
楼主第一题的解法不对,如果递增序列不是相邻的就错了,如果是相邻的也就没必要dp, 只要扫一边即可。
https://leetcode.com/problems/longest-increasing-subsequence/
最优解 O(n logn)

O(n^2) 解法:
  1. int lengthOfLIS(vector<int>& nums) {
  2.         if (nums.size() == 0) {
  3.             return 0;
  4.         }
  5.         
  6.         vector<int> dp(nums.size(), 1);
  7.         int ans = 1;
  8.         for (int i = 0; i < nums.size(); i++) {
  9.             for (int j = 0; j < i; j++) {
  10.                 if (nums[j] < nums[i]) {
  11.                     dp[i] = max(dp[i], dp[j] + 1);
  12.                     ans = max(ans, dp[i]);
  13.                 }
  14.             }
  15.         }
  16.         return ans;
  17.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| atwoodwang0918 发表于 2016-2-17 10:34:13 | 显示全部楼层
niel_hu 发表于 2016-2-17 08:03
楼主第一题的解法不对,如果递增序列不是相邻的就错了,如果是相邻的也就没必要dp, 只要扫一边即可。
http ...

恩恩 我一开始题目理解错了 后来才发现是leetcode上面的原题~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 00:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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