面试宝典之二 百度算法面试题分析

备注：几天之前凌晨6点醒了，也许是心血来潮，突然想用手机记下自己当时思考的几道百度算法面试题，

题目是在园子里看到的。草稿记在QQ日志草稿箱里。

已下为正文：

1.大整数相乘。

计算机表示整数的范围有限，那怎么实现两大整数相乘呢？

想了下没有思路，咨询了google大牛，看到有人是这样实现的:

大整数用字符串表示，每个大整数每一个数字字符转换为对应的整数，存入一维数组中，

然后被乘数的每一位数字分别与乘数的每一位数字相乘，结果保存在另一一维数组中，

此一维数组的大小为:被乘数的个数*乘数的个数，最后处理进位。

此方法用计算机模拟了两数相乘的过程。还有没有更好的方法?我暂时没查到也没想到。

既然大整数相乘计算机不能直接处理，自然而然会想到大整数相除呢？大整数相加呢？大整数相减呢？

大整数加减用计算机模拟人计算的过程很容易，难就难在大整数相除。

想到了两中方法:

1.对大整数因式分解，直至每个因子计算机能表示

2.跟乘法一样用计算机模拟，但是实现起来有些复杂，需要综合使用大整数乘法，大整数减法，大整数比较。

第二题很简单，这里就略过了。

3.有2n+1个数，有n个数重复，找出那个不同的数。

一开始没有完全理解有n个数重复这句话，要完成这道题很简单，可以先排序再找，也可以两重循环遍历，本来这道题没有分析的必要，

但是看了园友的回复，有一个很巧妙的方法，利用位运算的异或性质，时间复杂度为n,a异或b异或b=a,a异或b=b异或a.这手机坑爹啊，异或符号打不出来。

4.有个楼梯，每次只能上一阶或者两阶，到第N次的时候，总共走了多少阶？把所有可能的情况打印出来。

题目大概是这个意思。刚开始不知道怎么下手，每次走的阶数不固定，这有好多种情况，脑袋乱了，这可咋算？

根据概率来算有2的n次方种情况。看到园友的回复是一个费波那锲数列，园主的回答是可以使用动态规划，这些方法可以解决这个问题？

动态规划方法求最值才适用。某个时候突然想到:这个是不是可以使用递规来实现？

文章来源: aaaedu.blog.csdn.net，作者：tea_year，版权归原作者所有，如需转载，请联系作者。

原文链接：aaaedu.blog.csdn.net/article/details/50985776