paint splatter jeans - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>Fashion - 美丽时尚

paint splatter jeans

paint splatter jeans# Fashion - 美丽时尚

s*u2010-10-08 07:10

1 楼

感觉这道题经久不衰，一直是经典难题。就是一堆interval，带有start和end，以及高
度，整合之后每个interval要取最高值。
最近换汤不换药，出了speaker的版本：
http://www.mitbbs.com/article_t/JobHunting/32569901.html
epi有两道题，14.19和15.1处理这类问题。
方法是不同的，
一个先将endpoint排序，另外用一个BST维护当前的最大高度，然后结束时就删除相应
的节点，这个感觉很难想，代码简洁一点。
另一个是mergesort。思路简单，代码要冗长一点。
个人感觉前者适用于应付stream，如果是静态数据应该mergesort就够了。
大家怎么看呢？

b*l2010-10-08 07:10

2 楼

买了条上面有彩色油漆点儿的jeans,是不是特容易过时或已经过时了啊？

s*e2010-10-08 07:10

3 楼

这个是UVa里面的题目啊。

b*l2010-10-08 07:10

4 楼

就是这条，不过颜色偏蓝，paint有些红色和黄色的。MM们帮看看好吗

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

: 买了条上面有彩色油漆点儿的jeans,是不是特容易过时或已经过时了啊？

f*e2010-10-08 07:10

5 楼

LZ在看epi吗？里面的题目有些挺难的。。。

【在 s********u 的大作中提到】

: 感觉这道题经久不衰，一直是经典难题。就是一堆interval，带有start和end，以及高
: 度，整合之后每个interval要取最高值。
: 最近换汤不换药，出了speaker的版本：
: http://www.mitbbs.com/article_t/JobHunting/32569901.html
: epi有两道题，14.19和15.1处理这类问题。
: 方法是不同的，
: 一个先将endpoint排序，另外用一个BST维护当前的最大高度，然后结束时就删除相应
: 的节点，这个感觉很难想，代码简洁一点。
: 另一个是mergesort。思路简单，代码要冗长一点。
: 个人感觉前者适用于应付stream，如果是静态数据应该mergesort就够了。

E*T2010-10-08 07:10

6 楼

搭配比较重要了我觉得。。。比较不会HANDLE这样的。。
等其他 FASHION 牛人来解答

p*22010-10-08 07:10

7 楼

这题要问三爷了。他刚post了答案

h*d2010-10-08 07:10

8 楼

我觉得挺好看的

s*u2010-10-08 07:10

9 楼

epi题目很鲜活，但答案太文艺了。。。。

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

: LZ在看epi吗？里面的题目有些挺难的。。。

b*l2010-10-08 07:10

10 楼

仔细看是这样的， vince, 原价255刀
现在忽然看着有点儿恶心了，呵呵

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

: 买了条上面有彩色油漆点儿的jeans,是不是特容易过时或已经过时了啊？

s*x2010-10-08 07:10

11 楼

嗯，俺学到的就是可以用 ordered set 作 max heap.
ordered set 本身就是 BST, 可以容易的删除一个节点，find the max value using
end() - 1 或 begin() depending on how you define the comparing function.
this is nice.
classical max heap does not support removing random element well.

R*o2010-10-08 07:10

12 楼

你穿上照一张让大家看看

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

: 仔细看是这样的， vince, 原价255刀
: 现在忽然看着有点儿恶心了，呵呵

s*u2010-10-08 07:10

13 楼

