Siyang的小尾羊圈

第一题。给一个数组a[1]到a[n] : 例如 1，2，3，4，5，6

现在随机生成a的一个permutation: b[1]到b[n] （例如：3 1 5 2 4 6）

问, a和b数组在每一位上都不相同的概率是多少？假设a本身没有重复的数

我的解法：

主问题：F(n) = 给定长度为n的a数组，b数组有多少种取法

辅助问题：结果用f(n)表示。 b数组是{1….i-1,x,i+1…n}的一个排列，其中x!=i，满足a，b在每一位上都不相同，有多少种b？例如，a = 1,2,3,4; b是{1,2,5,4}的一个排列。换句话说，组成b的元素中，有且只有一个数不在a中。

这样定义了F(n),f(n)后，很显然有递推关系：

F(n) = (n-1) * f(n-1)    //解释：第一位有n-1种选择，任意一种选择后，问题变为一个 n-1规模的辅助问题

f(n) = F(n-1) + (n-1)*f(n-1)   //情况一，在b数组的第i位置填入x，考虑剩下的n-1个位置，即是一个n-1规模的主问题；情况二，i位置填入非x的数，考虑剩下的n-1个位置，即是一个n-1规模的辅助问题。

简化一下表达式就是:

F(n) = (n-1)(F(n-1)+F(n-2))

第二题，一个binary tree，逆序打印BFS序列。不能同时用两段存储空间（不同时用queue和stack）

解法，用一个vector（array)模拟queue+stack。queue的push操作即vector的push_back，等效于q.pop()+stack.push()的操作则是，vector的index往前走一步！最后把vector从尾到头打印一遍即可。

第三题，网上看的答案，超级巧妙，生成一个0-255 二进制数有多少位是1的查询表

static int BitSetCount256[256] =

{

#define B2(n) n, n+1, n+1, n+2,

#define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2),

#define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2),

B6(0), B6(1), B6(1), B6(2)

}

不得不说，这个宏递归的方法用的太妙了！！！

附带赞一个巧妙度略低一些的计算二进制数有多少位1的方法

int bitSetCount(unsigned int i){
int c=0;

while(i){

c++;

i &= (i-1);  //这一步很赞，每次保证清除最低一位1；

}

return c;

}

1. http://nf.nfdaily.cn/ttlist/content/2009-11/03/content_6179094.htm

卖水果老人因收4张假钞猝死街头 水果遭哄抢

几张假钞，一条人命，一场人间悲剧。因一星期内连续收到4张假钞，62岁的小贩气急攻心倒在了水果摊上。而令人不耻的是，就在小贩猝死倒地后，留下的700多公斤水果被一些路人在半个小时内连买带拿一扫而空。这是10月31日上午发生在娄底市金谷市场的一幕。

现场：老汉猝死，水果贱卖

　　10月31日上午，娄底市金谷市场传来阵阵恸哭声，死者李谋辉的家人悲痛欲绝。记者在现场看到，只见老人已经躺在木架上，身体全部用衣服覆盖，在其身边烧了一堆冥钱。

　　李谋辉的家人急于准备安葬老人的后事，把没有卖掉的2辆三轮车上的柑橘、苹果等水果作2毛钱一斤低价处理，吸引许多群众马上来抢购。围观的群众看到这么便宜的水果，加上主人不在，也开始哄抢死者水果车上的柑橘。有的好心人给了一二元钱，更多的人则是看到没有人问要钱，拿起水果就走人。半个小时，连买带拿大约700多公斤的水果就被一扫而空。

起因：一周收4张假钞还被人砸

　　“父亲是收到假钞活活气死的！”据李谋辉的儿子李建军介绍，父亲是涟源荷塘人，今年62岁，有一儿一女，在金谷市场做水果生意已有几年，父亲为人比较随和，人际关系比较好。老人在世时身体本身不是很好，有高血压，平时脾气比较大，个性比较强。

　　前几天，有人拿20元假钞在李谋辉那里买水果，被他发现，接着就发生了口角争执。当时，买水果的人将李谋辉的后脑勺砸出血，李谋辉在附近医院看了病后，买水果的人赔偿了3000元医药费就离开了。

　　10月29日上午，又有一个年轻人拿了一张20元钱的假钞跟李谋辉买了2个苹果。李建军介绍说：“当时父亲没有发现是假钞，过后给我检验后才知道是假钞。父亲马上把买苹果的年轻人追到，年轻人被追到了，将我父亲推倒就跑。在附近好心群众的帮助下我们才把那个年轻人抓获，并送到金谷市场警务室。”

