算法题的思考

最近遇见两个算法题，当时没有想到比较好的办法，第二天在公交上思考了一下，感觉像是比较不错的解题方法，今天记录一下。公交车是一个不错的思考场所！

一、有一个数组，长度为n，其中有若干个0，且不知道这些0所在的数组下标。要求：在不能开辟另外数组的情况下，用最少的空间复杂度和时间复杂度把所有的0排到最后去，且原来的非零数前后顺序不变。

我一开始的思路是记录0的个数x，遍历数组，找0便把后面的所有数往前挪一位，然后把数组最后一个元素赋值为0，x+1。接着再找，找到第二个0，继续把后面的往前挪，然后把数组倒数第二个元素赋值为0，x+1。继续此方法，直至遍历到下标为 n - x - 2 的元素。想想效率太差了，最差的情况下要交换  (n - 1 +1) / 2 * (n - 1)次,时间复杂度为O(n2)，空间复杂度为O(0)拙劣的思考。

后面我思考到了一个比较不错的方法：遍历数组，找到0之后记录该元素的下标index，继续往后遍历，找到第一个非零元素（因为0后面可能又接着是0），让该元素和下标为index的元素交换，接着做index++；继续往后遍历，找到接下来的第一个非零元素，让该元素和下标为index的元素交换，接着做index++......一直继续执行该操作至遍历到数组最后一个元素，大功告成！最差的情况下要交换n - 1 次,时间复杂度为O(n)，比之前思考的那一个方法快了一个指数级。

这个问题我只能优化到这里了，希望某一天我可以思考到更好的方法。

二、甲上楼需要走20个阶梯，每次可能走1步，也可能走2步。问有多少种走法？

其实这就是一个贪心算法，我一开始的思路是排列组合里面的捆绑。拆解：1、假设没有走两步，那么便是1种走法。2、假设只走了一次两步，那么把这两步捆绑在一起，插在其它18步的任意一步的前面后者后面，那么总共有19种走法。3、假设走了两次两步，捆绑插入那么便是17 * 18 / 2种走法。。。继续算下去至走了十次两步。乍一看我这个方法还不错，解决了问题，也能算出正确答案，但是有两个缺点。缺点1：容易算错，公式要用的比较细心。缺点2：如果题目是可能走1步，2步，也可能是3步，或者4步，那我这解法就要弄得更复杂才能解决这问题了。不能灵活变化的解法都不是好解法。

好解法当然还是有的，有人提醒我其实是一个斐波那契数列的应用。

原来如此！20步可能是19步+1步，也可能是18步+2步。那么f(20) = f(19) + f(18)，我只要算19步的走法数加上18步的走法数就好了，而f(19) = f(18) + f(17)，所以f(20) = f(18) + f(17) + f(18)，继续递归到右边的式子都是f(2) 和f(1)，那么问题也就只是个加法运算了。如果有走3步的可能，也同样可以使用该方法。

三、有15个瓶子，其中最多有一瓶有毒，现在有四只老鼠，老鼠喝了有毒的水之后第二天就会死。如何在第二天就可以判断出哪个瓶子有毒？

这个看到15瓶就知道怎么做了，最多一瓶有毒，所以共15+1=16种结果，而有4老鼠，用排列组合算一下就OK了。把老鼠编号A、B、C、D，把水编号1、2、3、4....14、15。解决方法：把1给A喝，2给B喝，3给C喝，4给D喝，5给A和B喝，6给A和C喝，7给A和D...10给C和D，11给A、B、C喝...14给B、C、D喝，15给所有老鼠都喝。

毒死1只老鼠：共4种。比如D死则4号水有毒。

毒死2只老鼠：共6种。比如A和D死则7号水有毒。

毒死3只老鼠：共4种。比如B、C、D死则14号水有毒。

毒死4只老鼠：共1种。15号水有毒。

毒死0只老师，共1种，也就是所有水都没毒。

根据毒死的结果就可以知道是哪瓶有毒了。

四、给定能随机生成整数 1 到 5 的函数，写出能随机生成整数 1 到 7 的函数。

看到题目是挺懵逼的，思考了很久想了一个答案，但没有完美解决这个问题。

5的幂都不能被7整除，所以只能曲线救国。f(a) = random（5）*  5 - random（5）+1 可以得到1-25的25个数其中的一个a，所有结果出现的概率相等。如果a是前面21个数除以3分别可以得到0-6其中的一个，如果是22-25中的其中一个，则再做一次f(a)，再用刚才的判断方法进行后续的步骤。

记录到这里，加油！