算法实战Array类型题目(二)

Java帮帮

共 1122字,需浏览 3分钟

 ·

2021-06-08 21:31

算法实战Array类型题目

这些题目又很多解法,个人只是针对不同得数据类型进行解答:

  1. 1.      爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

 

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

 

注意:给定 n 是一个正整数。

 

示例 1

2cd310a4e1b0e8a842e7c1b2697b43c6.webp



示例 2

602c806bed279e549062e480e2655a8a.webp



对于这种题目,第一眼我也是懵逼的,也许你会在纸上列举n110的不同结果找规律,

其实这题是斐波那契数列,公式 dp[n] = dp[n-1] + dp[n-2]dp[n]=dp[n1]+dp[n2]

因为你想爬上第n个台阶其实可以分为两个步骤:

1.爬上 n-1 阶楼梯的方法数量。因为再爬1阶就能到第n

2.爬上 n-2 阶楼梯的方法数量,因为再爬2阶就能到第n

你可能会想,这么考虑会不会遗漏,其实不会。

所以解题如下:

d6faffad10db2b5be73b8b64a7ccee52.webp



这是在leetcode上面的提交结果:

526683ea573917d064bf6a08882ef5d9.webp



注意一点,每道题他有很多解法,这里是为了熟悉数组,我们用数组进行解答。

 

 

 

2. 盛最多水的容器

给你 n 个非负整数 a1a2...an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线的两个端点分别为 (i, ai) (i, 0) 。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

 

说明:你不能倾斜容器。

 

示例 1

d4291aab2a49f1cbcd67f1c7cd1cf702.webp


303a9ae1cd2a06985ff69bc840d9bf94.webp




这题目一开始的思路是暴力法,我们可以遍历数组从下标0一直遍历到数组最后,然后看不同情况下,另外一一个高度不断遍历,求出最大值。但是这种解法算出来的事件复杂度为n的平方。

这时候有个解决方案:

双指针法:

指针每一次移动,都意味着排除掉了一个柱子

如下图所示我们一开始考虑最远的柱子所能容纳水的面积。水的宽度是两根柱子之间的距离 d = 8;水的高度取决于两根柱子之间较短的那个,即左边柱子的高度 h = 3。水的面积就是 3×8=24

357ffd17ab70f29f63a02c8d08f03c7e.webp



这个时候我们可以选择移动较小的0号柱子,为啥移动0号而不移动最右边的柱子,因为这个时候最右边的柱子比最左边的高,我们为了找到面积最大,高度被最左边的柱子高度控制住了,如果移动右边的柱子,那么高度可能不变或者更小,宽度是可定变小的,所以我们移动左边的柱子(高度较小的柱子)。每次的移动都是选择高度较小的柱子,因为宽度一直在变小。(这就是这题双指针方法的关键,每次移动的规则为高度小的柱子)然后把每次移动后算出的面积进行比较,最后得到最大的。

 

最后我们得出:

时间复杂度:O(N)O(N),双指针总计最多遍历整个数组一次。

空间复杂度:O(1)O(1),只需要额外的常数级别的空间。

 

这就是个人写的代码:

818ab0600494e27ee7e7a7514ea6fe84.webp



这是提交结果:

91e76f7f57391822b3fce90846c78323.webp



 


浏览 17
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报