温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

一行代码能做啥?题目难度为 Easy,目前通过率为 45.6%?你试试

发布时间:2020-08-10 08:34:40 来源:ITPUB博客 阅读:159 作者:千锋Python唐小强 栏目:编程语言

有很多伙伴跟我说,每次看完算法的文章,都觉得自己宛如一个智障,有木有同感的伙伴!(只要思想不滑坡,办法总困难多)

今天就不写太复杂的算法知识了,分享几道 LeetCode 上一行代码就能 AC 的算法题。可以瞅瞅你会不,哈哈哈!!!

一行代码能做啥?题目难度为 Easy,目前通过率为 45.6%?你试试

一,2 的幂

题目难度为 Easy,目前通过率为 45.6% 。

题目描述

给定一个整数,编写一个函数来判断它是否是 2 的幂次方。

题目解析

如果一个数是 2 的次方数的话,那么它的二进数必然是最高位为1,其它都为 0 ,那么如果此时我们减 1 的话,则最高位会降一位,其余为 0 的位现在都为变为 1,那么我们把两数相与,就会得到 0。

一行代码实现

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

二,3 的幂

题目难度为 Easy,目前通过率为 43.5% 。

题目描述

给定一个整数,写一个函数来判断它是否是 3 的幂次方。

题目解析

正常的思路是不停地去除以 3,看最后的迭代商是否为 1。这种思路的代码使用到了循环,逼格不够高。

这里取巧的方法  用到了数论的知识:3 的幂次的质因子只有 3

题目要求输入的是 int 类型,正数范围是 0 - 2 31 ,在此范围中允许的最大的 3 的次方数为 3 19 = 1162261467 ,那么只要看这个数能否被 n 整除即可。

一行代码实现

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

三,阶乘后的零

阶乘后的零。题目难度为 Easy,目前通过率为 38.0% 。

题目描述

给定一个整数  n ,返回  n ! 结果尾数中零的数量。

题目解析

题目很好理解,数阶乘后的数字末尾有多少个零。

最简单粗暴的方法就是先乘完再说,然后一个一个数。

事实上,你在使用暴力破解法的过程中就能发现规律:  这 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,然后求和即可。

一行代码实现

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

看完后是不是觉得也很简单,很多时候其实人都是有惰性的,不愿意尝试,你只有把它当个事情认真去想,去解,其实一点都不难!哈哈哈,是不是所谓的:只要思想不滑坡,办法总比困难多!加油!我的你们!


向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI