一亩三分地论坛

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

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

[Leetcode] Leetcode 里面Candy这道题有一个很长的test case 通不过

[复制链接] |试试Instant~ |关注本帖
mathg 发表于 2014-2-14 03:52:55 | 显示全部楼层 |阅读模式

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

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

x
不知到有没有人有类似的情况。
我的code是这样的:
        public int candy(int[] ratings){
                boolean[] min = new boolean[ratings.length];
                int pre = - 1;
                for(int n = 0; n < ratings.length; n++){
                        if(n == ratings.length - 1){
                                if(pre == -1)
                                        min[n] = true;
                        }
                        else{
                                if(ratings[n] < ratings[n + 1]){
                                        if(pre == -1)
                                                min[n] = true;
                                        pre = 1;
                                }
                                else if(ratings[n] > ratings[n+1])
                                        pre = -1;
                        }
                }
               
                boolean[] smin = new boolean[ratings.length];
                int sub = 1;
                for(int n = ratings.length - 1; n >= 0; n--){
                        if(n == 0){
                                if(sub == 1)
                                        smin[n] = true;
                        }
                        else{
                                if(ratings[n] < ratings[n - 1]){
                                        if(sub == 1)
                                                smin[n] = true;
                                        sub = -1;
                                }
                                else if(ratings[n] > ratings[n-1])
                                        sub = 1;
                        }
                }

                int cindy[] = new int[ratings.length];
                for(int i = 0; i < ratings.length; i++)
                        cindy[i] = 1;
               
                for(int n = 0; n < ratings.length; n++){
                        if(min[n]){
                                cindy[n] = 1;
                                for(int j = n + 1; j < ratings.length; j++){
                                        if(ratings[j] > ratings[j-1]){
                                                if(cindy[j - 1] + 1 > cindy[j])
                                                        cindy[j] = cindy[j-1] + 1;
                                        }
                                        else
                                                break;
                                }
                        }
                }
               
                for(int n = 0; n < ratings.length; n++){
                        if(smin[n]){
                                cindy[n] = 1;
                                for(int j = n - 1; j >= 0; j--){
                                        if(ratings[j] > ratings[j + 1]){
                                                if(cindy[j + 1] + 1 > cindy[j])
                                                        cindy[j]  = cindy[j + 1] + 1;
                                        }
                                        else
                                                break;
                                }
                        }
                }
               
                int sum = 0;
                for(int i = 0; i < ratings.length; i++)
                        sum += cindy[i];
                return sum;
}
adlxk 发表于 2014-2-14 07:14:41 | 显示全部楼层
没仔细看楼主的逻辑,但复杂度大概是time O(n^2) space O(n)。。这题时间上可以做到O(n)的
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-2-14 07:33:49 | 显示全部楼层
public int candy(int[] ratings) {
    if (ratings == null || ratings.length == 0) return 0;
    int head = 0;
    int len;
    int result = 0;
    int first = 0;
    int last = 1;
   
    while (head < ratings.length) {
      len = 1;
      while (head + len < ratings.length && ratings[head + len] < ratings[head + len - 1]) ++ len;
      first = (head > 0 && ratings[head] > ratings[head - 1]) ? Math.max(last + 1, len) : len;
      result += first + (len - 1) * len /2;
      last = (len > 1 ? 1 : first);
      head += len;
    }

    return result;
  }
}
回复 支持 反对

使用道具 举报

kelvinzhong 发表于 2014-2-14 08:37:24 | 显示全部楼层
我一开始也是用楼主的方法的..只不过时间复杂度太大了而已..
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 05:26

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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