Joyce' Blog
0%

sqrtx & climbing-stairs

发表于

题目描述

实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

题解

二分法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int mySqrt(int x) {
	if (!x||x==1)return x;
	int left = 0, right = x;
	//left不应从1开始，否则right=INT_MAX时，left+right会越界
	int mid;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (x / mid >= mid && x / (mid+1) < (mid + 1))return mid;
		else if (x / mid < mid)right = mid;
		else left = mid;
	}
	return left;
}

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。

题解

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int climbStairs(int n) {
	if (n <= 2)return n;
	int step;
	int step1 = 1;
	int step2 = 2;
	int i = n - 3;
	while (i >= 0)
	{
		step = step1 +  step2;
		step2 = step1;
		step1 = step;
		i--;
	}
	return step;
}