聊聊跟三哥三姐面试和共事的经历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 929|回复: 3
收起左侧

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

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

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

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

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)的
回复 支持 反对

使用道具 举报

全球28万学生4.7分推荐
北美农民 发表于 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 | 显示全部楼层
我一开始也是用楼主的方法的..只不过时间复杂度太大了而已..
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-22 12:41

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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