找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1230|回复: 2
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Candy】-【刷题第一弹2014】

[复制链接]

3

主题

5

精华

272

积分

高级会员

Rank: 3Rank: 3

积分
272
发表于 10-10-2014 04:05 PM | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 MengMa 于 12-21-2014 11:54 PM 编辑

快速通道:
oj.leetcode.com/problems/candy/

题目:There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?


本题可以采用两次扫描数组的方法。一次从左到右扫描,找到与前一个邻居比要满足条件的最小糖果数。如果一个人比前面一人rating 高,就在前面一人的糖数+1作为此人的最少糖数。如果小于等于前人,则最小糖数取1,暂时不考虑跟后面人的关系。在第二次扫描的时候,从右到左进行同样的操作,找到满足后向比较关系的最少糖数。最后,对每一个人的前向最小值和后向最小值取max,就是满足条件的最小值了。求所有人总和即可。
  1. public int candy(int[] ratings) {
  2.         final int n = ratings.length;
  3.         int[] leftMin = new int[n];
  4.         int[] rightMin = new int[n];
  5.         
  6.         leftMin[0] = 1;
  7.         rightMin[n - 1] = 1;
  8.         for (int i = 1; i < n; i++) {
  9.             if (ratings【i】 > ratings[i - 1])
  10.                 leftMin【i】 = leftMin[i - 1] + 1;
  11.             else
  12.                 leftMin【i】 = 1;
  13.             
  14.             if (ratings[n - 1 - i] > ratings[n - i])
  15.                 rightMin[n - 1 - i] = rightMin[n - i] + 1;
  16.             else
  17.                 rightMin[n - 1 - i] = 1;
  18.         }
  19.         
  20.         int count = 0;
  21.         for (int i = 0; i < n; i++)
  22.             count += Math.max(leftMin【i】, rightMin【i】);
  23.         return count;
  24.     }
复制代码
复杂度: 时间O(N),空间O(N)

=========点击传送门查看所有题目哟========
             汇总贴 传送门
=================================

本帖被以下淘专辑推荐:

12

主题

5

精华

249

积分

高级会员

Rank: 3Rank: 3

积分
249

最佳新人

发表于 10-21-2014 05:33 PM | 显示全部楼层
思路: 好像这题网上流行的套路都是从左扫一遍,然后再从右扫一遍。rating高的比邻近的rating低的 多发一颗糖。allenus代码以及非常清晰啦。下面发个C++的,有点地方可以优化的是,count可以放在第二个for循环里,减少N-1次循环。

  1.     int candy(vector<int> &ratings) {
  2.         int len = ratings.size();
  3.         vector<int> candy(len, 1);
  4.         int result = 0;
  5.         
  6.         for(int i = 1; i < len; ++i) {
  7.             if(ratings[i] > ratings[i-1]) candy[i] = candy[i-1] + 1;
  8.         }
  9.         for(int i = len-1; i > 0; --i) {
  10.             if(ratings[i-1] > ratings[i]) candy[i-1] = max(candy[i-1], candy[i] + 1);
  11.             result += candy[i];
  12.         }
  13.         result += candy[0];
  14.         
  15.         
  16.         return result;
  17.     }
复制代码


时间跟空间复杂度都是O(N)

点评

但这样把第二次遍历和最后的求和混在一起,可读性会变差吧, 而且所做的工作量基本没有减少,只是把两次循环的工作和到一个循环中了,感觉这样改可以再考虑  发表于 11-18-2014 03:07 AM
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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