LeetCode 数字 题目汇总

LeetCode

公众号

coding 笔记、点滴记录，以后的文章也会同步到公众号（Coding Insight）中，希望大家关注^_^

https://github.com/LjyYano/Thinking_in_Java_MindMapping

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;
    }
}

总结

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