面试经典150题(111-113)

leetcode 150道题 计划花两个月时候刷完之未完成后转，今天（第5天）完成了3道(111-113)150
111.（172. 阶乘后的零）题目描述：

给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
示例 2：
输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0

第一版（今天题全是数学题。。原谅我真的看不懂。这个题意思就是求 5 的个数，然后每5个数后才出现一次）

class Solution {public int trailingZeroes(int n) {int count=0;while(n!=0){n/=5;count+=n;}return count;}
}

112.（69. x 的平方根 ）题目描述：

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

第一版（这个看了解题也没懂，这个二分查找是找有边界还是左边界。。欣赏一下吧）

class Solution {public int mySqrt(int x) {//二分查找int left=0;int right=x;int ans=-1;int mid=left+(right-left)/2;while(left<=right){mid=left+(right-left)/2;if((long)mid*mid<=x){ans=mid;left=mid+1;}else{right=mid-1;}}return ans;}
}

113.（50. Pow(x, n)）题目描述：

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

第一版（我是暴力了，然后就超时了，看了解题这个感觉好理解，也感觉面试可能会出现，n 由 int 转为 long 是因为测试例子有一个超了）

class Solution {public double myPow(double x, int n) {long N=n;double res=1.0;boolean flag=false;if(N<0){flag=true;N=-N;}while(N>0){if(N%2==1){res*=x;}x*=x;N/=2;}if(flag){return 1.0/res;}return res;}
}

今天总结就是一个字：难！！！！