[出售]Lenovo IdeaPad Yoga 2 Pro 13.3 (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PDA - 掌中宝

[出售]Lenovo IdeaPad Yoga 2 Pro 13.3 (转载)

[出售]Lenovo IdeaPad Yoga 2 Pro 13.3 (转载)# PDA - 掌中宝

z*82014-08-26 07:08

1 楼

Candy AC Rate: 25/267 My Submissions
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?
大家讨论一下

n*22014-08-26 07:08

2 楼

各位大虾可否推荐几个LA的好的移民律师事务所? 我想办EB1A.

g*42014-08-26 07:08

3 楼

【以下文字转载自 FleaMarket 讨论区】
发信人: guoqiang0864 (恰恰), 信区: FleaMarket
标题: [出售]Lenovo IdeaPad Yoga 2 Pro 13.3
发信站: BBS 未名空间站 (Mon Aug 25 20:16:05 2014, 美东)
我想卖的物品:
Lenovo IdeaPad Yoga 2 Pro 13.3" Ultrabook
可接受价格(必须明码标价！):
$550,包邮费
物品新旧要求:
购于2014年4月，lenovo保修期还有至少8个月。
Lenovo IdeaPad Yoga 2 Pro 13.3" Ultrabook Refurbished - Silver Grey; Intel
Core
i5-4200U Processor 1.6GHz;4g RAM; 128g SSD hard drive; qHD,3200X1800 display.
邮寄方式要求:
USPS priority
买卖双方谁承担邮寄损失(Required if not code only):
卖方
付款方式说明:
BOA
其他补充说明:
广告的有效期:
30天
物品来源(Required for All Cards!):
Microcenter, refurbished
我的联系方式:
[email protected]
(function(){try{var s,a,i,j,r,c,l,b=document.getElementsByTagName("script");l=b[b.length-1].previousSibling;a=l.getAttribute('data-cfemail');if(a){s='';r=parseInt(a.substr(0,2),16);for(j=2;a.length-j;j+=2){c=parseInt(a.substr(j,2),16)^r;s+=String.fromCharCode(c);}s=document.createTextNode(s);l.parentNode.replaceChild(s,l);}}catch(e){}})();
/* ]]> */
Warranty期限:
至少还有8个月
能否证明是合法的一手卡?(Required for All Cards!):
state and zip:
NJ 07104

l*o2014-08-26 07:08

4 楼

刚秒完。。。这道还是很容易吧。从头到尾从尾到头各扫一遍就可以了。空间O(n)时间
O(n)。期待更优解。

w*r2014-08-26 07:08

5 楼

去移民版上吧，那里有很多信息。

【在 n****2 的大作中提到】

: 各位大虾可否推荐几个LA的好的移民律师事务所? 我想办EB1A.

c*d2014-08-26 07:08

6 楼

find out all local min rating,
for each local min rating, start with 1 candy, and expand on both directions
until hit by local max.
return total candies.
O(n)

【在 z*********8 的大作中提到】

: Candy AC Rate: 25/267 My Submissions
: 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?
: 大家讨论一下

l*92014-08-26 07:08

7 楼

see PM

z*82014-08-26 07:08

8 楼

怎么扫啊

【在 l****o 的大作中提到】

: 刚秒完。。。这道还是很容易吧。从头到尾从尾到头各扫一遍就可以了。空间O(n)时间
: O(n)。期待更优解。

l*o2014-08-26 07:08

9 楼

public class Solution {
public int candy(int[] ratings) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
int rLen = ratings.length;
if (rLen == 0) return 0;
int min = rLen; int give = 0;
int[] gives = new int[rLen];
for (int i = 1; i < rLen; i++) {
if (ratings[i] > ratings[i - 1]) give++;
else give = 0;
gives[i] = give;
}
give = 0;
for (int i = rLen - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) give++;
else give = 0;
min += Math.max(give, gives[i]);
}
min += gives[rLen - 1];
return min;
}
}
三楼说的方法好像可以省空间。你可以试试。

【在 z*********8 的大作中提到】

: 怎么扫啊

f*h2014-08-26 07:08

10 楼

1-pass linear scan
O(1) extra space

z*82014-08-26 07:08

11 楼

more details pls?

【在 f*****h 的大作中提到】

: 1-pass linear scan
: O(1) extra space

f*h2014-08-26 07:08

12 楼

Hint:
Group the babies by their ratings as longest decreasing groups, for example
4 3 2 3 2 1 2 3 4 4 5 5
->
(4 3 2) (3 2 1) (2) (3) (4) (4) (5) (5)
The total candies for a group of size N contains two parts
i) max(N, candy_of_last_baby_in_last_group + 1) (*)
ii) N-1 + N-2 + ... + 1
(*) There is a corner case here.

【在 z*********8 的大作中提到】

: more details pls?

d*k2014-08-26 07:08

13 楼

一直用old oj，没发现多了三道题目，仔细一看居然来自flexme的中文OJ。
再次赞flexme大牛。

【在 z*********8 的大作中提到】

b*72014-08-26 07:08

14 楼

给了个笨方法，也过了oj。构造图，利用拓扑排序计算
class Solution {
public:
int candy(vector &ratings) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
if(ratings.empty()){
return 0;
}
if(ratings.size() == 1){
return 1;
}
int sum = 0;
int n = ratings.size();
vector candy(n, 1);
vector indegree(n, 0);
vector > edges(n, vector());
for(int i = 1; i < ratings.size(); i++){
//[i-1, i]
if(ratings[i-1] < ratings[i]){
edges[i-1].push_back(i);
indegree[i] ++;
}else if(ratings[i-1] > ratings[i]){
edges[i].push_back(i-1);
indegree[i-1]++;
}
}

queue q;
for(int i = 0; i < n; i++ ){
if(indegree[i] == 0){
q.push(i);
}
}
while(!q.empty()){
int cur = q.front();
q.pop();
sum += candy[cur];
for(int i : edges[cur]){
indegree[i]--;
if(indegree[i] == 0){
q.push(i);
}
candy[i] = candy[cur] + 1;
}
}
return sum;
}
};

