第一题。给一个数组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;

}