找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2438|回复: 5
收起左侧

[提问] 29题WA

[复制链接]

32

主题

2

精华

367

积分

高级会员

Rank: 3Rank: 3

积分
367
发表于 3-7-2015 08:40 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
我想问下29题中in order是没有特指的么,升序、降序都可以么,因为一直WA不知道怎么回事。。感觉题意理解错了

22

主题

6

精华

612

积分

超级会员

Rank: 4

积分
612
发表于 3-18-2015 10:00 AM | 显示全部楼层
It should be non-descending.

Scan the whole array twice. One from left to right and find the rightmost index of the sequence, another from right to left to find the leftmost index of the sequence.

  1. class Solution {
  2.         public int getShortestSequenceLength(int [] a) {
  3.                 int n = a.length;
  4.                 int left = -1;
  5.                 int right = -1;
  6.                 int curMax = a[0];
  7.                 int curMin = a[n-1];
  8.                
  9.                 for(int i = 0; i < n; ++i){
  10.                         if(a【i】 > curMax){
  11.                                 curMax = a【i】;
  12.                         }
  13.                         if(a【i】 < curMax){
  14.                                 right = i;
  15.                         }
  16.                 }
  17.                 if(right == -1) return 0;
  18.                
  19.                 for(int i = n-1; i >= 0; --i){
  20.                         if(a【i】 < curMin){
  21.                                 curMin = a【i】;
  22.                         }
  23.                         if(a【i】 > curMin){
  24.                                 left = i;
  25.                         }
  26.                 }
  27.                 return right - left + 1;
  28.         }
  29. }
复制代码

32

主题

2

精华

367

积分

高级会员

Rank: 3Rank: 3

积分
367
 楼主| 发表于 3-18-2015 01:29 PM | 显示全部楼层
timeforce 发表于 3-18-2015 10:00 AM
It should be non-descending.

Scan the whole array twice. One from left to right and find the rig ...

非常感谢,请问你能帮我看下我的代码错哪里了么。。纠结死了
  1. class Solution {
  2. public:
  3.     int getShortestSequenceLength(const vector<int> &a) {
  4.         int n = a.size(), l = -1, r = n - 1;
  5.         // find first left > right
  6.         for (int i = 1; i < n; i++) {
  7.             if (a【i】 < a[i - 1]) {
  8.                 l = i;
  9.                 break;
  10.             }
  11.         }
  12.         if (l == -1)
  13.                 return 0;
  14.                // find last left > right
  15.         for (int i = n - 2; i >= 0; i--) {
  16.             if (a【i】 > a[i + 1]) {
  17.                 r = i;
  18.                 break;
  19.             }
  20.         }
  21.         // find min and max value in this window
  22.         int minNum = a[l], maxNum = a[l];
  23.         for (int i = min(l, r); i <= max(l, r); i++) {
  24.             minNum = min(minNum, a【i】);
  25.             maxNum = max(maxNum, a【i】);
  26.         }
  27.         // find their original places
  28.         for (int i = 0; i < l; i++) {
  29.             if (minNum < a【i】) {
  30.                 l = i;
  31.                 break;
  32.             }
  33.         }
  34.         for (int i = n - 1; i > r; i--) {
  35.             if (maxNum > a【i】) {
  36.                 r = i;
  37.                 break;
  38.             }
  39.         }
  40.         return r - l + 1;
  41.     }
  42. };
复制代码
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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