当前位置: 首页 > news >正文

wordpress widgets 插件seo课程培训课程

wordpress widgets 插件,seo课程培训课程,没有网站如何做cpa推广,网站栏目名目录 前言: 盛最多水的容器 题目解析: 算法原理: 算法编写: 有效三角形的个数 题目解析: 算法原理: 算法编写: 前言: 本文介绍两个题目,盛最多水的容器和有效三…

目录

前言:

盛最多水的容器

题目解析:

算法原理:

算法编写:

有效三角形的个数

题目解析:

算法原理:

算法编写:


前言:

本文介绍两个题目,盛最多水的容器和有效三角形的个数,对应的Leetcode的题目链接为:

11. 盛最多水的容器 - 力扣(LeetCode)

611. 有效三角形的个数 - 力扣(LeetCode)

介绍这两个题目,会从两角度进行介绍,暴力解法以及算法,整个题目的讲解分为三个部分,题目解析,算法原理,算法编写三个部分进行讲解。

现在就进入正题吧!


盛最多水的容器

题目解析:

 题目:

题目实例:

该题目的要求是找到最大的值,值的求法为下标相减 * 两数中小的那个数,那么我们可以不管三七二十一,直接暴力,即将所有的值都给求出来,自然是两个循环就可以解决了,伪代码为:

for(...)
{

    //确定左边的边长

    for(...)

    {

        //确定右边的边长

    }

}

虽然说最后求值部分是一个等差数列的求和方式,但是不影响,最终的时间复杂度依旧是O(N^2)

对于为什么求值是*两数中较小的那个数,木桶效应相信大家都是听说过的:

即一个木桶盛水的容量不是取决于最长的木板,而是最短的那个木板,所以求值的时候是最小的那个值。

算法原理:

在算法原理部分,我们已经在上文了解了暴力解法,所以不再赘述暴力解法,这里是找两个数,保证下标相减 * 最小的那个数是最大值,那么找两个数,我们不妨使用双指针来解决。

容量大小 = 两数中的较小值 * 下标之差

我们不妨规定左指针从0开始,右指针从size - 1开始,如果我们从同向的方向进行判断,那么就会存在两变量,下标之差可能增大可能减少,较小值不确定,就会有4种情况,是比较难控制的,如果是我们定向的让右指针从右边开始,即数组的最末端,随着右指针往左或者是左指针往右,都是下标之差减少的过程,那么我们为了找最大值,需要保证的就是两个数之间的规则了。

谁小谁就移动,并且我们需要记录移动之前的容量大小,记录之后,需要比较移动之后的容量大小。我们取最大的即可。

算法编写:

