c2c网站的功能,国内产品网站建设,项目管理软件有哪些优点,春考网页制作素材Leetcode数学部分笔记 1. 回文数2. 加一3. 阶乘后的零4. x 的平方根5. Pow(x, n) 1. 回文数
给你一个整数 x #xff0c;如果 x 是一个回文整数#xff0c;返回 true #xff1b;否则#xff0c;返回 false 。 回文数 是指正序#xff08;从左向右#xff09;和倒序如果 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[n1];digit[0] 1;return digit;}
}
3. 阶乘后的零
给定一个整数 n 返回 n! 结果中尾随零的数量。
提示 n! n * (n - 1) * (n - 2) * … * 3 * 2 * 1 解题思路用大白话讲一下找规律的思路
我们先以n7举个例子看一下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∗52∗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/5n/(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;}
}
