倒v是网站设置的还是作家自己,公众号开发者密码是什么,做卡盟网站,网建会是什么意思目录
前言#xff1a;
盛最多水的容器
题目解析#xff1a;
算法原理#xff1a;
算法编写#xff1a;
有效三角形的个数
题目解析#xff1a;
算法原理#xff1a;
算法编写#xff1a; 前言#xff1a;
本文介绍两个题目#xff0c;盛最多水的容器和有效三…目录
前言
盛最多水的容器
题目解析
算法原理
算法编写
有效三角形的个数
题目解析
算法原理
算法编写 前言
本文介绍两个题目盛最多水的容器和有效三角形的个数对应的Leetcode的题目链接为
11. 盛最多水的容器 - 力扣LeetCode
611. 有效三角形的个数 - 力扣LeetCode
介绍这两个题目会从两角度进行介绍暴力解法以及算法整个题目的讲解分为三个部分题目解析算法原理算法编写三个部分进行讲解。
现在就进入正题吧 盛最多水的容器
题目解析 题目 题目实例 该题目的要求是找到最大的值值的求法为下标相减 * 两数中小的那个数那么我们可以不管三七二十一直接暴力即将所有的值都给求出来自然是两个循环就可以解决了伪代码为 for(...) { //确定左边的边长 for(...) { //确定右边的边长 } } 虽然说最后求值部分是一个等差数列的求和方式但是不影响最终的时间复杂度依旧是O(N^2)
对于为什么求值是*两数中较小的那个数木桶效应相信大家都是听说过的 即一个木桶盛水的容量不是取决于最长的木板而是最短的那个木板所以求值的时候是最小的那个值。
算法原理
在算法原理部分我们已经在上文了解了暴力解法所以不再赘述暴力解法这里是找两个数保证下标相减 * 最小的那个数是最大值那么找两个数我们不妨使用双指针来解决。 容量大小 两数中的较小值 * 下标之差 我们不妨规定左指针从0开始右指针从size - 1开始如果我们从同向的方向进行判断那么就会存在两变量下标之差可能增大可能减少较小值不确定就会有4种情况是比较难控制的如果是我们定向的让右指针从右边开始即数组的最末端随着右指针往左或者是左指针往右都是下标之差减少的过程那么我们为了找最大值需要保证的就是两个数之间的规则了。
谁小谁就移动并且我们需要记录移动之前的容量大小记录之后需要比较移动之后的容量大小。我们取最大的即可。
算法编写
class Solution
{
public:int maxArea(vectorint height){int left 0, right height.size() - 1;int ret 0,ans 0;while(right left){ret min(height[left],height[right]) * (right - left);ans max(ret,ans);if(height[left] height[right]) right--;else left;}return ans;}
};
此时就完美通过了。 有效三角形的个数
题目解析
题目 题目示例 通过示例我们可以得出来一个结论是下标不同数值相同的元素我们可以使用即便组成的三角形是一样的。根据题目要求我们首先得到的一个信息是我们需要通过判断获取到的三个元素是否能构成三角形那么根据初中的理论三角形的充要条件是任意两边之和大于第三边。
难道我们判断三角形的时候就都要写三个条件吗那是不是有点太麻烦了这点先不管题目中还有的提示是数组是非负的整数数组也就是不会出现非整数和负数我们返回值是能构成三角形的个数。题目要求不多解析到这里已经差不多了。
算法原理
还是那句话遇事不决先暴力。
这道题的暴力解法是很简单的我们只需要三个循环一个循环找一条边即可
for()
{for(){for(){//判断三角形是否成立}}
}
但是时间复杂度也是惊人的高达到了O(N^3)一般leetcode上这种题到最后几个样例的时候O(N^3)一般都是会超时的。
所以我们需要另辟蹊径那么就使用双指针算法对于双指针来说影响的是两个数这是可是三个数我们应该如何操作呢
我们不妨借助单调性如果借助单调性我们碰见一组数我们就要判断是否为三角形这是否太麻烦了那么有了单调性比如a b c随着指针往右边走两个小的数都大于c了其他的数还能不大于吗到那个地步我们可以直接ans 下标之差了后面的肯定是符合条件的。那么c为最大边的所有三角形找到了--即可。
算法编写
class Solution
{
public:int triangleNumber(vectorint nums) {int ans 0;sort(nums.begin(),nums.end());for(int i nums.size() - 1; i 2 ;i--){int left 0,right i - 1;while(left right){if(nums[left] nums[right] nums[i]) ans (right - left),right--;else left; } }return ans;}
};
此时的时间复杂度为O(N^2)相对于O(N^3)是一个非常大的提升。
以上就是两道算法题目的详解。 感谢阅读
