|
B*****t
发帖数: 335 | 2 I think the question is to ask "how many different BINARY SEARCH TREES", not
"binary trees", otherwise the answer is not Catalan number, but the answer
can also be found by DP.
one |
|
|
|
c********0
发帖数: 112 | 5 第一个题貌似是那个Catalan number
第二题两个指针扫一遍就行了
具体参考1337code |
|
|
b*******8
发帖数: 37364 | 7 第一个Catalan树，手头推导结果有两种方法。一种先搞递归式，再用组合数学的生成函数，很难记住临时写出。第二种是转换为等价的（）配对计数问题，所有组合数减去不合法的配对，数据结构书上有，也很复杂，但是可以记住。
如果是写程序算，用第一种递归比较好。 |
|
F**********r
发帖数: 237 | 8 en, 知道是catalan数。。。可是还是没想通要怎么code啊。。。 |
|
f*****w
发帖数: 2602 | 9
我感觉递归是唯一的办法。
可以用catalan数的那个递归方程来做一些类似于DP的优化，但是复杂度还是没区别的
。 |
|
g*********8
发帖数: 64 | 10 全看的人飘过，对上面的恶俄罗斯方块和扫雷两道题不知道该怎么解，数学部分的大猩
猩那道题疯了，概率分析我最弱了。不过数学部分有道题讲到了Catalan Number还是蛮
有用的，可以解给定n个数，有多少可能的二叉树这个题。最后的一个数独知多少又挂
了。
当然最无感的是第一题，控制task manager |
|
w****x
发帖数: 2483 | 11 这是OnSite的题吧。
1. 有Merge的解法是O(m+n), 可以用二分解法，取median每次淘汰1/4.这题写起code来
edgecase超多
int GetMedian(int a[], int n, int b[], int m, int k)
{
assert(a && b);
if (n <= 0) return b[k-1];
if (m <= 0) return a[k-1];
if (k <= 1) return min(a[0], b[0]);
if (b[m/2] >= a[n/2])
{
if ((n/2 + 1 + m/2) >= k)
return GetMedian(a, n, b, m/2, k);
else
return GetMedian(a + n/2 + 1, n - (n/2 + 1), b, m, k - (n/2 + 1)
);
}
else
{
if ((m/2 +... 阅读全帖 |
|
i***e
发帖数: 452 | 12 right. Catalan numbers!! |
|
i***e
发帖数: 452 | 13 that's wrong! please google "catalan numbers" |
|
b*****n
发帖数: 143 | 14 是不是 C(n) / n!, in which C(n) is Catalan number of n. |
|
|
e***s
发帖数: 799 | 16 二爷，有个更牛B 的求Catalan Number的方法，求解释。
public static int uniqueBinarySearchTreeDPII(int n){
int ret = 1;
for(int i = 2; i <= n; i++)
ret = 2 * (2 * i - 1) * ret / (i + 1);
return ret;
} |
|
s*****l
发帖数: 10 | 17 N*N的grid，对角线上半部分或者下半部分的不同路径（包含对角线路径）数目是
Catalan number，可以直接用DP求解。C(i) = C(i-1) * (2*i - 1) * 2 / (i+1). 初
始值C(0) = 1，C(1) = 1.
如果不包含对角线路径，且考虑对角线上下两部分的不同路径，求2*C(N-1)。 |
|
s*******s
发帖数: 1031 | 18 找工作结束了，从版上学到了很多东西，总结一下我的经历回报版上，希望大家都能拿
到心仪的offer。
本人纯DS男一枚，跟本上的牛人绝对没得比。总结一下我这几个月的申请经验。
先后面试了几家公司，拿到了A, MS 和 G 三家的面试。A家7月初面试结束后到现在对
我不管不问，不说拒也不说不拒，应该是默剧了。 M家是8月中oniste的，第二天出的
offer。一周后的周一面试的G家，因为有MS家的offer让我赶快答复，我就push G 家快
点出结果， G家当周的周五确认我拿到offer。
最后我选择了去G家，package很DS，跟版上牛人的没得比，就不拿出来献丑了。
先上面经。
A家：
先是2轮电面。然后参加了onsite，见到了6个人。
电面1: 老美白人
1. talk about a scenario during your works, when the manager did not
want to take your advice, but you try to finished it at your own time.
2. ... 阅读全帖 |
|
s*******s
发帖数: 1031 | 19 找工作结束了，从版上学到了很多东西，总结一下我的经历回报版上，希望大家都能拿
到心仪的offer。
本人纯DS男一枚，跟本上的牛人绝对没得比。总结一下我这几个月的申请经验。
先后面试了几家公司，拿到了A, MS 和 G 三家的面试。A家7月初面试结束后到现在对
我不管不问，不说拒也不说不拒，应该是默剧了。 M家是8月中oniste的，第二天出的
offer。一周后的周一面试的G家，因为有MS家的offer让我赶快答复，我就push G 家快
点出结果， G家当周的周五确认我拿到offer。
最后我选择了去G家，package很DS，跟版上牛人的没得比，就不拿出来献丑了。
先上面经。
A家：
先是2轮电面。然后参加了onsite，见到了6个人。
电面1: 老美白人
1. talk about a scenario during your works, when the manager did not
want to take your advice, but you try to finished it at your own time.
2. ... 阅读全帖 |
|
|
h*******e
发帖数: 1377 | 21 可是dp在求catalan 数500左右的时候超时需要先约分再除， 有没有个大概的总结帖子
~~ |
|
r*****e
发帖数: 30 | 22 好吧，我明白你的意思了
第4题括号匹配是一个Catalan Number的问题
你看下http://en.wikipedia.org/wiki/Catalan_number#Applications_in_combinatorics里面有个浅蓝色的图
就是有箭头的那张，每个向右的箭头对应一个‘（’，每个向上的箭头对应一个‘）’
,同时要满足任何时候'（'的数量>=')'的数量
所以递推式就是 f(i,j) = (j-1>=i?f(i,j-1):0) + （i-1>=0?f(i-1,j):0),其中i是
行，j是列,行对应‘）’，列对应‘（’
算完整个矩阵后，n对括号，第k大的问题就是从f(n,n)开始往f(0,0)走，走的过程中比
较f(i,j)和k的关系，从而决定该往下走，还是往左走，同时加上括号，如果当前在(i,
j）的位置，如果i-1>=0&&f(i-1,j)>=k,就向下走同时加一个'(',否则向左走同时加一
个‘）’，并且更新k-=f(i-1,j) |
|
|
z***e
发帖数: 5600 | 24 Somehow Spain CDS or IBEX index have not moved much recently for this to
matter for the global market. I thought Catalan independence was a big deal. |
|
h********o
发帖数: 3320 | 25 绝对坏消息。今天一早一直在追高，，然后在2580以上全部抛掉了SP X long的仓位。
不能太贪。UV XY一早抛掉一半，剩下的roll到下周。大盘风险仍然很高，目前有盈利
立马锁定。等tech过去之后，以后的季报估计不会太好看。
: Somehow Spain CDS or IBEX index have not moved much recently for this
to
: matter for the global market. I thought Catalan independence was a
big deal.
|
|
h*********n
发帖数: 11319 | 26 Catalan GDP大概2500亿，相当于WI或者TN的水平，而且又没有自己的军队，闹不起来。 |
|
z***e
发帖数: 5600 | 27 Catalan是坏消息，但对全球金融市场如何造成负面影响？能想到的还是通过西班牙国
债在独立后谁来负的风险来传递。但是如果西班牙国债/CDS都没啥动静，SPX/VIX怎么
会在乎呢？时机目前还没到。这些风险会被先忽略，然后某天集中爆发
this |
|
h********o
发帖数: 3320 | 28 市场需要调整的时候，不需要多么大的消息。当年希腊危机对美国有什么影响？不也是
把大盘砸了一个坑。这个可以算以后大盘调整的一个风险因素。Catalonia独立，应该
算自动脱离欧盟。
: Catalan GDP大概2500亿，相当于WI或者TN的水平，而且又没有自己的军队，闹
不起来。
|
|
G**********e
发帖数: 11693 | 29 The challenge in choosing 10 of the best restaurants to open in Houston each
year is a daunting one: Many of the restaurants I think are "the best" have
little to nothing to do with each other, making for a list that falls all
over the map when it comes to price, cuisine and location.
Then again, the amusing disjointedness represents Houston itself -- as does
the fact that three of last year's top 10 best new restaurants no longer
exist in the same incarnations (Caffe Bello, Umai and Bootsie's).... 阅读全帖 |
|
|
S*****3
发帖数: 720 | 31 北京时间7月12日凌晨，约翰内斯堡的足球城球场，世界杯决赛在西班牙和荷兰队之间
进行。
在比赛开始前，上届世界杯冠军意大利队的队长卡纳瓦罗提前出场，他带来了大力
神杯。卡纳瓦罗向全场观众展示着大力神杯，他微笑着向球场各个方向看台的观众们举
起奖杯。随后，卡纳瓦罗走出球场，将大力神杯交给工作人员。两个小时之后，这座奖
杯将交给新的世界冠军。
就在这时，决赛赛场上演神奇一幕，一位男球迷从主席台对面的左侧入口冲进去，
而且横跨了球场，一直冲到了主席台前，用手触摸大力神杯。
球场的保安快步冲了上去，一拳将这名男子击倒在地。这个人就是著名的吉米跳(
Jimmy Jump)。
吉米蹦(Jimmy Jump)原名科托(Jaume MarquetCot)，西班牙人，生于1974年，是加
泰罗尼亚(Catalan)的一个房地产经纪人。在欧洲杯决赛葡萄牙同希腊比赛快要结束时
，科托当着全世界观众的面开了菲戈一个大玩笑。他像天使又像魔鬼般的从看台直窜场
地中央，然后拉开巴萨的横幅重重的丢在菲戈的脸上。吉米蹦(JimmyJump)名副其实，
科托一跳成名 |
|
f**********4
发帖数: 2617 | 32 klutz1998 说的对，有些人听着风就是雨，Catalan和Castillan是绝对相似的。自从西班牙王
国成立以来，加泰罗尼亚就是其一部分，从来就没有独立出去过。哪来的“本来就不是
它的”？
另外即便是“彪悍”的巴斯克，独立倾向也早就今非昔比。巴斯克语在巴斯克大区的最
重要城市比如毕尔巴鄂，圣塞巴斯蒂安，第一的地位都已被Castillan取代了，只有比
较偏僻的小城市，乡村还是普遍通用的语言。
最后，巴斯克和加泰一样也是发达地区，不同的是，加泰重商，巴斯克重工。所以落后
地区有独立倾向可不是罕见的。 |
|
l*******o
发帖数: 12469 | 33
Earlier, on 24 September 1983, Andoni Goikoetxea Olaskoaga achieved
notoriety for an infamous tackle on Diego Maradona in a league match at the
Camp Nou, ferociously tackling the Argentine from behind and leaving him
severely injured, and reportedly later keeping "the boot he had used to
destroy...(Maradona’s) ankle ligaments" at home in a glass case.When the
two teams met in that year's Cup final (1–0 for Athletic), the match ended
with several players fighting in the field. Goikoetxea also se... 阅读全帖 |
|
d*********2
发帖数: 48111 | 34 作了什么贼了， 至于要亏心成这样吗？
Infamous last year’s Chelsea-Barcelona referee retires to be a monk
Posted on28 December 2009 at 14:24. Tags: barcelona, champions league,
chelsea, essien, football, iniesta, monk, tom henning obrevo
In search of peace and to get away from the nightmare he had to live since
the fateful meeting in the semifinals of Champions League between Chelsea
and Barcelona in London, where he didn’t sanction four penalties for the
English tosmooth the way of the Catalans to the Champions C... 阅读全帖 |
|
l*****i
发帖数: 3929 | 35 They produce hte best people...
everyone at the Spanish club, as Owen Slot discovered
是一种美丽游戏，不如说是一种生活方式。
from the Nou Camp and is as follows: Barcelona do not only produce the best
footballers, they produce the best people, too.
仅出产最好球员，还出产最好的人。
personality. There is an opinion at large that a requirement to be a world-
beating athlete in any sport is a certain hardness, a cold-blooded arrogance
, but here at La Masia you will: 他们会下功夫磨练球技，会下更多功夫珩磨人格
。有这样一种笼统的观点：无论想在哪个体育项目里称雄，都要以冷酷和无情的傲慢为
必备条件。... 阅读全帖 |
|
M**Q
发帖数: 477 | 36 http://sports.yahoo.com/soccer/news;_ylt=ArBzYYvL195NjEmXosH9FT
MADRID (AFP) - Arsenal have abandoned efforts to keep skipper Cesc Fabregas
who could be set for a return to Spanish giants Barcelona, Spanish sports
newspapers said Thursday.
Gunners coach Arsene Wenger has allowed his skipper to leave on condition he
does not sign with another English team, the Barcelona-based daily Mundo
Deportivo said, quoting a conversation between the two.
But it warned that "negotiations between the two clubs... 阅读全帖 |
|
P*******9
发帖数: 9700 | 37 西乙Granada CF有11名球员都是乌鸡租借过去的
这下宇宙队也学着要把罗马变成自己在意假的卫星队了
How Udinese beat the system and stands at the gates of La Liga
June 14th, 2011 By Eric Beard
At the end of the 2009-10 season, Granada CF and Barcelona B finished first
and second in the third tier of Spanish football, both gaining promotion to
Liga Adelante. This past season, Barcelona B finished 3rd and Granada
finished 5th.
Promotion into La Liga is almost identical to promotion into the Premier
League. That is, the best two sides in the le... 阅读全帖 |
|
b*****e
发帖数: 53215 | 38 Strike, Cesc
By ANTONY KASTRINAKIS
Published: Today
Add a comment (50)
BARCELONA want Cesc Fabregas to go on strike next week to force a cut-price
move from Arsenal.
The Gunners face a nail-biting wait to see if their skipper turns up for the
first day of pre-season training a week today.
Barcelona have had a 7million bid turned down and are unlikely to meet Ars
enal's 0m valuation.
If Fabregas refuses to join up with his team-mates, it will put Arsenal unde
r enormous pressure to finally sell t... 阅读全帖 |
|
l*********0
发帖数: 2508 | 39 周六比赛上半场马德里裁判对皮克的点球抗议表示你丫闭嘴，要不红你小样儿的
Velasco-Carballo (referee, to Pique during penalty discussion at half-time
Sporting game): "You, shut up, you'll get a red card."
下半场2分钟果然给了皮克红牌，皮克抱怨：这是阴谋，裁判早想把俺罚下了
风声传出，裁判委员会要研究皮克的阴谋论言行，对其追加处罚，因为媒体大肆报道了
此事
Jimenez (spokesperson Spanish referee committee): "Why complaint against
Pique? We act depending on the media impact of statements."
有人问马德里那边对裁判的大量抨击为啥统统被无视？裁判委员会表示俺们没听说他们
抨击过裁判
巴萨这边坐不住了，要对红牌上诉，并拒绝出席明天讨论国王杯决赛场地的会议以示抗
议（另有小道消息说巴萨要自己找决赛场地，反了不成？）
Barcelona wil... 阅读全帖 |
|
s**c
发帖数: 34339 | 40 ☆─────────────────────────────────────☆
lindeshen80 (最熟悉的陌生人) 于 (Mon Mar 5 22:26:24 2012, 美东) 提到:
周六比赛上半场马德里裁判对皮克的点球抗议表示你丫闭嘴，要不红你小样儿的
Velasco-Carballo (referee, to Pique during penalty discussion at half-time
Sporting game): "You, shut up, you'll get a red card."
下半场2分钟果然给了皮克红牌，皮克抱怨：这是阴谋，裁判早想把俺罚下了
风声传出，裁判委员会要研究皮克的阴谋论言行，对其追加处罚，因为媒体大肆报道了
此事
Jimenez (spokesperson Spanish referee committee): "Why complaint against
Pique? We act depending on the media impact of statements."
有人问马德里那边对裁判的大量抨击为啥统统... 阅读全帖 |
|
B******e
发帖数: 16928 | 41 都是著名的Catalan economist，一个大牛，一个小牛，大牛还兼从事加泰罗尼亚独立
运动。 |
|
c*****n
发帖数: 1150 | 42 A2 说对了，这个裁判”has a great personality"。
http://www.goal.com/en/news/1716/champions-league/2012/04/04/30
Barcelona-Milan referee pleased with match officials' performance
The man in charge during Tuesday's Champions League encounter at Camp Nou
has affirmed that he is satisfied with his display and has been receiving
compliments
The Dutch referee has received his fair share of criticism for his decision
to award the Catalans a second penalty after Alessandro Nesta's infringement
on Sergio Busquets ... 阅读全帖 |
|
a**q
发帖数: 29 | 43 Barcelona struck a deal Thursday to sign Valencia and Spain left-back Jordi
Alba for 14 million euros ($17.5 million) on a five-year contract, the
Catalan club said.
"Barcelona Football Club has today reached an agreement with Valencia for
the transfer of Jordi Alba, pending a medical which he will undergo in
Barcelona next week," a statement from the club said.
"The cost of the transfer will be 14 million euros and the player will sign
a contract for the next five seasons," it added.
The Barcel... 阅读全帖 |
|
e*******e
发帖数: 9616 | 44 这是他重申２０１１年may 输给把塞时说的话。
我是听着他说的，那场比赛在我的dvr里。
我都看了好几遍。连我儿子都知道xavi/inesta.
昨天吃饭一下就从电视上认出他们俩了。
http://www.guardian.co.uk/football/2011/may/29/sir-alex-ferguso
"Sir Alex Ferguson hailed Barcelona as the strongest team he has confronted
as a manager after the Catalans claimed their fourth European Cup at
Manchester United's expense, although this chastening experience has not
dented the Scot's enthusiasm to attempt to overhaul "the best team in Europe
"." |
|
t***o
发帖数: 19256 | 45 http://news-ro.com/balotelli-playing-in-the-club-i-do-not-play-
Balotelli: “Playing in the club? I do not play with girls”
by admin on Friday, July 27th, 2012 | No Comments
Mario Balotelli Italian striker Mario Balotelli during a workout. (AP)
Enlarge
read more:”79″>Mario Ballotelli
, one of the protagonists of the last European Championship
football news again, this time for remarks about a Spanish club FC Barcelona.
In an interview, and asked about the possibility of playing in t... 阅读全帖 |
|
D*****r
发帖数: 6791 | 46 应该是巴萨在兴风作浪，catalan体育新闻什么放出来的消息。凯塔走了要买中场，哈
维马丁内斯买不下来，就开始打宋的主意。
阿森纳的风格是在高点卖，这边4000万的范佩西马上就要自由转会了，哪有功夫考虑宋
这个第二高的。
要买也行也不用2500万，1500万就行，不过得搭个蒂亚戈。
阿森纳这边才送走日本人去维甘，已经不需要阿费莱这样的边路选手了。如果范佩西卖
不出去，不如就趁实力过剩的这个机会拿个冠军，老卖人不拿冠军也对不起球迷。
宇宙 |
|
s***i
发帖数: 10182 | 47 Robinho advises Neymar to join Barcelona over Real Madrid
The Brazilian attacker feels his countryman would be wise to pick the
Catalans if he harbours the ambition of becoming the best player in the
world one day |
|
s******n
发帖数: 2279 | 48 弗朗西斯科利都知道吧
Francescoli: Barcelona's Messi better than Maradona
The 50-year-old has revealed his admiration for the Catalans forward who he
says is better than El Diego and had kind words for Zinedine Zidane
Enzo Francescoli, one of the greats of Uruguayan football, has hailed Lionel
Messi as the greatest player ever, surpassing Diego Maradona.
The 50-year-old was speaking as a guest on the television programme Por
Deporte in Argentina and lauded both footballers.
But it was the current Barcelona... 阅读全帖 |
|
k*******8
发帖数: 2320 | 49 瓦倫西亞也是講Catalan的 和加泰羅尼亞一起獨立才對 |
|
A**4
发帖数: 2165 | 50 Catalonia would beat Spain easily if there were a game. However, it's not
pertinent to compare Catalane with red necks.
ola" |
|
