年中真的挺多人参加面试的，最近又收集到了不少算法相关的面试题。不过我觉得国内的算法面试题相对于国外的，还是有点差距吧。今天我们来看一看腾讯一道题目。
原题：
给你一个数n，有3种操作：
1.这个数加1
2.这个数减1
3.如果这个数是2的倍数，那么这个数除以2
问给你一个数n，问最少经过多少步，可以把这个数变成1
思考：
这个题目，与之前我们分析过的 《一天一算法题，将复杂问题进行分解！》那个优先用除法的子问题有点相似。唯一不同的是，这个题目同时可以用加减法。
那么多了这么一个点有什么不同呢？
举个栗子15，如果我们只用减法跟除法，那么这个题目的答案是：
15 - 1 = 14
14 / 2 = 7
7 - 1 = 6
6 / 2 = 3
3 - 1 = 2
2 / 2 = 1
总共需要6次操作
但是如果使用了加减法，就不需要这么多了。
15 + 1 = 16
16 / 2 = 8
8 / 2 = 4
4 / 2 = 2
2 / 2 = 1
这个只需要5次
是不是使用加法的策略更优呢？好像也不是，我们很容易就能举出反例，例如9.使用减除最少，需要4次。也就是有的数需要优先用加法，有的需要优先考虑减法。
想到这里，很多人其实就萌逼了，到底要使用加法还是减法呢？我们需要来看到问题的本质。
既然是除以2，那么非常大的可能是跟二进制有关系！我们如果用二进制来表示这个题目，那么这个题目可以等价于一个k位的二进制数，把它变成1.
我们来看一看三种操作，我们先看看除法！
除以2其实就是把末位0干掉！
这里我们隆重的迎接我们今天的主角，贪心算法。其实叫做贪心策略更加合适，贪心其实更像是一种思想。
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
既然要把变成有且仅有一个1，除2可以立马少掉1位，根据贪心思想，我们尽可能的使用/2操作。
在贪心策略的指引下，我们如果末位是0，就立马干掉！
接下来我们来看看，减1操作。
我们发现，-1操作只有2种可能，第一种不但没有增加0的个数，反而减少了，只有0才能够进行除以2.而第二种方法可以增加一个0.根据贪心的策略，我们选择了更优的第二种，只有当末位为1的时候，才考虑进行减1.
我们来看看+1的操作：
如
果最后一位是0，不但没有增加0的个数反而适得其反。这个我们不用。我们再看看第二种情况，虽然可以增加0的个数，但却把所有的增加了1位。如果进行这个
操作，我们需要进行多2个步骤。1是加1，2是需要多除一次。（本来除3次，现在变成4次了）。但是，我们减少了3次-1的次数。于是我们得出一个结论，
如果末尾有超过连续3个1，那么我们可以选择+1.
总结：
至此，我们把这个题目的策略整理出来了。
我们有如下的策略
1. 如果末尾是0，那么直接除以2.
2.如果末尾是1，并且末尾连续1的个数小于3，那么优先选择剪发，然后开始除法。
3.如果末尾超过连续3个1，那么先使用加法，再使用除法。
4,我们把n转成2进制，然后从低位开始，按上面的策略操作。
老规矩，如果是面试真题，不提供源代码。
贪 心算法，其实我觉得叫思想更为正确，现在国内的很多贪心的面试题，其实都要求你得到正确解。这点我觉得跟国外的面试差距很大 ，谷歌的贪心题目，经常是没有完美的贪心方案，但是，面试官会让你举出你使用的贪心策略的反例。这个更能考验面试者的思维，同时这种情况现实中更多。
原创不易，欢迎大家关注我的头条号，也可以关注我的微信公众号（ddpcyh）,后续会提供算法学习资料，一起来学习算法吧。
