【每日刷题】Day3
🥕个人主页:开敲🍉
🔥所属专栏:每日刷题🍍
目录
1. 69. x 的平方根 - 力扣(LeetCode)
2. 70. 爬楼梯 - 力扣(LeetCode)
3. 118. 杨辉三角 - 力扣(LeetCode)
1. 69. x 的平方根 - 力扣(LeetCode)
//牛顿迭代法
int mySqrt(int x)
{
if(x<2)
{
return x;
}
double y = x/2.0;
double precision = 1e-6;
while(fabs(y*y-x)>precision)
{
y = (y+x/y)/2.0;//核心:牛顿迭代公式(泰勒级数展开)
}
return (int)y;
}
2. 70. 爬楼梯 - 力扣(LeetCode)
//动态规划思想
int climbStairs(int n)
{
int num[46] = {0};
num[0] = 1;
num[1] = 2;
num[2] = 3;
int i = 0;
if(n<=3)
{
return n;
}
for(i = 3;i<n;i++)
{
num[i] = num[i-1]+num[i-2];每一级台阶的跳法都等于上两级台阶的跳法之和
}
return num[i-1];
}
3. 118. 杨辉三角 - 力扣(LeetCode)
//具体思路:杨辉三角每一行的每一列元素都等于(上一行上一列元素+上一行当前列元素)
int** generate(int numRows, int* returnSize, int** returnColumnSizes)
{
int** arr = (int**)malloc(sizeof(int*)*numRows);//为数组开辟行空间
*returnSize = numRows;//行空间返回值写入行数
*returnColumnSizes = (int*)malloc(sizeof(int)*numRows);//为每一行开辟列空间,有多少行就开辟多少列
for(int i = 0;i<numRows;i++)//进入循环
{
arr[i] = (int*)malloc(sizeof(int)*(i+1));//为当前行开辟列空间
(*returnColumnSizes)[i] = i+1;//写入当前行的列空间数
arr[i][0] = 1;
arr[i][i] = 1;
for(int j = 1;j<i;j++)
{
arr[i][j] = arr[i-1][j-1]+arr[i-1][j];//当前行、列的数等于(上一行上一列元素+上一行当前列元素)
}
}
return arr;
}