　　10月31日上午，李谋辉又在水果摊上收到一张20元的假钞。“父亲因为年老了眼睛不好，在一个星期内一连收了4张假钞，其中1张100元的，3张20元的，20元是FA6开头的。我们卖一箱香蕉才赚5元钱，收了几张假钞，这几天就等于白干，因此我父亲对此事耿耿于怀，可能是气急攻心，父亲当场晕倒在地就再也没有醒来。”李建军说：“我想就是假钞害死我父亲的！”

2.  http://news.163.com/09/1103/13/5N6RF6TR0001124J.html

大学生救人溺亡 捞尸者手牵绑尸绳谈价(图)

大学生救人溺亡事件 捞尸人：我们走错这步棋

核心提示：湖北三位大学生救人溺亡，目击者现场拍下照片：被打捞上来的一具大学生的遗体被绳子绑着，大半个身子浸在水里；一名穿白衬衫的老年男子，一边拉着绑尸体的绳子，一边摆手和岸上的师生谈价要钱。打捞3具遗体，捞尸者前后一共收取了3.6万元。

浙江在线11月3日报道 10月30日上午，湖北荆州宝塔湾烟雾朦胧，远处的货轮像往常一样在长江上平稳行驶。岸边的沙滩上，自发来这里祭奠英雄的人们络绎不绝……

6天前，当地两所高校的3名大学生何东旭、方招、陈及时为救两名落水少年，在这里献出了宝贵的生命。

令人心寒的是，在英雄遗体打捞时，面对同学们的“跪求”，个体打捞者不仅不为所动，而且挟尸要价，一共收取了36000元的捞尸费!

19岁救人大学生3个月前做开胸术

篮球队长主动和女班长换位，把自己换在“人链”最前端

宝塔湾位于荆州市郊，因附近一座明代万寿宝塔而得名。这里有一处沙滩，面积大约半个足球场那么大，坡地，是当地人游玩散步的去处，也是游泳爱好者们经常下水的地方。

堤岸上，矗立着一块巨型安全警示牌——“特别提醒，宝塔湾河段水情异常复杂，不知吞噬了多少人的宝贵生命，游泳危险”。

“这里经常有人溺水身亡，今年夏天的时候，我就亲眼见过捞出一具尸体。”住在附近的赵超广老人说。

赵超广退休前是荆州第三棉纺厂职工，也是一位游泳爱好者。他指着江水说，宝塔湾看着平静，实际上水下暗流涌动，河底都是锅底状的陡坡，人在水中游走一旦踩空十分危险。

事情就出在这个水下的“陡坡”。

“救人时，大家手挽手结成‘人链’，前面的同学一脚踩进深处，有两个同学的手松开了，‘人链’断开处的前9人一下子落水……”讲起10月24日发生的那一幕，目击者长江大学文理学院(独立学院，与长江大学不属于同所高校)新生高阳陷入痛苦的回忆。

那是一个普通的周末，天气很好。高阳所在的广播电视新闻专业两个班的新生，相约来到宝塔湾郊游。大家来自全国各地，到校只有50天时间，很多同学还没有近距离看过长江。

深秋之季，长江水清江平，宝塔湾看上去十分静谧。下午2时，一顿饕餮过后，大家坐在松软的沙滩上，三五扎堆，漫不经心地开始聊天。

“救命!救命!”不远处传来的呼救声惊动了大家——两个小男孩落水了!当天是周六，在宝塔湾观光游玩的少说也有100多人，大家纷纷顺着呼救声围拢过去。

正当女班长姜梦淋转身张望时，身旁的李佳隆边跑边脱掉外套，冲向江中。“落水小孩离江岸就几米，感觉能救上来。李佳隆会游泳，第一个跳下水，把少年抓住，大家在岸上开始欢呼了。可是，很快我们发现他游着游着，忽然在原地不动了，其他同学赶紧跳下去帮助……”高阳说。

原来，因为没有水上救援经验，李佳隆被遇救少年紧紧抱住，活动受限，加之牛仔裤浸水后下沉，眼看就支撑不住了。这时，他一边拨水，一边向同学们大喊“不行了”……

见此情景，岸上的徐彬程、方招赶忙跳下水。徐彬程迅速游过去，从李佳隆手中接过落水少年，大家协力将他推上岸。事后，经核实，这名被救少年名叫陈天亮。

很快，救人溺水的李佳隆也被方招安全救出。李佳隆上岸后不停地呕吐，但思维还清醒，被岸上的高阳等同学送往医院。

与此同时，长江大学土木工程专业新生陈及时跳下水中，去救另一名溺水少年，不幸被卷入江水中。见情势危急，方招和徐彬程再次返回江水中救人，但此时江面上除了那名少年还在挣扎外，已经看不到陈及时的身影了。

岸上的同学们想出手拉手结成“人链”方法一起救人。

19岁的何东旭是班里的篮球队队长，平时就乐于助人，这次他主动和女班长姜梦淋换位，把自己换在“人链”最前端——同学透露，3个月前，何东旭才做过一次开胸手术。

一个更大的隐患埋下了——“人链”断裂时，前面的9人溺水，开始乱扑腾。

现场失控，同学们有的哭喊，有的呼救，有的报警求助。100米外的宝塔湾大堤上，3名冬泳爱好者闻声急忙赶来相救。他们是宝塔湾冬泳队队员韩德元、鲁德忠和杨天林。

捞尸者手牵绑尸绳谈价要钱好冷酷

“他们把捞尸体当作职业，只图赚钱，没有人性”

当冬泳爱好者、其他大学生、渔夫救出9名大学生和另外一名落水少年后，江面上就再看不到人影了——陈及时、何东旭、方招已经沉入江中。现场参与救援的两条渔船离开了宝塔湾，下水救人的冬泳队员韩德元、鲁德忠、杨天林也相继上岸。

按两艘渔船渔夫事后给警方的交代，此时因为江面上看不到目标，无法继续施救，所以他们离开了宝塔湾。

“江中救人和游泳池救人是完全不同的，一旦溺水者沉入流动的水中，根本找不到目标，很难施救。”对于渔夫的说法，多次参与水上救援的宝塔湾冬泳队队长王珏认为也不是没有一点道理。

渔船离开几十分钟后，两只打捞船向宝塔湾开来。此时，长江大学校领导也闻讯赶到事发现场。“‘活人不救，只捞尸体，打捞一个1.2万元，先交钱，后打捞。’对方开口就是这话……”在场的高阳说。打捞船开到后，没有一点救人的意思，所有的对话都围绕着一个钱字。“救援的理想时间是溺水后的5-7分钟，等打捞船赶到的时候，早已没有‘救人’的希望了。‘见死不救’之所以被误传，是因为同学们把在事发现场的渔船和后来赶到的打捞船混淆了。”王珏认为，救援和打捞的基本事实是：前期，渔夫参与了救人；后期，捞尸者拿不到钱不打捞。

当时校领导身上带的现金不够，答应对方先捞人，剩余的钱随后补上，但打捞船船主不干。其间有女同学“跪求”打捞船船主尽快救人，但对方就是坐在船上不动。无奈，师生们掏出身上所有的钱，凑了4000元交给对方，捞尸者才开始打捞，同时扬言：“钱不到位的话，只打捞一个”。

现场多名同学证实，打捞船船主挟尸要价。有的目击者还现场拍下照片为证：画面上，被打捞上来的一具大学生的遗体被绳子绑着，大半个身子浸在水里；一名穿白衬衫的老年男子，一边拉着绑尸体的绳子，一边摆手和岸上的师生谈价要钱，表情木然。捞尸者就干脆坐在船上等着学校领导派人回校取钱。打捞3具遗体，捞尸者前后一共收取了3.6万元。“他们把捞尸体当作职业，只图赚钱，没有人性！”赵超广说。“第一次真实接触社会，很受刺激。我们很单纯，他们只认钱，两个极端。”高阳说。

据长江航运公安局荆州分局调查，事发现场的两条渔船和后来赶到的两条打捞船，均来自长江对岸的公安县埠河镇，打捞船则专门以打捞尸体为职业。当地群众反映，这些捞尸者曾向他们发放印有“24小时服务，专业人员打捞”的名片，并称如果给他们提供打捞线索，给200元情报费。

挟尸要价事件曝光后，当地警方称有可能以涉嫌敲诈勒索追究其法律责任。知情者还爆料称，之所以敢开出天价捞尸费，是因为一个姓陈的打捞船船主垄断了这一带的打捞业务，其他人如果私自打捞就会受到恐吓甚至被砸船，有“黑社会”嫌疑。

在支持警方打击挟尸要价的同时，人们也不得不承认，捞尸者趁人之危向家属索要高价牟取暴利的事，在绝大多数江河沿岸都曾发生过。

2004年7月7日，武汉新河街幸福里社区一名11岁的小孩溺水，痛失爱子的家长赶至现场后一筹莫展，这时附近江面上的4条私人渔船闻讯赶至，并向家属开出了“捞上来3000元，捞不上来1500元，先交押金1000元”的价格。

2007年7月9日下午，兰州两名外地民工在黄河一沙坑游泳时溺水，接到求助的民警叫来羊皮筏子下水营救，但筏子主人因为费用问题几次放弃打捞救援。4名好心市民冒着生命危险下水义务营救，却遭到围观人群的起哄嘲笑。两个多小时后，溺水民工被捞起，但已气绝身亡。筏子主人得到了3000 元的打捞费。

回到这次宝塔湾事件。危险发生后，同学们第一时间报警求助，当地海事部门、水上派出所、公安消防人员赶到后，均以不具备条件、没有专业设备为由，未能提供有效救援和帮助。应该说，这正是打捞船挟尸要价的土壤。

紧急救援，这个本属于公益领域的服务被赤裸裸商业化和营利化，直接或间接地侵蚀着公民的生命健康权，让生命价值和人的尊严被利欲熏心所践踏。大学生舍己救人牺牲却遭遇捞尸者勒索，再次暴露了政府紧急救援(特别是水上救援)的缺失带来的严重后果。

陈波收钱捞尸的时候，并不知道三个大学生是因救人溺水的英雄。“如果当时知道他是英雄，我们把收的钱当场捐出来，不是名利双收吗？你说是不是？”夏兵说，“我们走错这步棋。等我们把钱收完了，别人再说他是英雄，我们也来不及了。舆论啊。”
这张相片在网络上引起极大争议

题目1. 一个任意的数组，找出一个严格单调递增的最长子序列。

例如: {3,0,1,7,2,4,5,9} –> output： {0, 1, 2, 4, 5, 9}

很简洁巧妙的算法，能在O(N log N)时间和O(N)空间做出来！

题目2. 玻璃杯/鸡蛋drop问题。有N层楼，假定是在 i 层楼扔鸡蛋，如果没有碎，那么在所有<=i 楼层扔鸡蛋都保证不会碎，反之如果碎了，那么保证在所有 >=i 楼层扔鸡蛋都必碎。通过若干次尝试扔鸡蛋，找到某个鸡蛋碎/不碎的”临界”层。允许你扔鸡蛋的总次数是D，允许你打碎的鸡蛋数是B。

问题的描述是：对一组给定的数（N D B），如果存在一个策略保证能在D B的限制下，在N层楼中找到“临界”层，那么称此(N D B)是Solvable的。接下来相关联的三个问题就是:

（a）给定D，B，求满足（N，D，B）Solvable的最大的N_max. 例：D=4，B=1， 策略是从第一层开始一层层往上. N_max=D=4.

（b）给定F，B，求最小的D_min

（c）给定F，D，求最小的B_min

这个问题相当容易找到看似最优的解，但是绝大部分的方法都不是最优的(最快最高效)。而且最迷惑人的是，(a)(b)(c)三个问题中，必须先从其中某一个下手开始解决，如果你不幸的先从另外的两个问题下手，多半离最优解遥遥无望。

如果你找到了正确的入手点，有了正确的思路，最后的答案会异常的简单！

题目3. 经典的概率悖论。3扇门，一扇背后有羊，你选中一扇门后，现在另外一扇门开了，里面是空的。问你是否应该重新选择。

分析：据观察，有一部分的人坚持认为一定要重新选择，另一部分的人认为是否重新选择都一样。另外少部分的人能看出，这个问题很巧妙的隐含了意识(主观intention)，信息和概率的关系！

题目4. 很简单的，N个数的数组，找出最大的和第二大的数，只用N+logN-2的比较次数，不需要额外空间。这个是典型的问题本身就是答案提示的题目--基于比较又有LogN，很显然思路涉及二分法，继续下去，剩下的问题就仅仅是找一个符合要求的Implementation了。

题目5. 找N！最后一个非零的数字。巧妙的方法可以在 LogN 时间内找出来，一个hint是利用 5^k（和log_5）划分问题

题目6. 任务分配，假设有N个任务，每个任务需要W_i工作量，M个人，每人每天能做工作量w_i，如何安排工作，使得所有工作能最快完成。这个问题其实更像一个开放性问题，因为一个合理的贪心策略，最后的结果跟最优结是很接近的(大致上，最多只差一天)。

题目7. 计算Fibonacci 数 F(n)，O(n)的算法是很trival的。但是有很漂亮简洁的Log(N)算法，思路是利用2*2矩阵表示Fibonacci递推式，然后用二分法的思想球矩阵的N次方。

题目8. 一颗BinaryTree，每个节点有个NULL指针，要求把每个节点和在BFS中它的下一个节点串起来。其他BinaryTree的常见题有比如非递归的实现遍历，用.parent or stack。思考这些题的经验是，对于这一类的树的题目，有很强的递归性/规律性，通常都是O(N)的复杂度，那么把N steps的问题，放在某个单step来研究，会把思路变得更清晰。另外一点就是，完全可以假设在做这一单步之前，在做这一步之前的问题已经最大可能的正确解决了，这样能够以一种数学归纳法的思想去利用之前的结论。比如这个题里面，假设节点 i 之前的节点都已经串好了，如何把 i 串到下一个节点。这个问题就是看一眼草图就能知道的了。最后一点经验是，在效率相当的算法的基础上，不同版本的实现，已经有能够互相启发的地方。

题目9. lookup table找0-255二进制数的set bit的数目。网上看到的源码，太赞了！

unsigned char BitSetCountTable256[256]
{
# define B2(n) n,     n+1,     n+1,     n+2
# define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
# define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
    B6(0), B6(1), B6(1), B6(2)
};

开车：

憋了一个寒假，想出去开开车的欲望越来越浓。寒假里倒是去了一趟六旗魔山，除了冲上云霄的刺激体验外，那片蔚蓝天空下金黄荒漠的景色，勾引起我对户外旷野的向往，但远远满足不了心里想要远走八方博览美景的愿望。不知道怎么回事，也许家乡是平原城市的原因，从小就喜欢野外的山岭，静幽的湖泊，浩瀚的旷漠，澎湃的汪洋，小的时候就图体验个稀奇拍照留影到此一游，写在作文里面的“亲近大自然”多少是搬来的辞藻。长大后，才慢慢的倒过来去欣赏和品味过去课本里所描绘的“大好河山”，才慢慢在心境上有所感悟。不光是亲近大自然，越是长大了，越有男儿走四方的志向，博览众态广瞰世间万象品味异乡风情文化，走南闯北的阅历才能堆成有血肉的人生和思想。

前阵子看个片子，非诚勿扰，看着看着，主线情节倒是没有多在意了，也没有多少兴趣。倒是若干场景的景色让我觉得心头一震，譬如杭州西溪那片静谧的湿地，中国民乐缭绕的茶馆，北海道明亮瑰丽旷野，伴着最后一丝夕阳的湖畔或是小港湾，小镇错落的民间建筑，广阔金黄麦田中的一处小基督教堂，云雾磅礴的海岸，山林中的清泉，乌云笼罩下平静的大海。。。实在是把我勾的心痒痒！也不是没见过风景图画的人，但是最撩人心的是那从天地分界线缓缓驶过的孤零零的一辆车，就给我感觉是我也能这样，开着自己的老牛车，驶过如此的画面，时而停下来小憩，裹着阳光微风和明媚的景色，拌在后备箱的饮料和肉里面，抚慰一下肚肚。实在忍不住，想出去开车，纯粹为了开车去开车，享受的就是这样一种人在旅途自由自在赏景的悠闲自得。

鸣谢xxl同学分享一条海边的驾车路线，终于有机会在昨天下午三点过，载着mm一起出去，从newport到dana point，从阳光灿烂的下午到染红海面的夕阳西下，往返在起伏的一号公路，眺望纷飞的海鸟，金黄闪耀的海面，山间盘绕的海景别墅，laguna小镇的酒吧杂货店，时不时穿过小镇居民区，一会儿又随着海风蜿蜒在海岸边上。心里的烦扰担忧，暂时的清空出去，敞开心情去开车，最后还真满载回了全心的清爽。

有的时候想到什么，没有写下来，一溜烟就过了，人长大了记性就变差，所以决定每一两天写写日志，也是一种时而反省自己的方式吧。

就从1月7号开始吧。