是的，主要是库里的heap不支持，自己可以写但太麻烦了，要siftup和siftdown。所以
还是bst好维护。对了，取最后一个值的话用rbegin()和end(）-1有什么区别呢

【在 s**x 的大作中提到】

: 嗯，俺学到的就是可以用 ordered set 作 max heap.
: ordered set 本身就是 BST, 可以容易的删除一个节点，find the max value using
: end() - 1 或 begin() depending on how you define the comparing function.
: this is nice.
: classical max heap does not support removing random element well.

S*t2010-10-08 07:10

14 楼

穿上效果咧？

g*e2010-10-08 07:10

15 楼

这题还可以用divide and conquer做

y*g2010-10-08 07:10

16 楼

这种水洗今年很多，不能保证明年会不会过时。但是你这条看起来洗的一般，我见过一
款dior homme浅色裤子，上面有很多颜色/油漆斑点的，洗的很好看，上个月国内it对
折，价格还是比较高。
其实这种裤子没太多意思，人家一看就知道大概是哪年的款式。就好象前几年的黑胶裤
，然后又是金漆银漆，到去年的破坏重水洗，今年的彩色油漆斑。
要买就买当时最经典的某runway款，作为搜藏，就算过季，偶尔拿出来穿穿也可以炫耀
一下。但是七七八八非专业品牌的还是算了。

b*e2010-10-08 07:10

17 楼

mark le.

b*l2010-10-08 07:10

18 楼

有道理，我也有同感。那我还是拿去退了吧，就不穿上献丑了，呵呵。大家长周末愉快。

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

: 这种水洗今年很多，不能保证明年会不会过时。但是你这条看起来洗的一般，我见过一
: 款dior homme浅色裤子，上面有很多颜色/油漆斑点的，洗的很好看，上个月国内it对
: 折，价格还是比较高。
: 其实这种裤子没太多意思，人家一看就知道大概是哪年的款式。就好象前几年的黑胶裤
: ，然后又是金漆银漆，到去年的破坏重水洗，今年的彩色油漆斑。
: 要买就买当时最经典的某runway款，作为搜藏，就算过季，偶尔拿出来穿穿也可以炫耀
: 一下。但是七七八八非专业品牌的还是算了。

f*e2010-10-08 07:10

19 楼

恩里面很多代码都是用template写的，有些挺简练的

【在 s********u 的大作中提到】

: epi题目很鲜活，但答案太文艺了。。。。

y*g2010-10-08 07:10

20 楼

既然买回来了，退之前照一张奔一个做个留念吧！哈哈
养牛人的意见是，如果自己穿着牛仔裤干活，刷油漆，画画，不小心弄破弄脏了裤子，
沾上了颜料，沥青，金粉，不需要刻意放很多洗衣粉洗掉，而是留在裤子上接着穿。
但是如果花钱请服装厂的工人给你的牛仔裤涂颜料刷胶什么的模拟把裤子搞脏了是在是
没意思。除非是某大师的经典之作，以后再也不会出第二批了，买来收藏的。有人就喜
欢收藏hedi slimane原来给dior homme设计的某几款水洗裤，主要是03年的，04年和07
年的某几条。

快。

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

: 有道理，我也有同感。那我还是拿去退了吧，就不穿上献丑了，呵呵。大家长周末愉快。

s*u2010-10-08 07:10

21 楼

嗯，就是我说的merge

【在 g*********e 的大作中提到】

: 这题还可以用divide and conquer做

b*l2010-10-08 07:10

22 楼

现在看着它越来越觉得丑+俗了，不污染视听了。

07

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

: 既然买回来了，退之前照一张奔一个做个留念吧！哈哈
: 养牛人的意见是，如果自己穿着牛仔裤干活，刷油漆，画画，不小心弄破弄脏了裤子，
: 沾上了颜料，沥青，金粉，不需要刻意放很多洗衣粉洗掉，而是留在裤子上接着穿。
: 但是如果花钱请服装厂的工人给你的牛仔裤涂颜料刷胶什么的模拟把裤子搞脏了是在是
: 没意思。除非是某大师的经典之作，以后再也不会出第二批了，买来收藏的。有人就喜
: 欢收藏hedi slimane原来给dior homme设计的某几款水洗裤，主要是03年的，04年和07
: 年的某几条。
:
: 快。

J*32010-10-08 07:10

23 楼

我用 g++ 4.7 测怎么map木有emplace这个函数呢。楼主有碰到吗

y*g2010-10-08 07:10

24 楼

-_-;
没这么严重吧。。。

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

: 现在看着它越来越觉得丑+俗了，不污染视听了。
:
: 07

s*u2010-10-08 07:10

25 楼

C++11有，是emplace_back吧，其实你就当是push_back吧

【在 J****3 的大作中提到】

: 我用 g++ 4.7 测怎么map木有emplace这个函数呢。楼主有碰到吗

I*e2010-10-08 07:10

26 楼

MM...我几个月前就买了这条。。。很好看。也很好穿。。。周末休闲穿。
vince的牛仔裤超级舒服的。。。。。

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

: 仔细看是这样的， vince, 原价255刀
: 现在忽然看着有点儿恶心了，呵呵

f*x2010-10-08 07:10

27 楼

thanks!
这题学会了

【在 s********u 的大作中提到】

I*e2010-10-08 07:10

28 楼

【在 I*****e 的大作中提到】

: MM...我几个月前就买了这条。。。很好看。也很好穿。。。周末休闲穿。
: vince的牛仔裤超级舒服的。。。。。

J*32010-10-08 07:10

29 楼

是的我是用11标准编译的。 map在11里也没emplace_back哇，我是看你发的那个link
上的代码想跑跑他那个例子看。

【在 s********u 的大作中提到】

: C++11有，是emplace_back吧，其实你就当是push_back吧

y*g2010-10-08 07:10

30 楼

那你也奔个吧

【在 I*****e 的大作中提到】

J*32010-10-08 07:10

31 楼

就insert好了。不懂为啥

【在 s********u 的大作中提到】

: C++11有，是emplace_back吧，其实你就当是push_back吧

b*l2010-10-08 07:10

32 楼

天呀，没留心看回帖，没想到MV也买了啊。早知道就不去退了啊。。。。。。。

【在 I*****e 的大作中提到】

s*u2010-10-08 07:10

33 楼

哦哦我傻掉了，是map。其实我一般都是用[]的呵呵。他那个例子我经常跑死机。。。
不知为啥。。

link

【在 J****3 的大作中提到】

: 是的我是用11标准编译的。 map在11里也没emplace_back哇，我是看你发的那个link
: 上的代码想跑跑他那个例子看。

J*32010-10-08 07:10

34 楼

哈哈，对啦上面你们说的用ordered set 做？是指怎么实现？

【在 s********u 的大作中提到】

: 哦哦我傻掉了，是map。其实我一般都是用[]的呵呵。他那个例子我经常跑死机。。。
: 不知为啥。。
:
: link

n*e2010-10-08 07:10

35 楼

同感啊，有些答案写得不容易看懂，读起来挺费劲的。

【在 s********u 的大作中提到】

: epi题目很鲜活，但答案太文艺了。。。。

s*u2010-10-08 07:10

36 楼

就是bst，维护一个当前的最大高度，碰到末尾就把他删掉，这时候就能获取次高的高
度。
ordered_set就是一个没有value只有key的bst。但这个题好像的确应该是用map的，除
非你把value整合到set的key里面去。。

【在 J****3 的大作中提到】

: 哈哈，对啦上面你们说的用ordered set 做？是指怎么实现？

J*32010-10-08 07:10

37 楼

恩这题他也说用height做proxy，也提到height在这里是唯一的，作为map的key。不
过map也是rbt。后面有个变体题目是height不唯一的情况

【在 s********u 的大作中提到】

: 就是bst，维护一个当前的最大高度，碰到末尾就把他删掉，这时候就能获取次高的高
: 度。
: ordered_set就是一个没有value只有key的bst。但这个题好像的确应该是用map的，除
: 非你把value整合到set的key里面去。。

s*u2010-10-08 07:10

38 楼

你是说15.1么，嗯。就是我说的mergesort。bst主要是std::map不支持说重复key的情
况。如果自己实现则可以。

【在 J****3 的大作中提到】

: 恩这题他也说用height做proxy，也提到height在这里是唯一的，作为map的key。不
: 过map也是rbt。后面有个变体题目是height不唯一的情况

A*c2010-10-08 07:10

39 楼

emplace_back() 比 push_back()更加效率一点。
新的c++11的feature用gcc 4.8或者比较新的clang++都支持。

【在 J****3 的大作中提到】

: 我用 g++ 4.7 测怎么map木有emplace这个函数呢。楼主有碰到吗

A*c2010-10-08 07:10

40 楼

这题前两天看了一眼，没有思路，就没搞，现在电面都玩这个了？

【在 s********u 的大作中提到】

J*32010-10-08 07:10

41 楼

是这个题答案后面的e-variant 题吧

【在 s********u 的大作中提到】

: 你是说15.1么，嗯。就是我说的mergesort。bst主要是std::map不支持说重复key的情
: 况。如果自己实现则可以。

J*32010-10-08 07:10

42 楼

这样啊原来是4.7支持的不够全面？

【在 A*********c 的大作中提到】

: emplace_back() 比 push_back()更加效率一点。
: 新的c++11的feature用gcc 4.8或者比较新的clang++都支持。

c*w2010-10-08 07:10

43 楼

mark

A*c2010-10-08 07:10

44 楼

嗯，我记得好像是4.8才开始支持C++11的。

【在 J****3 的大作中提到】

: 这样啊原来是4.7支持的不够全面？

s*u2010-10-08 07:10

45 楼

4.7也支持，不全面而已。

【在 A*********c 的大作中提到】

: 嗯，我记得好像是4.8才开始支持C++11的。

A*c2010-10-08 07:10

46 楼

哦，I see。thanks！

【在 s********u 的大作中提到】

: 4.7也支持，不全面而已。

o*n2010-10-08 07:10

47 楼

这样做可以吗？
先把所有的区间切成单位长度。然后，区间的位置作为key, 音量为值。
然后按照key 从小到大，比较音量，取大值。排成数组。
S1=[[(2,5), 10], [(6,10), 2],[(11, 13), 6]]
S2= [[(1,6),1], [(8,12), 8],[(13,15),3]]
print S1
print S2
def speaker(S1,S2):
res=[]
SN1,SN2=dict(),dict()
for s in S1:
for i in range(s[0][0],s[0][1]):
SN1[i]= s[1]
for s in S2:
for j in range(s[0][0],s[0][1]):
SN2[j]=s[1]
mk=max(SN1.keys()[-1],SN2.keys()[-1])
for k in range(mk+1):
if k in SN1.keys() and k in SN2.keys():
res.append(((k,k+1),max(SN1[k],SN2[k])))
elif k in SN1.keys():
res.append(((k,k+1), SN1[k]))
elif k in SN2.keys():
res.append(((k,k+1), SN2[k]))
return res
print speaker(S1,S2)
output:
[((1, 2), 1), ((2, 3), 10), ((3, 4), 10), ((4, 5), 10), ((5, 6), 1), ((6, 7)
, 2), ((7, 8), 2), ((8, 9), 8), ((9, 10), 8), ((10, 11), 8), ((11, 12), 8),
((12, 13), 6), ((13, 14), 3), ((14, 15), 3)]

s*u2010-10-08 07:10

48 楼

可以是可以，复杂度较高。

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

: 这样做可以吗？
: 先把所有的区间切成单位长度。然后，区间的位置作为key, 音量为值。
: 然后按照key 从小到大，比较音量，取大值。排成数组。
: S1=[[(2,5), 10], [(6,10), 2],[(11, 13), 6]]
: S2= [[(1,6),1], [(8,12), 8],[(13,15),3]]
: print S1
: print S2
: def speaker(S1,S2):
: res=[]
: SN1,SN2=dict(),dict()