Leetcode数学部分笔记

1. 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数
是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。

解题思路：
把回文数转为String类型，然后让StringBuffer存储后再逆置，看看和原本的String相同不。

class Solution {public boolean isPalindrome(int x) {String str1 = String.valueOf(x);StringBuffer buffer = new StringBuffer();buffer.append(str1);return str1.equals(buffer.reverse().toString());   }
}

2. 加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

**解题思路：**逆序遍历这个数组，让最后一位加一，再让遍历的这一位和10取余，如果结果不为0，则说明没有进位，直接返回。如果遍历结果为0，则说明有进位，让倒数第二位继续加1，在判断是否有进位。
遍历一遍以后，如果都有进位，则说明需要扩大一个空间，让第一位为1。

在这里插入代码片

class Solution {public int[] plusOne(int[] digits) {int n = digits.length;for(int i = n-1;i >= 0; i--){digits[i] ++;digits[i] = digits[i] % 10;if(digits[i]!=0) return digits; }int[] digit = new int[n+1];digit[0] = 1;return digit;}
}

3. 阶乘后的零

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

提示 n! = n * (n - 1) * (n - 2) * … * 3 * 2 * 1

解题思路：用大白话讲一下找规律的思路：

我们先以n=7举个例子，看一下7!末尾有几个0。

我们把7!展开来看下：

7!=1∗2∗3∗4∗5∗6∗7
我们知道，只有2∗5才可以得到一个0，那我们只需要看7!可以分解为多少个2∗5就可以。

2出现的频率肯定是高于5的，因为:

每隔 2 个数就会包含因子2，比如2,4,6,…，
而每个 5 个数才会出现一个包含因子5的数，比如5,10,15,…
那我们的题目就可以转换为，n!最多可以分解出多少个因子5。

对于n!，5 的因子一定是每隔 5 个数出现一次，也就是下边的样子。

n!=1∗2∗3∗4∗(1∗5)∗…∗(2∗5)∗…∗(3∗5)∗…∗n
但我们还会发现，每隔 25(5*5) 个数字，出现的是 2 个 5，如下：

…∗(1∗5)∗…∗(1∗5∗5)∗…∗(2∗5∗5)∗…∗(3∗5∗5)∗…∗n
比如1∗5∗5，2∗5∗5，里面包含了 2 个 5。

同理，每隔 125(555)个数字，出现的是 3 个 5，如下:

…∗(1∗5)∗…∗(1∗5∗5∗5)∗…∗(2∗5∗5∗5)∗…∗(3∗5∗5∗5)∗…∗n
那么，我们要计算n!中一共有多少个因子5的话，计算方法方式就应该是：

每隔5个数出现一次的因子5的次数+每隔25个数出现一次的因子5的次数+…
也就是:

n/5+n/(5∗5)+n/(5∗5∗5)+…

class Solution {public int trailingZeroes(int n) {int count = 0;// 每次循环都将 n 除以 5，统计有多少个 5 的因数while (n >= 5) {n /= 5; // 每五个数中会引入一个 5count += n; // 统计所有包含 5 的数}return count; // 返回尾随零的数量}
}

4. x 的平方根

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

解题思路：二分查找，如果小于等于了，就存一个最大的mid，如果大于等于了，就让r = mid - 1

class Solution {public int mySqrt(int x) {int l = 0, r = x, ans = -1;while (l <= r) {int mid = l + (r - l) / 2;if ((long) mid * mid <= x) {ans = mid;l = mid + 1;} else {r = mid - 1;}}return ans;}
}

5. Pow(x, n)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。

把指数都变成正的，如果是负的则进行除法操作。
对指数N进行拆分，如果和2取余等于1，则说明需要称一次，其他时候乘两次

class Solution {public double myPow(double x, int n) {long N = n;return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);}public double quickMul(double x, long N) {double ans = 1.0;// 贡献的初始值为 xdouble x_contribute = x;// 在对 N 进行二进制拆分的同时计算答案while (N > 0) {if (N % 2 == 1) {// 如果 N 二进制表示的最低位为 1，那么需要计入贡献ans *= x_contribute;}// 将贡献不断地平方x_contribute *= x_contribute;// 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可N /= 2;}return ans;}
}