📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: atwoodwang0918
跳转到指定楼层
上一主题 下一主题
收起左侧

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

🔗
 楼主| 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上面的原题~
回复

使用道具 举报

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

本版积分规则

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