📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 3577| 回复: 13
跳转到指定楼层
上一主题 下一主题
收起左侧

G家面试 Longest Increasing Subarray 请问有没有更优解

全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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>
复制代码

上一篇:请教f家 task schedule题目follow up
下一篇:关于hash table中remove方法的递归实现问题
推荐
 楼主| 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[i][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[i][j]){
                        int cur = findMax(i+d[0],j+d[1]);
                        max = Math.max(cur,max);
                    }
                }
                longest[i][j]=max+1;
            }
            return longest[i][j];
        }
}


回复

使用道具 举报

推荐
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.     }
复制代码
回复

使用道具 举报

推荐
dietpepsi 2016-1-16 12:27:51 | 只看该作者
全局:
atwoodwang0918 发表于 2016-1-16 09:39
请问用拓扑排序的话具体怎么做呢??怎么构造图结构呢呢??

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

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

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

直到没有新的叶子为止。

一共有多少层就是答案。

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

使用道具 举报

🔗
 楼主| atwoodwang0918 2016-1-13 13:22:12 | 只看该作者
全局:
代码粘贴有问题 Follow up的代码在下面~
回复

使用道具 举报

🔗
微斯渝 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
回复

使用道具 举报

🔗
ninacc 2016-1-16 12:52:23 | 只看该作者
全局:
第二题其实就是经典的滑雪问题,做记忆化搜索,可以搜POJ 1088
回复

使用道具 举报

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

本版积分规则

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