h*r
2 楼
“妈妈,再爱我一次吧!趁我现在身体还能行,我给您磕三个头,您辛苦了”跪在病床
上的管继泽头磕下去久久没有抬起头来,这个年仅16岁的男孩身上承受了太多的磨难,
因为有妈妈一直陪伴,才有些许的温暖。管继泽今年16岁,患有再生障碍性贫血,是辽
宁省丹东市爱河上堡村人,目前在北京大学人民医院接受治疗。
因为是慢性,医生建议先保守采取中西医结合治疗,直到2017年6月病情加重开始输血
,且越来越频繁,医生告知没办法必须尽快移植了,在坚定无论如何都要救孩子的信念
以后,李娜开始凑移植费用。当他了解到自己目前的情况后,他深深的知道母亲所面对
的困难,他没有什么愿望,只求妈妈能再爱他一次。
早在2008年,李娜就和丈夫管锐离婚了,并且是净身出户只要了儿子,跟她前夫基本没
有任何联系。那时候为了给孩子多存点钱,李娜选择外出打工。2014年,小泽突然高烧
不止,浑身疼痛,在当地医院查血项发现异常但也无法确诊到底是何病,在外务工的李
娜几经打听后让前夫带着孩子去天津血研所做骨穿检查,知道结果后李娜立马赶回了老
家,从此便没有离开小泽半步。
再生障碍性贫血移植康复的几率非常大,很多患者在移植以后都能回归到正常生活,李
娜以为熬过了人间劫难便能迎来曙光,可没曾想最可怕的事情发生了,移植出仓到现在
3个多月了,小泽的细胞没有上涨,仍靠血制品续命,一点造血功能都没有,也就是说
移植失败了。
“我想让他吃药的,但是我是真的没有钱买了啊,现在吃的好多药是病友送的,吃药能
让他少点痛苦,看着他那么难受,我更难受”李娜哽咽的说,她悄悄的去询问过医生病
情,医生也只是说“准备足够的资金,再谈下一步的治疗方案吧”。可是她没钱了,这
个是所有人都知道的事,可眼下急需做二次移植的准备。
2018年4月10号,小泽在北京大学人民医院进仓,在仓里因为上大疗后发烧,心包积液
,拉肚各种症状都出现且严重,期间签了2次病危书,短短20几天就花了近44万,也就
是说李娜一家9个月才凑够的钱在1个月不到就花光了。更可怕的是,5月6号出仓后小泽
出现肠排、皮排、肝排、巨细胞病毒,几乎要了他半条命。
那时候一天拉血十几次,肛门皮肤破皮禁食40天,肚子绞痛到两眼发直,浑身颤抖说不
出话,只能靠打吗啡来止疼。皮排导致皮肤大面积发黑脱皮,一天费用一万多,直到一
个半月以后才慢慢缓解。这一个多月,是小泽一生中最为痛苦的日子,也是李娜透支了
所有亲戚朋友,人缘用尽达到极限才挺过去的日子,母子俩终身难忘。
上的管继泽头磕下去久久没有抬起头来,这个年仅16岁的男孩身上承受了太多的磨难,
因为有妈妈一直陪伴,才有些许的温暖。管继泽今年16岁,患有再生障碍性贫血,是辽
宁省丹东市爱河上堡村人,目前在北京大学人民医院接受治疗。
因为是慢性,医生建议先保守采取中西医结合治疗,直到2017年6月病情加重开始输血
,且越来越频繁,医生告知没办法必须尽快移植了,在坚定无论如何都要救孩子的信念
以后,李娜开始凑移植费用。当他了解到自己目前的情况后,他深深的知道母亲所面对
的困难,他没有什么愿望,只求妈妈能再爱他一次。
早在2008年,李娜就和丈夫管锐离婚了,并且是净身出户只要了儿子,跟她前夫基本没
有任何联系。那时候为了给孩子多存点钱,李娜选择外出打工。2014年,小泽突然高烧
不止,浑身疼痛,在当地医院查血项发现异常但也无法确诊到底是何病,在外务工的李
娜几经打听后让前夫带着孩子去天津血研所做骨穿检查,知道结果后李娜立马赶回了老
家,从此便没有离开小泽半步。
再生障碍性贫血移植康复的几率非常大,很多患者在移植以后都能回归到正常生活,李
娜以为熬过了人间劫难便能迎来曙光,可没曾想最可怕的事情发生了,移植出仓到现在
3个多月了,小泽的细胞没有上涨,仍靠血制品续命,一点造血功能都没有,也就是说
移植失败了。
“我想让他吃药的,但是我是真的没有钱买了啊,现在吃的好多药是病友送的,吃药能
让他少点痛苦,看着他那么难受,我更难受”李娜哽咽的说,她悄悄的去询问过医生病
情,医生也只是说“准备足够的资金,再谈下一步的治疗方案吧”。可是她没钱了,这
个是所有人都知道的事,可眼下急需做二次移植的准备。
2018年4月10号,小泽在北京大学人民医院进仓,在仓里因为上大疗后发烧,心包积液
,拉肚各种症状都出现且严重,期间签了2次病危书,短短20几天就花了近44万,也就
是说李娜一家9个月才凑够的钱在1个月不到就花光了。更可怕的是,5月6号出仓后小泽
出现肠排、皮排、肝排、巨细胞病毒,几乎要了他半条命。
那时候一天拉血十几次,肛门皮肤破皮禁食40天,肚子绞痛到两眼发直,浑身颤抖说不
出话,只能靠打吗啡来止疼。皮排导致皮肤大面积发黑脱皮,一天费用一万多,直到一
个半月以后才慢慢缓解。这一个多月,是小泽一生中最为痛苦的日子,也是李娜透支了
所有亲戚朋友,人缘用尽达到极限才挺过去的日子,母子俩终身难忘。
h*e
3 楼
discuss 里面有一个, 但是感觉不大好。。
大家上代码的时候尽量 写点小思路,方便他人阅读~~
大家上代码的时候尽量 写点小思路,方便他人阅读~~
j*8
4 楼
我的28行,不过看着也挺繁琐的。思路就是碰到递增的就一直加1,递减的话一直减,
碰到往上走时就回头check一下看那段递减的需不需要调整(负数,或者最小的不是1)
public int candy(int[] ratings) {
if(ratings == null || ratings.length == 0) return 0;
int len = ratings.length;
int[] num = new int[len];
for(int i = 0; i < len; i++) {
if(i == 0) num[i] = 1;
else {
if(ratings[i] > ratings[i-1]) num[i] = num[i-1] + 1;
else if(ratings[i] == ratings[i-1]) num[i] = 1;
else {
num[i] = num[i-1] > 1 ? 1 : num[i-1] - 1;
if(i == len - 1 || ratings[i] <= ratings[i+1])
if(num[i] != 1) adjust(ratings, num, i);
}
}
}
int result = 0;
for(int i = 0; i < len; i++) result += num[i];
return result;
}
private void adjust(int[] ratings, int[] num, int pos) {
int diff = 1 - num[pos];
while(pos >= 1 && ratings[pos] < ratings[pos-1]) {
num[pos] += diff;
pos--;
}
if(num[pos] <= num[pos+1]) num[pos] = num[pos+1] + 1;
}
碰到往上走时就回头check一下看那段递减的需不需要调整(负数,或者最小的不是1)
public int candy(int[] ratings) {
if(ratings == null || ratings.length == 0) return 0;
int len = ratings.length;
int[] num = new int[len];
for(int i = 0; i < len; i++) {
if(i == 0) num[i] = 1;
else {
if(ratings[i] > ratings[i-1]) num[i] = num[i-1] + 1;
else if(ratings[i] == ratings[i-1]) num[i] = 1;
else {
num[i] = num[i-1] > 1 ? 1 : num[i-1] - 1;
if(i == len - 1 || ratings[i] <= ratings[i+1])
if(num[i] != 1) adjust(ratings, num, i);
}
}
}
int result = 0;
for(int i = 0; i < len; i++) result += num[i];
return result;
}
private void adjust(int[] ratings, int[] num, int pos) {
int diff = 1 - num[pos];
while(pos >= 1 && ratings[pos] < ratings[pos-1]) {
num[pos] += diff;
pos--;
}
if(num[pos] <= num[pos+1]) num[pos] = num[pos+1] + 1;
}
h*e
5 楼
楼上做的挺好,只是多用了O(n) 的space, 我也得把我自己的算法帖一下,我的就是
check 上升下降的转折点,然后把 所有单调上升, 单调下降, 单调水平的部分拿出
来 把他们变成最小为一的上升或者下降序列 或者水平序列但是 单调性不变 用等差数
列求和 求部分和, 唯一tricky的地方就是 转折点需要取两边的单调序列的最大值~~~
one pass 不回头查的,空间时间复杂性都不错,但是就是代码太长了, 逻辑也不那
么清晰,还有没有时间空间复杂度类似的,但是思路或者代码比我这个好一些的。减到
了37行现在。
class Solution {
public:
int compare_int(int preVal, int val)
{ return preVal < val ? 1: (preVal > val? -1: 0); }
int candy(vector &ratings) {
int dirVal = 0, preDirVal = -2, preIndex = 0, curIndex, totSum = 0,
preEdge = 1;
for(int rateI = 1; rateI <= ratings.size(); ++ rateI)
{
int val, preVal = ratings[rateI-1];
if(rateI != ratings.size())
{
val = ratings[rateI];
dirVal = compare_int(preVal, val);
}
if(rateI == ratings.size() || preDirVal != -2 && preDirVal !=
dirVal )
{
curIndex = rateI -1;
int size = curIndex - preIndex + 1, newSum = 0;
int frontEdge, backEdge, inc;
if(preDirVal == 1)
{ frontEdge = 1; backEdge = size; inc = 1; }
else if(preDirVal == -1)
{ frontEdge = size; backEdge =1; inc = -1; }
else
{ frontEdge = backEdge = 1; inc = 0; }
totSum += frontEdge * size + size * (size -1 ) /2 * inc +
max(preEdge -frontEdge, 0)
- (rateI != ratings.size()? backEdge: 0);
preEdge = backEdge;
preIndex = curIndex;
}
preDirVal = dirVal;
}
return totSum;
}
};
check 上升下降的转折点,然后把 所有单调上升, 单调下降, 单调水平的部分拿出
来 把他们变成最小为一的上升或者下降序列 或者水平序列但是 单调性不变 用等差数
列求和 求部分和, 唯一tricky的地方就是 转折点需要取两边的单调序列的最大值~~~
one pass 不回头查的,空间时间复杂性都不错,但是就是代码太长了, 逻辑也不那
么清晰,还有没有时间空间复杂度类似的,但是思路或者代码比我这个好一些的。减到
了37行现在。
class Solution {
public:
int compare_int(int preVal, int val)
{ return preVal < val ? 1: (preVal > val? -1: 0); }
int candy(vector
int dirVal = 0, preDirVal = -2, preIndex = 0, curIndex, totSum = 0,
preEdge = 1;
for(int rateI = 1; rateI <= ratings.size(); ++ rateI)
{
int val, preVal = ratings[rateI-1];
if(rateI != ratings.size())
{
val = ratings[rateI];
dirVal = compare_int(preVal, val);
}
if(rateI == ratings.size() || preDirVal != -2 && preDirVal !=
dirVal )
{
curIndex = rateI -1;
int size = curIndex - preIndex + 1, newSum = 0;
int frontEdge, backEdge, inc;
if(preDirVal == 1)
{ frontEdge = 1; backEdge = size; inc = 1; }
else if(preDirVal == -1)
{ frontEdge = size; backEdge =1; inc = -1; }
else
{ frontEdge = backEdge = 1; inc = 0; }
totSum += frontEdge * size + size * (size -1 ) /2 * inc +
max(preEdge -frontEdge, 0)
- (rateI != ratings.size()? backEdge: 0);
preEdge = backEdge;
preIndex = curIndex;
}
preDirVal = dirVal;
}
return totSum;
}
};
w*9
6 楼
我这个解法也》30行,
int candy(vector &ratings) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
int sum = ratings.size();
int r=0, l=0, nsum=0;
for (int i=1; i if (ratings[i]>=ratings[i-1]) {
if (l<0) {
sum += -1*(nsum-l);
if (r+l<0) sum += -1*(r+l);
l=0;
nsum = 0;
r= (ratings[i]==ratings[i-1]) ? 0:1;
sum += r;
}
else {
if (ratings[i]>ratings[i-1]) ++r;
else r=0;
sum += r;
}
}
else {
--l;
nsum += l;
}
}
if (l<0) sum += -1*(nsum-l);
if (r+l<0) sum += -1*(r+l);
return sum;
}
int candy(vector
// Note: The Solution object is instantiated only once and is reused
by each test case.
int sum = ratings.size();
int r=0, l=0, nsum=0;
for (int i=1; i
if (l<0) {
sum += -1*(nsum-l);
if (r+l<0) sum += -1*(r+l);
l=0;
nsum = 0;
r= (ratings[i]==ratings[i-1]) ? 0:1;
sum += r;
}
else {
if (ratings[i]>ratings[i-1]) ++r;
else r=0;
sum += r;
}
}
else {
--l;
nsum += l;
}
}
if (l<0) sum += -1*(nsum-l);
if (r+l<0) sum += -1*(r+l);
return sum;
}
h*e
7 楼
看起来不错能写个简单的思路么。
reused
【在 w**********9 的大作中提到】
: 我这个解法也》30行,
: int candy(vector &ratings) {
: // Note: The Solution object is instantiated only once and is reused
: by each test case.
: int sum = ratings.size();
: int r=0, l=0, nsum=0;
: for (int i=1; i : if (ratings[i]>=ratings[i-1]) {
: if (l<0) {
: sum += -1*(nsum-l);
reused
【在 w**********9 的大作中提到】
: 我这个解法也》30行,
: int candy(vector
: // Note: The Solution object is instantiated only once and is reused
: by each test case.
: int sum = ratings.size();
: int r=0, l=0, nsum=0;
: for (int i=1; i
: if (l<0) {
: sum += -1*(nsum-l);
j*8
8 楼
嗯,是,那个O(n)的空间应该可以降到O(1),没想这么多。。
~~
【在 h*******e 的大作中提到】
: 楼上做的挺好,只是多用了O(n) 的space, 我也得把我自己的算法帖一下,我的就是
: check 上升下降的转折点,然后把 所有单调上升, 单调下降, 单调水平的部分拿出
: 来 把他们变成最小为一的上升或者下降序列 或者水平序列但是 单调性不变 用等差数
: 列求和 求部分和, 唯一tricky的地方就是 转折点需要取两边的单调序列的最大值~~~
: one pass 不回头查的,空间时间复杂性都不错,但是就是代码太长了, 逻辑也不那
: 么清晰,还有没有时间空间复杂度类似的,但是思路或者代码比我这个好一些的。减到
: 了37行现在。
: class Solution {
: public:
: int compare_int(int preVal, int val)
~~
【在 h*******e 的大作中提到】
: 楼上做的挺好,只是多用了O(n) 的space, 我也得把我自己的算法帖一下,我的就是
: check 上升下降的转折点,然后把 所有单调上升, 单调下降, 单调水平的部分拿出
: 来 把他们变成最小为一的上升或者下降序列 或者水平序列但是 单调性不变 用等差数
: 列求和 求部分和, 唯一tricky的地方就是 转折点需要取两边的单调序列的最大值~~~
: one pass 不回头查的,空间时间复杂性都不错,但是就是代码太长了, 逻辑也不那
: 么清晰,还有没有时间空间复杂度类似的,但是思路或者代码比我这个好一些的。减到
: 了37行现在。
: class Solution {
: public:
: int compare_int(int preVal, int val)
x*u
12 楼
public class Solution {
public int candy(int[] ratings) {
int num[] = new int[ratings.length];
for (int i = 0; i < ratings.length - 1; i++) {
if (ratings[i+1] > ratings[i]) num[i+1] = num[i] + 1;
}
for (int i = ratings.length - 1; i > 0; i--) {
if (ratings[i-1] > ratings[i]) num[i-1] = Math.max(num[i]+1, num
[i-1]);
}
int sum = 0;
for (int i = 0; i < num.length; i++)
sum += 1 + num[i];
return sum;
}
}
左边扫一遍,右边来一遍
public int candy(int[] ratings) {
int num[] = new int[ratings.length];
for (int i = 0; i < ratings.length - 1; i++) {
if (ratings[i+1] > ratings[i]) num[i+1] = num[i] + 1;
}
for (int i = ratings.length - 1; i > 0; i--) {
if (ratings[i-1] > ratings[i]) num[i-1] = Math.max(num[i]+1, num
[i-1]);
}
int sum = 0;
for (int i = 0; i < num.length; i++)
sum += 1 + num[i];
return sum;
}
}
左边扫一遍,右边来一遍
l*e
15 楼
20- 行 我的 right 是单调不回溯的 所以是 O(n) 时间,O(1) 空间也显然,程序也应
该显然
class Solution {
public:
int candy(vector& ratings) {
int sum = 0;
int left = -1, right = 1;
for (int i = 0; i < ratings.size(); ++i) {
if (i > 0 && ratings[i] <= ratings[i - 1]) {
left = i - 1;
}
right = max(right, i + 1);
while (right < ratings.size() && ratings[right] < ratings[right - 1]) {
++right;
}
sum += max(i - left, right - i);
}
return sum;
}
};
该显然
class Solution {
public:
int candy(vector
int sum = 0;
int left = -1, right = 1;
for (int i = 0; i < ratings.size(); ++i) {
if (i > 0 && ratings[i] <= ratings[i - 1]) {
left = i - 1;
}
right = max(right, i + 1);
while (right < ratings.size() && ratings[right] < ratings[right - 1]) {
++right;
}
sum += max(i - left, right - i);
}
return sum;
}
};
l*e
16 楼
还是解释一下吧
left 表示从 i 开始向左最多能延伸到的点的边界,right 是向右
所以单调区间就是 (left, i] 和 [i, right)
left 表示从 i 开始向左最多能延伸到的点的边界,right 是向右
所以单调区间就是 (left, i] 和 [i, right)
h*e
17 楼
w*9
19 楼
p*r
20 楼
20 行
public int candySimple(int[] ratings){
if(ratings == null || ratings.length == 0) return 0;
if(ratings.length == 1) return 1;
int[] temp = new int[ratings.length];
temp[0] = 1;
for(int i = 1; i < ratings.length; i++){
if(ratings[i] > ratings[i-1])
temp[i] = temp[i-1] + 1;
else temp[i] = 1;
}
temp[ratings.length - 1] = Math.max(1, temp[ratings.length - 1]);
int last = 1, total = temp[ratings.length - 1];
for(int i = ratings.length - 2; i >= 0 ; i--){
if(ratings[i] > ratings[i+1])
last = last + 1;
else last = 1;
temp[i] = Math.max(temp[i], last);
total += temp[i];
}
return total;
}
public int candySimple(int[] ratings){
if(ratings == null || ratings.length == 0) return 0;
if(ratings.length == 1) return 1;
int[] temp = new int[ratings.length];
temp[0] = 1;
for(int i = 1; i < ratings.length; i++){
if(ratings[i] > ratings[i-1])
temp[i] = temp[i-1] + 1;
else temp[i] = 1;
}
temp[ratings.length - 1] = Math.max(1, temp[ratings.length - 1]);
int last = 1, total = temp[ratings.length - 1];
for(int i = ratings.length - 2; i >= 0 ; i--){
if(ratings[i] > ratings[i+1])
last = last + 1;
else last = 1;
temp[i] = Math.max(temp[i], last);
total += temp[i];
}
return total;
}
h*e
21 楼
仔细读了,很赞阿!! O(N)时间 O(1)空间。
【在 l******e 的大作中提到】
: 20- 行 我的 right 是单调不回溯的 所以是 O(n) 时间,O(1) 空间也显然,程序也应
: 该显然
: class Solution {
: public:
: int candy(vector& ratings) {
: int sum = 0;
: int left = -1, right = 1;
: for (int i = 0; i < ratings.size(); ++i) {
: if (i > 0 && ratings[i] <= ratings[i - 1]) {
: left = i - 1;
【在 l******e 的大作中提到】
: 20- 行 我的 right 是单调不回溯的 所以是 O(n) 时间,O(1) 空间也显然,程序也应
: 该显然
: class Solution {
: public:
: int candy(vector
: int sum = 0;
: int left = -1, right = 1;
: for (int i = 0; i < ratings.size(); ++i) {
: if (i > 0 && ratings[i] <= ratings[i - 1]) {
: left = i - 1;
相关阅读
一周多岁的宝宝该怎样带求指导幼儿园小男孩淘气顽皮怎么解?裤子大又躺枪啦!!!我为什么会说个“又”字呢?9月出生的女娃,赶不上公立学校开学,是等一年还是上私立?不好意思问一下,美国哪种卫生巾是棉质的2016年美国大选,你的决定关乎你后代将来 (转载)育儿”的世纪误区:可能从根本上就是错误的(转载)龙永图:从我送外孙女去美国谈谈中国的教育 (转载)怎样培养孩子学习自觉性木兰成长记之一 - 我要去开会虎毒不食子,但人可以食子儿子昨天跑步时狗咬了,狗主人见死不救,怎么告他?木兰成长记之三 - 不得不承认乍寒乍暖之下怎样预防宝宝生病 (转载)当奥运冠军的父母也真是不容易带2岁半娃去Houston签证对于孩子的教育你比较care哪方面有的孩子真想扯过来踢两脚!补充宝宝大脑智慧的食物 (转载)让孩子从网瘾厌学中走出来