阿里巴巴校招面试题目，还是不是十分确定，来问问大家

Ager

InMySin 发表于 2012-10-28 21:23
这个估计大家都看见过的题目，但是我google搜素效果却不是很好，丫的居然没找到。。KuMa！

事情是这样的 ...

不需要递归，用单纯的循环可以做的：

首先，我们从最简单的1x1网格开始：

1. x-x
   
2. | |
   
3. o-x

复制代码

我们约定：用“u”表示“往上走一步”，用“r”表示“往右边走一步”。

根据题意，小dot（o）“每次走都只能往上或者往右走一步”，那么，对于1x1网格，小o的走法只能有两种：

1：ur
2：ru

继续，我们以“日”字即2x1网格为例：

1. x-x
   
2. | |
   
3. x-x
   
4. | |
   
5. o-x

复制代码

很简单，小o的走法，只能有3种：

1：uur
2：uru
3：ruu

我们发现，对于mxn网格，小o的路径中，u一定出现m次、r一定出现n次。

此时，我们不再以u和r做标记，而以0与1代替之。

很显然，对于mxn网格，小o的走步次数，一定是m+n次。

那么，我们构造一个序列（构造序列的技巧是：将整数0 -> 整数2^(m+n)-1分别用位向量表示）：

1. 000....000（有m+n位，下同）
   
2. 000....001
   
3. 000....010
   
4. 000....011
   
5. 000.......
   
6. 111....110
   
7. 111....111

复制代码

这个序列中的每一项，都是m+n位数的。

所以，完整的序列，一定有2^(m+n)项，而这么多项中，有许多项，是不符合题意的，我们怎么把它们剔除掉呢？

很简单，上面我们已经认识到：小o的路径中，u一定出现m次、r一定出现n次，即0一定出现m次、1一定出现n次。

0一定出现m次、1一定出现n次 —— 这意味着：将序列中的每一项里的位按权1累加起来，如果和==n，（24楼有超级简便方法）即是符合题意的路径。

解毕。

Ager

linux_c_py_php 发表于 2012-10-28 22:47
动态规划肯定是可以的.

龙哥来刷版了，用的是24K金粉！！！！

Ager

linux_c_py_php 发表于 2012-10-28 23:06
{:3_184:}

Ager

@InMySin

InMySin 发表于 2012-10-29 11:41
回复 3# Ager
求一个路径的 00...11 中的1的计算量为 m+n; 然后需要进行 2^(m+n) 次比较， 会可能到达 (m+n)*2^(m+n)，这样复杂度有点高。。
一是要改进计算1的个数的方法（可不可以参考计算一个二进制数中1的个数，CU就出现过，很神奇方法）

烦那个神干嘛呀……在GNU这边，可以直接用：

int __builtin_popcount (unsigned int x)


呵呵……