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

想问问大家,你在面试中遇到过leetcode上hard难度或者更难的算法题吗?

🔗
bluestarwing 2015-7-11 01:42:43 | 只看该作者
全局:
word ladderII好难啊...
回复

使用道具 举报

🔗
 楼主| zhuli19901106 2015-7-11 13:19:14 | 只看该作者
全局:
本帖最后由 zhuli19901106 于 2015-7-11 14:16 编辑
stellari 发表于 2015-7-10 21:05
那是,这道题我可是花了好长时间写出来的,怎么能让你们轻易通过

话说怎么确定一个问题可达到的最优复杂度?比如Maximum Subarray III这题,O(N^3)的DP解很快就能想出来,但我想了一个多钟头也没想出O(N^2)的,网上搜了也没有找到平方的解。
有什么比较严谨的办法证明有或者没有吗?难道只能靠脑子想?
更新:刚刚搜了搜论文,说有O(n + k)的解。但是限定条件不同,论文中允许子数组重叠,所以和这个不是一个问题。
再更新:花了俩钟头,终于搞出了O(N * K)的DP解法,怒贴代码~~
  1. // O(k * n) DP with O(n) space, yes!
  2. #include <algorithm>
  3. #include <climits>
  4. using namespace std;

  5. class Solution {
  6. public:
  7.     /**
  8.      * @param nums: A list of integers
  9.      * @param k: An integer denote to find k non-overlapping subarrays
  10.      * @return: An integer denote the sum of max k non-overlapping subarrays
  11.      */
  12.     int maxSubArray(vector<int> nums, int k) {
  13.         vector<int> &a = nums;
  14.         int n = a.size();
  15.         if (k <= 0 || k > n) {
  16.             return 0;
  17.         }
  18.         vector<vector<int> > dp(2, vector<int>(n, 0));
  19.         vector<int> mx(n, 0);
  20.         int i, j;
  21.         int f, nf;
  22.         
  23.         mx[0] = dp[0][0] = a[0];
  24.         for (i = 1; i < n; ++i) {
  25.             dp[0][i] = max(dp[0][i - 1], 0) + a[i];
  26.         }
  27.         mx[0] = dp[0][0];
  28.         for (i = 1; i < n; ++i) {
  29.             mx[i] = max(mx[i - 1], dp[0][i]);
  30.         }
  31.         
  32.         f = 1;
  33.         nf = !f;
  34.         for (i = 1; i < k; ++i) {
  35.             dp[f][i] = dp[nf][i - 1] + a[i];
  36.             for (j = i + 1; j < n; ++j) {
  37.                 dp[f][j] = max(dp[f][j - 1], mx[j - 1]) + a[j];
  38.             }
  39.             mx[i] = dp[f][i];
  40.             for (j = i + 1; j < n; ++j) {
  41.                 mx[j] = max(mx[j - 1], dp[f][j]);
  42.             }
  43.             f = !f;
  44.             nf = !f;
  45.         }
  46.         return mx[n - 1];
  47.     }
  48. };
复制代码
回复

使用道具 举报

全局:
stellari 发表于 2015-7-10 21:05
那是,这道题我可是花了好长时间写出来的,怎么能让你们轻易通过

我在13年10月左右面微软OS组,第四面挂在这题。。
回复

使用道具 举报

🔗
57656929bb 2015-7-11 15:33:23 | 只看该作者
全局:
这题还谁出的。。。。geekforgeek上一百年前的原题。。。。
回复

使用道具 举报

🔗
 楼主| zhuli19901106 2015-7-11 15:42:50 | 只看该作者
全局:
本帖最后由 zhuli19901106 于 2015-7-11 15:57 编辑
57656929bb 发表于 2015-7-11 15:33
这题还谁出的。。。。geekforgeek上一百年前的原题。。。。

我说的是leetcode上那题是stellari添加的。。另外,咱能愉快地交谈吗,一百年前geekforgeek还没开张
没说leetcode所有题都是原创,比如LCA问题才刚刚添加,然而别的OJ都见过无数遍了
回复

使用道具 举报

🔗
stellari 2015-7-11 17:31:20 | 只看该作者
全局:
本帖最后由 stellari 于 2015-7-11 17:34 编辑
zhuli19901106 发表于 2015-7-11 13:19
话说怎么确定一个问题可达到的最优复杂度?比如Maximum Subarray III这题,O(N^3)的DP解很快就能想出来, ...

应该是不存在“确定一个问题可达到的最优复杂度”的一般方法的,否则我们也不需要一道一道地去证明哪些问题是NP-Hard的了。

Maximum Subarray III这题的思路和Sell/Buy Stock IV的思路基本一样。维护两个二维DP数组,分别是:
global[ k ][ i ] -> 子数组0~i中,取k个subarray能达到的最大值。
local[ k ][ i ]  -> 子数组0~i 中,取k个subarray,且第k个subarray一定包含元素 i 时能达到的最大值。

最后你会发现,local和global的状态转移方程都分别依赖于对方。并且每个元素都能在O(1)时间内算出,因此最后总时间是O(N*K)。
回复

使用道具 举报

🔗
 楼主| zhuli19901106 2015-7-11 17:32:44 | 只看该作者
全局:
stellari 发表于 2015-7-11 17:31
应该是不存在“确定一个问题可达到的最优复杂度”的一般方法的,否则我们也不需要一道一道地去证明哪些问 ...

嗯,就是这样。
局部最优和全局最优交替更新。
回复

使用道具 举报

🔗
stellari 2015-7-11 17:36:48 | 只看该作者
全局:
zhuli19901106 发表于 2015-7-11 13:19
话说怎么确定一个问题可达到的最优复杂度?比如Maximum Subarray III这题,O(N^3)的DP解很快就能想出来, ...

赞,顺便贴一个我的版本:
  1.     int maxSubArray(vector<int> nums, int k) {
  2.         // write your code here
  3.         int N = nums.size();
  4.         vector<vector<int> > local(k+1, vector<int>(N+1, 0));
  5.         vector<vector<int> > global(k+1, vector<int>(N+1, 0));
  6.         
  7.         
  8.         for (int ic = 1; ic <= N; ++ic) {
  9.             for (int ir = 1; ir <= k; ++ir) {
  10.                 local[ir][ic] = max(global[ir-1][ic-1], local[ir][ic-1]) + nums[ic-1];
  11.                 if (ir < ic)
  12.                     global[ir][ic] = max(local[ir][ic], global[ir][ic-1]);
  13.                 else
  14.                     global[ir][ic] = local[ir][ic];
  15.             }
  16.         }
  17.         
  18.         return global[k][N];
  19.     }
复制代码
回复

使用道具 举报

🔗
bluesky6 2015-7-11 19:04:44 | 只看该作者
全局:
謝謝大家分享
回复

使用道具 举报

🔗
dmsehuang 2015-7-12 04:22:57 | 只看该作者
全局:
zhuli19901106 发表于 2015-7-11 13:19
话说怎么确定一个问题可达到的最优复杂度?比如Maximum Subarray III这题,O(N^3)的DP解很快就能想出来, ...

看来leetcode现在是每个账户公开的题目不一样?比如说很早之前,有个同学告诉我leetcode有一道题目是数n里面含有数字为1的总数,我是前天才看到这道题目的。同样,你说的maximum subarray III我也没有看到啊。

点评

好像应该是lintcode  发表于 2015-7-12 04:43
回复

使用道具 举报

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

本版积分规则

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