LeetCode 数字 题目汇总

LeetCode解题链接

干货!LeetCode 题解汇总

7. Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321 Example2: x = -123, return -321

click to show spoilers.

Note: The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.

思路

要考虑的问题:

  • 负数
  • 溢出

对于溢出问题,因为是int型,在计算的过程中,我们只需要将计算的临时变量定义成long即可!这样在判断溢出时会非常简单。

代码

public class Solution {
    public int reverse(int x) {
        long ans = 0;
        while(x != 0) {
            ans = ans * 10 + x % 10;
            x /= 10;
            if(ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE)
                return 0;
        }
        return (int)ans;
    }
}

231. Power of Two

Given an integer, write a function to determine if it is a power of two.

思路

  • 可以根据 (n & (n - 1)) == 0 来判断,这是因为2的幂仅有1位是1,其余位全部是0;如果-1,那么1的那位会变成0,后面的位全部为1。
  • 可以根据 (n & -n) == n 来判断,这是 JDK 中 Ingeger 中使用的判断方法。因为 -n 的二进制表示,恰好相当于(n - 1)取反,而符号位本来就是不同的。本质上和上一种解放是一样的。

代码

代码1:

public class Solution {
    public boolean isPowerOfTwo(int n) {
        if(n <= 0) return false;
        return (n & (n - 1)) == 0;
    }
}

代码2:

public class Solution {
    public boolean isPowerOfTwo(int n) {
        if(n <= 0) return false;
        return (n & -n) == n;
    }
}

326. Power of Three

Given an integer, write a function to determine if it is a power of three.

Follow up: Could you do it without using any loop / recursion?

思路

如果n是3的幂,那么 n % 3 == 0

代码

public class Solution {
    public bool IsPowerOfThree(int n) {
        // 1162261467 是小于 Integer.MAX_VALUE 的3的最大幂数
        return n > 0 && (1162261467 % n == 0);
    }
}

342. Power of Four

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example: Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

思路

可以和上一题:Power of Three一样,使用作弊的方法……但是这道题显然是根Power of Two有关。思考一下,4的幂相对于2的幂,有哪些特点呢?

答案就是:在2的幂的基础上,位数为1的位置仅出现在奇数的位置上,例如

  • 0000 0001 = 1,是4的幂
  • 0000 0010 = 2,不是4的幂
  • 0000 0100 = 4,是4的幂

那么如何判断位数为1的位置仅出现在奇数的位置上呢?与上0x55(0101 0101)就好了!

代码

public class Solution {
    public boolean isPowerOfFour(int n) {
        if(n <= 0) return false;
        return ((n & (n - 1)) == 0) && ((n & 0x55555555) != 0);
    }
}

172. Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

分析

在面试时,曾遇到这样的一道题:

30!结果转换成3进制,结尾有多少个连续的0?

第一次做的话,感觉没有思路,但是换个角度想,转换成3进制,那么十进制中的1~30,哪些因子相乘,才会贡献出三进制结尾的0呢?当然是:3的倍数。

3, 6, 9, 12, 15 ,18, 21, 24, 27, 30

那么,每一个因子贡献了多少个0呢?

贡献了1个0的因子

3 = 3 * 1
6 = 3 * 2
12 = 3 * 4
15 = 3 * 5
21 = 3 * 7
24 = 3 * 8
30 = 3 * 10

贡献了2个0的因子

9 = 3 * 3
18 = 3 * 3 * 2

贡献了3个0的因子

27 = 3 * 3 * 3

30/3+30/9+30/27所代表的,就是最终结果。

这是因为:30/3把所有贡献了0的因子都算了一次,9、18、27已经被算过一次了,但是9和18还有一个因子没有算,27中还有两个因子没有算。

30/9则计算了一次9、18、27,但是27中还有一个因子没有算。

30/27计算了一次27,至此,所有的因子都计算完毕。

答案就是

30/3+30/9+30/27=10+3+1=14

分析本题

n!中,结尾有多少个连续的0

不能像上题一样,直接除以10……因为10可以拆分成两个因子,2和5。但是也不能除以2,因为在任何情况下,2的个数都会多余5的个数,所以,最终除以5就好啦!

100!中,结尾有多少个连续的0?

100/5 + 100/25 + 100/125 = 20 + 4 + 0 = 24

计算公式

在代码中,一定要注意溢出的问题,如下代码(我的第一个代码)就不能通过测试。因为在n很大时,比如Integer.MAX_VALUE,i *= 5溢出了,i一直是小于等于n,所以是死循环!

public int trailingZeroes2(int n) {
    int rt = 0;
    for (int i = 5; i <= n; i *= 5) {
        rt += n / i;
    }
    return rt;
}

解决方法,把n定义成long型。注意i也要定义成long型,否则在n很大时,主要是i * 5 > Integer.MAX_VALUE后会出错。

代码

public class Solution {
    public int trailingZeroes(int n) {
        int rt = 0;
        for (long i = 5; i <= n; i *= 5) {
            rt += n / i;
        }
        return rt;
    }
}

总结

对于数字的问题,本质上还是要回归到对数字本身的分析上,考察了数学的基本功。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1200 同余方程

1200 同余方程 2012年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目...

29240
来自专栏海天一树

小朋友学C语言(4):单精度浮点数与双精度浮点数

上节课 简单介绍了浮点数。计算机程序中的浮点数分为单精度浮点数和双精度浮点数。 单精度和双精度精确的范围不一样。 计算机里的最基本的存储单位用位(bit)来表...

408120
来自专栏TensorFlow从0到N

讨厌算法的程序员 5 - 合并算法

本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。 之所以把它独立成一篇,一方面是一旦...

35950
来自专栏灯塔大数据

每周学点大数据 | No.22 外排序

No.22期 外排序(一) Mr. 王:接下来我们看一看在磁盘算法中一个比较典型的例子——外排序。 小可:那什么又是外排序呢? Mr. 王:外排序是相...

37760
来自专栏程序生活

Leetcode-Easy 136. Single Number

136. Single Number 描述: 有一个数组,数字都出现两次,只有一个数字出现一次,找出现一次的数字 ? 思路: 现将数组去重...

30530
来自专栏韦弦的偶尔分享

Swift 只出现一次的数字 - LeetCode

给定一个整数数组,除了某个元素外其余元素均出现两次。请找出这个只出现一次的元素。 备注: 你的算法应该是一个线性时间复杂度。 你可以不用额外空间来实现它吗?

17210
来自专栏小文博客

十进制转换二进制(C语言)

42420
来自专栏SeanCheney的专栏

《Pandas Cookbook》第05章 布尔索引1. 计算布尔值统计信息2. 构建多个布尔条件3. 用布尔索引过滤4. 用标签索引代替布尔索引5. 用唯一和有序索引选取6. 观察股价7. 翻译SQ

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

21320
来自专栏陈树义

BloomFilter算法

Bloom filter 是由 Howard Bloom 在 1970 年提出的二进制向量数据结构,它具有很好的空间和时间效率,被用来检测一个元素是不是集合中的...

39580
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第12章 pandas高级应用12.1 分类数据12.2 GroupBy高级应用12.3 链式编程技术12.4 总结

前面的章节关注于不同类型的数据规整流程和NumPy、pandas与其它库的特点。随着时间的发展,pandas发展出了更多适合高级用户的功能。本章就要深入学习pa...

74370

扫码关注云+社区

领取腾讯云代金券