注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex135 Candy  

2015-05-29 22:48:43|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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?

思路比较暴力,先确定什么地方该放1,出现一个谷底的时候就应该放1,然后从左往右扫一遍,上台阶的时候就加1,ratings值不变的时候count重置为1.这是我比较稚嫩的代码,我居然调通了,~~~
别人的思路貌似也是这样,不过代码就简洁多了,附在参考后面,以后仔细拜读。

class Solution {
public:
int candy(vector<int>& ratings) {
return traverse(ratings);
}
int traverse(vector<int> ratings)
{
/*
* 需要扫描三遍数据
* 第一遍,确定 ratings分布的谷底,题目的要求是与自己相邻的ratings,
* 只有比自己大的时候分配的糖果多,所以说相等的时候也没有用 所以遍历到i的时候 ratings[i]<=ratings[i+1] &&ratings[i]<=ratings[i-1]
* 两边的时候特殊处理一下
*
* 第二遍的时候从peak开始找上升的部分,这一部分正向扫描(我的代码写的有些冗余,以后再看的时候再修改吧)
* 记住每次扫描的时候不能改变peak位置的值,一定要限定,因为在元素相等的时候会发生这种坑爹的情况,例如 1 2 2 或者 2 2 1
* 这一个部分把每个peak之间上升的部分给解决了,每上一个台阶 +1 ,当遇到前后两个元素相等的时候count 要置为1,然后重新上台阶
* 当遇到visited过的数据之后,取当前值和count中较大的,接着break,不能往后走了
*
* 接着逆向扫描第三遍
* 过程和第二遍是一样的,只不过看的方向是从后往前,上升了
*
* 复杂度是线性的,还有一些很简洁的算法,目前暂时不写了
*/
int len = ratings.size();
vector<int> height(len,0);
vector<bool>visited(len,false);
vector<bool>peak(len, false);
if (ratings[0] <= ratings[1])
{
height[0] = 1;
visited[0] = true;
peak[0] = true;
}

if (ratings[len - 1] <= ratings[len - 2])
{
height[len-1] = 1;
visited[len - 1] = true;
peak[len-1] = true;
}

int i;
for (i = 1; i < len - 1; i++)
{
if (ratings[i] <= ratings[i - 1] && ratings[i] <= ratings[i + 1])
{
height[i] = 1;
visited[i] = true;
peak[i] = true;
}
}
//正向扫一遍
i = 0;
int count = 0;
while (i < len)
{
while (i<len && height[i] != 1)
i++;
count = 1;
while ((i + 1)<len && ratings[i + 1] >= ratings[i]&&!peak[i+1])
{
//peak就是第一次画好的边界,不能越过去
if (ratings[i] == ratings[i + 1])
{
if (visited[i + 1])
{
//如果以前访问过,这里求一个较大的直接退出
height[i + 1] = myMax(count,height[i+1]);
break;
}
else
{
count = 1;
//没有访问过,台阶是平的,count重置
height[i + 1] = count;
}

}
else
{
count++;
//上升部分 count不断上台阶
if (visited[i + 1])
{
height[i + 1] = myMax(count, height[i + 1]);
break;
}
else
height[i + 1] = count;
}
visited[i + 1] = true;
i++;
}
i++;
}

//反向扫描一遍
i = len - 1;
while (i >=0)
{
while (i>=0 && height[i] != 1)
i--;
count = 1;
while ((i - 1) >= 0 && ratings[i - 1] >= ratings[i] && !peak[i - 1])
{
//peak就是第一次画好的边界,不能越过去
if (ratings[i] == ratings[i - 1])
{
if (visited[i - 1])
{
height[i - 1] = myMax(count, height[i - 1]);
break;
}
else
{
//没有访问过,台阶是平的,count重置
count = 1;
height[i - 1] = count;
}
}
else
{
count++;
//逆向上升部分 count不断上台阶
if (visited[i - 1])
{
height[i - 1] = myMax(count, height[i - 1]);
break;
}
else
height[i - 1] = count;
}
visited[i - 1] = true;
i--;
}
i--;
}
int sum = 0;
for (i = 0; i < len; i++)
sum += height[i];
return sum;

}
int myMin(int a,int b)
{
return a > b ? b : a;
}
int myMax(int a, int b)
{
return a > b ? a : b;
}
};


参考
http://blog.csdn.net/lanxu_yy/article/details/17752273
  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017