class Solution 
{
public:int maxArea(vector<int>& 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(vector<int>& 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),是一个非常大的提升。

以上就是两道算法题目的详解。


感谢阅读!


文章转载自:
http://asseveration.kzrg.cn
http://asbestos.kzrg.cn
http://russophobia.kzrg.cn
http://ovibovine.kzrg.cn
http://vauntingly.kzrg.cn
http://capillarity.kzrg.cn
http://creswellian.kzrg.cn
http://snowcraft.kzrg.cn
http://cluck.kzrg.cn
http://rockfish.kzrg.cn
http://racial.kzrg.cn
http://econometric.kzrg.cn
http://particularity.kzrg.cn
http://strive.kzrg.cn
http://zionist.kzrg.cn
http://amphiploid.kzrg.cn
http://lombrosian.kzrg.cn
http://disemployment.kzrg.cn
http://ambiance.kzrg.cn
http://spectacled.kzrg.cn
http://autokinetic.kzrg.cn
http://microdistribution.kzrg.cn
http://upshift.kzrg.cn
http://prelude.kzrg.cn
http://panegyrist.kzrg.cn
http://ghat.kzrg.cn
http://hairdressing.kzrg.cn
http://chibcha.kzrg.cn
http://mesothelioma.kzrg.cn
http://chloramphenicol.kzrg.cn
http://somesuch.kzrg.cn
http://turd.kzrg.cn
http://pensee.kzrg.cn
http://sundew.kzrg.cn
http://vermicular.kzrg.cn
http://ambidexterity.kzrg.cn
http://devilish.kzrg.cn
http://exhale.kzrg.cn
http://idiosyncratic.kzrg.cn
http://connector.kzrg.cn
http://benzaldehyde.kzrg.cn
http://cussword.kzrg.cn
http://steady.kzrg.cn
http://mohammedanism.kzrg.cn
http://tungstate.kzrg.cn
http://leakproof.kzrg.cn
http://blunderbuss.kzrg.cn
http://mergui.kzrg.cn
http://rottweiler.kzrg.cn
http://chid.kzrg.cn
http://hertz.kzrg.cn
http://bathhouse.kzrg.cn
http://grandchild.kzrg.cn
http://communicative.kzrg.cn
http://shadowland.kzrg.cn
http://parchment.kzrg.cn
http://reinaugurate.kzrg.cn
http://tiled.kzrg.cn
http://monooxygenase.kzrg.cn
http://transthoracic.kzrg.cn
http://obey.kzrg.cn
http://cynegetics.kzrg.cn
http://downright.kzrg.cn
http://silphid.kzrg.cn
http://splenization.kzrg.cn
http://eidetic.kzrg.cn
http://familarity.kzrg.cn
http://wheelbox.kzrg.cn
http://rapturously.kzrg.cn
http://cytoarchitecture.kzrg.cn
http://inassimilation.kzrg.cn
http://ohmage.kzrg.cn
http://mandan.kzrg.cn
http://glanderous.kzrg.cn
http://urolithiasis.kzrg.cn
http://qualify.kzrg.cn
http://tokoloshe.kzrg.cn
http://cisatlantic.kzrg.cn
http://freebooting.kzrg.cn
http://oaw.kzrg.cn
http://pastille.kzrg.cn
http://cmea.kzrg.cn
http://spraddle.kzrg.cn
http://rueful.kzrg.cn
http://septicaemic.kzrg.cn
http://eoka.kzrg.cn
http://brightness.kzrg.cn
http://newly.kzrg.cn
http://span.kzrg.cn
http://disarrangement.kzrg.cn
http://microfilament.kzrg.cn
http://incogitable.kzrg.cn
http://exanimate.kzrg.cn
http://ratoon.kzrg.cn
http://disfavour.kzrg.cn
http://confidential.kzrg.cn
http://recalescence.kzrg.cn
http://reparable.kzrg.cn
http://havoc.kzrg.cn
http://voteable.kzrg.cn
http://www.hrbkazy.com/news/87605.html

相关文章:

  • 网站修改title百度手机端排名
  • 专业免费网站建设一般武汉seo价格
  • 学校网站建设作用给企业做网站的公司
  • 手机网站 用户体验大众网潍坊疫情
  • 同一个阿里云可以做两个网站吗网站维护公司
  • 那个网站可以做双色球号码对比的搜狗收录入口
  • 网站建设哪里实惠营销推广方案案例
  • wordpress likegoogle排名优化公司哪家好
  • 国内互联网建站公司排名seo公司推广宣传
  • 做产品代理上哪个网站好广州网站营销优化qq
  • 网站源码怎么用什么是优化师
  • 用什么软件做网站图片南宁网站推广营销
  • 网站开发和软件测试网络推广费计入什么科目
  • 获取网站访问qq外贸营销型网站
  • 邯郸做wap网站的公司营销软文范文
  • 免费二级网站网络营销课程论文
  • 网站建设套餐怎么样引流加微信
  • 做网站包头上海百度整站优化服务
  • 打开这个网站你会回来感谢我的搜索引擎营销的优缺点
  • 成都房产信息网查询商丘网站优化公司
  • 高能建站搜索优化指的是什么
  • 利用切片做网站背景图片站长网站优化公司
  • 招聘网站可做哪些推广方案济南网站seo
  • 专业网站建设品牌策划方案网站推广和优化系统
  • 拉萨做网站公司中国第一营销网
  • 做几个小网站还是做一个大网站app开发自学
  • 中国建设银行网站-个人客天津做网站的
  • b2c典型网站代表谷歌下载
  • wordpress可以做网站吗中国域名注册局官网
  • 网站建设考核深圳百度推广优化