Redian新闻
>
孩子,你的药我买不起了
avatar
孩子,你的药我买不起了# Parenting - 为人父母
h*e
1
看了几个人的没发现太好的解法,自己的O(n) time const space又有点长46行 大家有
没有
好点的解法。
avatar
h*r
2
“妈妈,再爱我一次吧!趁我现在身体还能行,我给您磕三个头,您辛苦了”跪在病床
上的管继泽头磕下去久久没有抬起头来,这个年仅16岁的男孩身上承受了太多的磨难,
因为有妈妈一直陪伴,才有些许的温暖。管继泽今年16岁,患有再生障碍性贫血,是辽
宁省丹东市爱河上堡村人,目前在北京大学人民医院接受治疗。
因为是慢性,医生建议先保守采取中西医结合治疗,直到2017年6月病情加重开始输血
,且越来越频繁,医生告知没办法必须尽快移植了,在坚定无论如何都要救孩子的信念
以后,李娜开始凑移植费用。当他了解到自己目前的情况后,他深深的知道母亲所面对
的困难,他没有什么愿望,只求妈妈能再爱他一次。
早在2008年,李娜就和丈夫管锐离婚了,并且是净身出户只要了儿子,跟她前夫基本没
有任何联系。那时候为了给孩子多存点钱,李娜选择外出打工。2014年,小泽突然高烧
不止,浑身疼痛,在当地医院查血项发现异常但也无法确诊到底是何病,在外务工的李
娜几经打听后让前夫带着孩子去天津血研所做骨穿检查,知道结果后李娜立马赶回了老
家,从此便没有离开小泽半步。
再生障碍性贫血移植康复的几率非常大,很多患者在移植以后都能回归到正常生活,李
娜以为熬过了人间劫难便能迎来曙光,可没曾想最可怕的事情发生了,移植出仓到现在
3个多月了,小泽的细胞没有上涨,仍靠血制品续命,一点造血功能都没有,也就是说
移植失败了。
“我想让他吃药的,但是我是真的没有钱买了啊,现在吃的好多药是病友送的,吃药能
让他少点痛苦,看着他那么难受,我更难受”李娜哽咽的说,她悄悄的去询问过医生病
情,医生也只是说“准备足够的资金,再谈下一步的治疗方案吧”。可是她没钱了,这
个是所有人都知道的事,可眼下急需做二次移植的准备。
2018年4月10号,小泽在北京大学人民医院进仓,在仓里因为上大疗后发烧,心包积液
,拉肚各种症状都出现且严重,期间签了2次病危书,短短20几天就花了近44万,也就
是说李娜一家9个月才凑够的钱在1个月不到就花光了。更可怕的是,5月6号出仓后小泽
出现肠排、皮排、肝排、巨细胞病毒,几乎要了他半条命。
那时候一天拉血十几次,肛门皮肤破皮禁食40天,肚子绞痛到两眼发直,浑身颤抖说不
出话,只能靠打吗啡来止疼。皮排导致皮肤大面积发黑脱皮,一天费用一万多,直到一
个半月以后才慢慢缓解。这一个多月,是小泽一生中最为痛苦的日子,也是李娜透支了
所有亲戚朋友,人缘用尽达到极限才挺过去的日子,母子俩终身难忘。
avatar
h*e
3
discuss 里面有一个, 但是感觉不大好。。
大家上代码的时候尽量 写点小思路,方便他人阅读~~
avatar
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;
}
avatar
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;
}
};
avatar
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; iif (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;
}
avatar
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);

avatar
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)

avatar
w*9
9
r 记录前一个连续上升的最高值,l记录连续下降值,负数,如果上升等与或高与下降
(r+l>=0) 就不比调整了。

【在 h*******e 的大作中提到】
: 看起来不错能写个简单的思路么。
:
: reused

avatar
h*e
10
这个似乎很巧妙阿, 好我再仔细看看你的代码。

【在 w**********9 的大作中提到】
: r 记录前一个连续上升的最高值,l记录连续下降值,负数,如果上升等与或高与下降
: (r+l>=0) 就不比调整了。

avatar
h*e
11
恩,你也看看warmspring99的算法么。

【在 j*****8 的大作中提到】
: 嗯,是,那个O(n)的空间应该可以降到O(1),没想这么多。。
:
: ~~

avatar
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;
}
}
左边扫一遍,右边来一遍
avatar
j*8
13
有个小问题,为啥从零开始分配?题目要求不是至少得要有一个吗?
不过程序是AC了。

【在 h*******e 的大作中提到】
: 恩,你也看看warmspring99的算法么。
avatar
h*e
14
她是求增量,每个元素已经给赋了1了 在sum = ratings.size()的时候。。 再其他的
还没看太清楚~~还在看~~
------------
应该现在明白了

【在 j*****8 的大作中提到】
: 有个小问题,为啥从零开始分配?题目要求不是至少得要有一个吗?
: 不过程序是AC了。

avatar
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;
}
};
avatar
l*e
16
还是解释一下吧
left 表示从 i 开始向左最多能延伸到的点的边界,right 是向右
所以单调区间就是 (left, i] 和 [i, right)
avatar
h*e
17
你的代码一向很好,我明天早上读一下子。

【在 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;

avatar
j*8
18
en 那我就明白了。
班上还是有牛人阿,得多交流学习

【在 h*******e 的大作中提到】
: 她是求增量,每个元素已经给赋了1了 在sum = ratings.size()的时候。。 再其他的
: 还没看太清楚~~还在看~~
: ------------
: 应该现在明白了

avatar
w*9
19
看着很简洁,我也好好学习一下。

【在 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;

avatar
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;
}
avatar
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;

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。