[关闭]
@Yano 2019-09-20T10:54:09.000000Z 字数 2896 阅读 2292

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即可!这样在判断溢出时会非常简单。

代码

  1. public class Solution {
  2. public int reverse(int x) {
  3. long ans = 0;
  4. while(x != 0) {
  5. ans = ans * 10 + x % 10;
  6. x /= 10;
  7. if(ans > Integer.MAX_VALUE || ans < Integer.MIN_VALUE)
  8. return 0;
  9. }
  10. return (int)ans;
  11. }
  12. }

231. Power of Two

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

思路

代码

代码1:

  1. public class Solution {
  2. public boolean isPowerOfTwo(int n) {
  3. if(n <= 0) return false;
  4. return (n & (n - 1)) == 0;
  5. }
  6. }

代码2:

  1. public class Solution {
  2. public boolean isPowerOfTwo(int n) {
  3. if(n <= 0) return false;
  4. return (n & -n) == n;
  5. }
  6. }

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

代码

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

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的位置仅出现在奇数的位置上,例如

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

代码

  1. public class Solution {
  2. public boolean isPowerOfFour(int n) {
  3. if(n <= 0) return false;
  4. return ((n & (n - 1)) == 0) && ((n & 0x55555555) != 0);
  5. }
  6. }

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,所以是死循环!

  1. public int trailingZeroes2(int n) {
  2. int rt = 0;
  3. for (int i = 5; i <= n; i *= 5) {
  4. rt += n / i;
  5. }
  6. return rt;
  7. }

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

代码

  1. public class Solution {
  2. public int trailingZeroes(int n) {
  3. int rt = 0;
  4. for (long i = 5; i <= n; i *= 5) {
  5. rt += n / i;
  6. }
  7. return rt;
  8. }
  9. }

总结

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注