一行代码能做什么？

点击蓝色“五分钟学算法”关注我哟
加个“星标”，一起学算法

今天周五临近放假，就不写太复杂的算法知识了，分享几道 LeetCode 上一行代码就能 AC 的算法题。

一2 的幂
题目来源于 LeetCode 上第 231 号问题：2 的幂。题目难度为 Easy，目前通过率为 45.6% 。
[h2]题目描述 [/h2]给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
[h2]题目解析 [/h2]如果一个数是 2 的次方数的话，那么它的二进数必然是最高位为1，其它都为 0 ，那么如果此时我们减 1 的话，则最高位会降一位，其余为 0 的位现在都为变为 1，那么我们把两数相与，就会得到 0。
[h2]一行代码实现 [/h2]

class Solution {public: bool isPowerOfTwo(int n) { return (n > 0) && (!(n & (n - 1))); } };

复制代码

二3 的幂
题目来源于 LeetCode 上第 326 号问题：3 的幂。题目难度为 Easy，目前通过率为 43.5% 。
[h2]题目描述 [/h2]给定一个整数，写一个函数来判断它是否是 3 的幂次方。
[h2]题目解析 [/h2]正常的思路是不停地去除以 3，看最后的迭代商是否为 1。这种思路的代码使用到了循环，逼格不够高。
这里取巧的方法用到了数论的知识：3 的幂次的质因子只有 3。
题目要求输入的是 int 类型，正数范围是 0 - 2[sup]31[/sup]，在此范围中允许的最大的 3 的次方数为 3[sup]19 [/sup]= 1162261467 ，那么只要看这个数能否被 n 整除即可。
[h2]一行代码实现 [/h2]

class Solution { public boolean isPowerOfThree(int n) { return n > 0 && 1162261467 % n == 0; }}

复制代码

三阶乘后的零
题目来源于 LeetCode 上第 172 号问题：阶乘后的零。题目难度为 Easy，目前通过率为 38.0% 。
[h2]题目描述 [/h2]给定一个整数 n，返回 n! 结果尾数中零的数量。
[h2]题目解析 [/h2]题目很好理解，数阶乘后的数字末尾有多少个零。
最简单粗暴的方法就是先乘完再说，然后一个一个数。
事实上，你在使用暴力破解法的过程中就能发现规律：这 9 个数字中只有 2（它的倍数）与 5 （它的倍数）相乘才有 0 出现。
所以，现在问题就变成了这个阶乘数中能配多少对 2 与 5 。
举个复杂点的例子：

10！ = 【 2 *（ 2 * 2 ）* 5 *（ 2 * 3 ）*（ 2 * 2 * 2 ）*（ 2 * 5）】

复制代码

在 10！这个阶乘数中可以匹配两对 2 * 5 ，所以10！末尾有 2 个 0。
可以发现，一个数字进行拆分后 2 的个数肯定是大于 5 的个数的，所以能匹配多少对取决于 5 的个数。
那么问题又变成了统计阶乘数里有多少个 5 这个因子。
需要注意的是，像 25，125 这样的不只含有一个 5 的数字的情况需要考虑进去。
比如

n = 15

复制代码

。那么在

15!

复制代码

中有

3

复制代码

个

5

复制代码

(来自其中的

5

复制代码

,

10

复制代码

,

15

复制代码

)，所以计算

n/5

复制代码

就可以。
但是比如

n = 25

复制代码

，依旧计算

n/5

复制代码

，可以得到

5

复制代码

个

5

复制代码

，分别来自其中的

5, 10, 15, 20, 25

复制代码

，但是在

25

复制代码

中其实是包含

2

复制代码

个

5

复制代码

的，这一点需要注意。
所以除了计算

n/5

复制代码

，还要计算

n/5/5 , n/5/5/5 , n/5/5/5/5 , ..., n/5/5/5,,,/5

复制代码

直到商为0，然后求和即可。
[h2]一行代码实现 [/h2]

public class Solution { public int trailingZeroes(int n) { return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5); }}

复制代码

[h1]
[/h1] 原创热文推荐

毕业十年后，我忍不住出了一份程序员的高考试卷
[/url][url=http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect]一道腾讯面试题：厉害了我的杯

[/url][url=http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484184&idx=1&sn=62965b401aa42107b3c17d1d8ea17454&chksm=fa0e6c99cd79e58f298e9026f677f912bd8c8e55edb48fc509b2b5834f05e529a9b47d59d202&scene=21#wechat_redirect]十大经典排序算法动画与解析，看我就够了！（配代码完全版）
[/url][url=http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485556&idx=1&sn=344738dd74b211e091f8f3477bdf91ee&chksm=fa0e67f5cd79eee3139d4667f3b94fa9618067efc45a797b69b41105a7f313654d0e86949607&scene=21#wechat_redirect]这或许是东半球分析十大排序算法最好的一篇文章
[/url][url=http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect]面试官，我会写二分查找法！对，没有 bug 的那种！

你点的每个“在看”，我都认真当成了喜欢