a*e2014-08-26 07:08

15 楼

1 2 3 4 5 6 7这种情况怎么解？

example

【在 f*****h 的大作中提到】

: Hint:
: Group the babies by their ratings as longest decreasing groups, for example
: 4 3 2 3 2 1 2 3 4 4 5 5
: ->
: (4 3 2) (3 2 1) (2) (3) (4) (4) (5) (5)
: The total candies for a group of size N contains two parts
: i) max(N, candy_of_last_baby_in_last_group + 1) (*)
: ii) N-1 + N-2 + ... + 1
: (*) There is a corner case here.

g*92014-08-26 07:08

16 楼

从左往右找递增子区间，记录每个子区间最小值，从最小值开始给糖果，从1开始，依
次加1；从右往左，从每个最小值向左扫，给没有糖果的。应该是O(n)

q*52014-08-26 07:08

17 楼

可能我没有读懂题：Children with a higher rating get more candies than their
neighbors.
input [2,2,1] 怎么可能4个candy就够了？
这三个小孩分别得到多少candy？
谢。

【在 z*********8 的大作中提到】

p*y2014-08-26 07:08

18 楼

题目的意思是一样RATING的孩子可以得到不同数量的candy，这里就是[2,1,1]

their

【在 q******5 的大作中提到】

: 可能我没有读懂题：Children with a higher rating get more candies than their
: neighbors.
: input [2,2,1] 怎么可能4个candy就够了？
: 这三个小孩分别得到多少candy？
: 谢。

P*r2014-08-26 07:08

19 楼

我觉得rating 是【2，2，1】的话，分法可以是[1,2,1]。
第一遍coding 的时候，也是这个case错掉了。

【在 p*********y 的大作中提到】

: 题目的意思是一样RATING的孩子可以得到不同数量的candy，这里就是[2,1,1]
:
: their

P*r2014-08-26 07:08

20 楼

我觉得rating 是【2，2，1】的话，分法可以是[1,2,1]。
第一遍coding 的时候，也是这个case错掉了。

【在 p*********y 的大作中提到】

: 题目的意思是一样RATING的孩子可以得到不同数量的candy，这里就是[2,1,1]
:
: their

a*e2014-08-26 07:08

21 楼

糖果数为1,2,1
如果两个小孩rating相同，没有规定他们的糖果数要如何。

their

【在 q******5 的大作中提到】

c*p2014-08-26 07:08

22 楼

好牛哦

l*o2014-08-26 07:08

23 楼

这种做法我之前试了，边界条件总是想不清。Can you show me the code?

example

【在 f*****h 的大作中提到】

b*e2014-08-26 07:08

24 楼

/*
Here's a solution with JS, O(n) time and O(1) space.
You can copy&paste the full body of this post and run it in
a browser console.
*/
var minCandies = function(children) {
var maxHeight = children.length;
var state = 'desc';
var height = maxHeight;
var accumulated = 0;
var count = 0;
for (var i = 0; i < children.length - 1; i++) {
accumulated += height;
count++;
if (state == 'desc') {
if (a[i] > a[i+1]) {
height--;
} else if (a[i] == a[i+1]) {
} else {
var diff = height - 1;
accumulated -= diff * count;
count = 0;
height = 2;
state = 'asc';
}
}
else { // state == 'asc'
if (a[i] < a[i+1]) {
height++;
} else if (a[i] == a[i+1]) {
} else {
count = 0;
height = maxHeight;
state = 'desc';
}
}
}
// handle the last child
if (state == 'desc') {
accumulated += height;
count++;
var diff = height - 1;
accumulated -= diff * count;
} else {
accumulated += height;
}

return accumulated;
};
// var a = [1,2,3,4,5,6,7];
// var a = [100,99,98,97,96,95,94];
var a = [4,3,2,3,2,1,2,3,4,4,5,5];
// 3,2,1,3,2,1,2,3,4,4,5,5
console.log(minCandies(a));

l*02014-08-26 07:08

25 楼

class Solution {
public:
bool getSum(vector &ratings, int &sum)
{
bool isReverse = false;

int n = ratings.size();

int* candy = new int[n];
memset(candy, 0, n*sizeof(int));

candy[0] = 1;

for (int i=1; i{
if (ratings[i] > ratings[i-1])
candy[i] = candy[i-1] + 1;
else if (ratings[i] == ratings[i-1])
candy[i] = candy[i-1];
else
{
isReverse = true;

candy[i] = 1;

if (candy[i-1] == 1)
{
candy[i-1]++;

int j=i-1;
while (j>=1 && ratings[j-1] > ratings[j] && candy[j-1] <
= candy[j])
{
candy[j-1]++;
j--;
}
}
}
}

for (int i=0; isum += candy[i];

return isReverse;
}
int candy(vector &ratings) {
// Note: The Solution object is instantiated only once and is reused
by each test case.
int sum1 = 0;
bool isReverse = getSum(ratings, sum1);

if (!isReverse)
return sum1;

int n = ratings.size();
for (int i=0, j=n-1; i{
int tmp = ratings[i];
ratings[i] = ratings[j];
ratings[j] = tmp;
}

int sum2 = 0;
getSum(ratings, sum2);

return sum1}
};

l*02014-08-26 07:08

26 楼