算法进修Day-35

本文主要是介绍算法进修Day-35，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法进修Day-35

69. x的平方根

难度：简单
题目要求：
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例1

输入：x = 4
输出：2

示例2

输入：x = 8
输出：2

题解

使用二分查找，定义 $high=x$ 和 $low=1$ 来表示上下边界，进行如下操作

• 如果 $x=0$，那么直接返回0
• 如果 $low<high$，那么定义 $mid=low+(high-low+1)/2$，如果$(mid\ast mid)\le x$ 那么让 $low=mid$，否则 $high=mid-1$

遍历结束之后直接返回 $low$

想法代码

class Solution
{public static void Main(String[] args){Solution solution = new Solution();int x = 36;int res = solution.MySqrt(x);Console.WriteLine(res);}public int MySqrt(int x){int low = 1;int high = x;if (x == 0){return 0;}while (low < high){int mid = low + (high - low + 1) / 2;if ((long)mid * mid <= x){low = mid;}else{high = mid - 1;}}return low;}
}

70. 爬楼梯

难度：简单
题目要求：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例1

输入：n = 2
输出：2

示例2

输入：n = 3
输出：3

题解

使用回溯法，使用数组 $array$ 来存储总计的内容，定义 $array[0]=1,array[1]=1$
回溯法方法如下：

• 如果数组的第n个元素不是0，那么，直接返回第n个元素
• 根据第1，2，3，4层方法得出的结果来看，结果为斐波那契数列，所以第n层方法为 $(n+1)+(n+2)$
• 定义 $x$ 为回溯方法的第 $n-1$ 层
• 定义 $y$ 为回溯方法的第 $n-2$ 层
  最后 $array[n]=x+y$ 并返回

想法代码

class Solution
{public static void Main(String[] args){Solution solution = new Solution();int n = 3;int res = solution.ClimbStairs(n);Console.WriteLine(res);}public int ClimbStairs(int n){int[] array = new int[n + 1];array[0] = 1;array[1] = 1;return ChangeArray(n,array);}public int ChangeArray(int n, int[] array){if (array[n] != 0){return array[n];}int x = ChangeArray(n-1, array);int y = ChangeArray(n-2, array);array[n] = x + y;return array[n];}
}

这篇关于算法进修Day-35的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---