计算并返回 x 的平方根,其中 x 是非负整数。 由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
示例 1:
输入: 4 输出: 2
示例 2:
输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。
分析 本题有三个方法求解分别为:
- 暴力求解(不推荐)
- 二分查找(推荐)
- 牛顿迭代法
对于本题,笔者就实现一个二分查找找到这个数字,而牛顿迭代法有空可以自行学习(也不是很难原理可以找专门文章看一看)。
public int mySqrt(int x) {
//二分
int l=0,r=x/2+1;
while (l<r) {
long mid=(l+r)/2;
if(mid*mid<=x)
{
if((mid+1)*(mid+1)<=x)
{
l=(int) (mid+1);
}
else {
return (int) mid;
}
}
else {
r=(int) mid;
}
}
return l;
}
分析:
入门dp,状态转移方程为:初始赋值好后,dp[i]=dp[i-1]+dp[i-2];
public int climbStairs(int n) {
if(n<3)return n;
int dp[]=new int[n+1];
dp[1]=1;
dp[2]=2;
for(int i=3;i<n+1;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
原创不易,bigsai请你帮两件事帮忙一下:
-
star支持一下, 您的肯定是我在平台创作的源源动力。
-
微信搜索「bigsai」,关注我的公众号,不仅免费送你电子书,我还会第一时间在公众号分享知识技术。加我还可拉你进力扣打卡群一起打卡LeetCode。
记得关注、咱们下次再见!