算法实战Array类型题目(二)
共 1122字,需浏览 3分钟
·
2021-06-08 21:31
算法实战Array类型题目
这些题目又很多解法,个人只是针对不同得数据类型进行解答:
1. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例 1:
示例 2:
对于这种题目,第一眼我也是懵逼的,也许你会在纸上列举n从1到10的不同结果找规律,
其实这题是斐波那契数列,公式 dp[n] = dp[n-1] + dp[n-2]dp[n]=dp[n−1]+dp[n−2]。
因为你想爬上第n个台阶其实可以分为两个步骤:
1.爬上 n-1 阶楼梯的方法数量。因为再爬1阶就能到第n阶
2.爬上 n-2 阶楼梯的方法数量,因为再爬2阶就能到第n阶
你可能会想,这么考虑会不会遗漏,其实不会。
所以解题如下:
这是在leetcode上面的提交结果:
注意一点,每道题他有很多解法,这里是为了熟悉数组,我们用数组进行解答。
2. 盛最多水的容器
给你 n 个非负整数 a1,a2,...,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明:你不能倾斜容器。
示例 1:
这题目一开始的思路是暴力法,我们可以遍历数组从下标0一直遍历到数组最后,然后看不同情况下,另外一一个高度不断遍历,求出最大值。但是这种解法算出来的事件复杂度为n的平方。
这时候有个解决方案:
双指针法:
指针每一次移动,都意味着排除掉了一个柱子。
如下图所示我们一开始考虑最远的柱子所能容纳水的面积。水的宽度是两根柱子之间的距离 d = 8;水的高度取决于两根柱子之间较短的那个,即左边柱子的高度 h = 3。水的面积就是 3×8=24。
这个时候我们可以选择移动较小的0号柱子,为啥移动0号而不移动最右边的柱子,因为这个时候最右边的柱子比最左边的高,我们为了找到面积最大,高度被最左边的柱子高度控制住了,如果移动右边的柱子,那么高度可能不变或者更小,宽度是可定变小的,所以我们移动左边的柱子(高度较小的柱子)。每次的移动都是选择高度较小的柱子,因为宽度一直在变小。(这就是这题双指针方法的关键,每次移动的规则为高度小的柱子)然后把每次移动后算出的面积进行比较,最后得到最大的。
最后我们得出:
时间复杂度:O(N)O(N),双指针总计最多遍历整个数组一次。
空间复杂度:O(1)O(1),只需要额外的常数级别的空间。
这就是个人写的代码:
这是提交结果: