登陆

极彩娱乐在线平台-LeetCode基础算法题第1046.Last Stone Weight

admin 2019-10-27 190人围观 ,发现0个评论

技能进步是一个按部就班的进程,所以我讲的leetcode算法题从最简略的level开端写的,然后到中级难度,终究到hard难度悉数完。现在我挑选C言语,Python和Ja极彩娱乐在线平台-LeetCode基础算法题第1046.Last Stone Weightva作为完成言语,因为这三种言语仍是比较典型的。因为篇幅和精力有限,其他言语的完成有爱好的朋友请自己测验。

假如有任何问题能够在文章后谈论或许私信给我。

假如有朋友期望我讲些其他论题,请在谈论区留言或许私信给我。

持续共享,敬请重视。

LeetCode 1046. 终究一个石头的分量(Last Stone Weight)

问题描绘:

咱们收集了一些石头,每一个石头的分量都是正整数。现在,要求选出两个最重的石头损坏它们,假定它们的分量别离是x和y,x <= y,那么损坏的成果是:假如 x == y,它们都被一起彻底毁掉;假如 x != y,那么分量为x的会被彻底毁掉, y会被毁掉分量x后,剩余的y-x放回去。如此这样,终究仅有一个石头留下来,回来石头的分量(假如没有石头留下了,回来0)

注:

  • 1 <= stones.length <= 30;
  • 1 <= stones[i] <= 1000;

示例:

C言语完成:

解题的关键是,怎么找到两个最大分量。

因为每次找到两个最大分量后还要将它们的差值丢进去。所以假如差值不为0,那么或许影响下一轮最大值的查找。(留意假如两个石头相同重,它们的差值是0,表明的是,没有任何极彩娱乐在线平台-LeetCode基础算法题第1046.Last Stone Weight石头留下,因而从头放回,不影响下一轮最大值的查找)

解题办法至少有3种。

第一种:排序

将stones依照从大到小的次序排序,那么前两个数便是最大两个分量,核算它们的差后,丢进去,持续下一轮排序。

留意每次操作后,要排序的元素个数就少一个。

这个算法的时刻复杂度比较高。

第二种:只取两个最大数

从左到右,经过彼此比较,只是找到两个最大的分量,这样每次的查找的时刻复杂度是线性的。

核算出差值后,从头将差值丢回去,再如此,进入到下一轮。

因为每一轮操作后,要查找的元素个数都会少一个,所以算法的复杂度为O(n^2)。

第三种:用最大堆

关于最大堆,咱南航电话们前面的标题中用过。

最大堆是一种二叉堆,它是一种彻底二叉树。特点是,关于每个子树,它的根节点都要比一切的子节点大。

为什么要用最大堆?因为最大堆获取最大元素的复杂度是常数级的,而它的刺进复杂度是O(logn)。所以十分合适解这道题。

咱们要点来阐明用最大堆的完成。

1.二叉堆的结构

首要咱们界说函数heap_create,根据stones来结构一个最大堆,它内部调用heap_insert来完成具体堆元素的刺进。

该结构办法是经过每次在叶子节点增加元素,再让元素上浮的办法,这种办法功率通常是比较高的。上浮的原理便是不断的和父节点比较并替换的进程,具体示意图和阐明能够参阅《第123篇》极彩娱乐在线平台-LeetCode基础算法题第1046.Last Stone Weight。

咱们阐明一下最大堆的存储结构。咱们前面讲过,因为最大堆是一个彻底二叉树,所以能够用数组来寄存二叉堆。下图是一个二叉堆和彻底二叉树的对应联系:

可见关于下标为x的元素,它的左右子节点的下标别离是2x+1和2x+2;相同它的父节点的下标是(x-1)/2。

得到这些信息后,咱们就能够很简单完成堆的结构。

2.毁掉石头

堆结构完成后,咱们就要开端毁掉作业。

1). 咱们需求获取最大的两个元素,很简略,最大堆的根节点(即堆数组的首元素)便是最大的。咱们经过两次弹出根元素,就能够取得两个最大的元素。

可是留意,每次弹出根节点后,堆结构就会被损坏,咱们需求在每次弹出后,重构堆结构, 办法是:

当根弹出后,将终究一个叶子节点,复制到堆的开始方位,作为暂时的根节点,然后经过下沉的办法重构堆结构,这个进程,新的最大元素会上浮终究成为新的根节点。

2).当咱们获取两个最大元极彩娱乐在线平台-LeetCode基础算法题第1046.Last Stone Weight素后,核算它们的差值,并将这个差值从头刺进进堆数组中。

留意这个进程中,每毁掉一个石头,堆巨细就会减一。(假如两个石头巨细相同,咱们能够以为只毁掉其间一个,它们的差0被放回,因为0不影响终究成果)

咱们重复这个毁掉进程,直到堆巨细为1的时分,阐明里边只要一个石头了,回来它的巨细即可。

下面是这个进程的示意图:

首要结构堆,结构完成后,别离弹出78和38,并重构堆成果,然后将它们的差,40放回到堆中。灰色的元素是这个进程中失效的元素。

具体代码如下:

终究留一个问题给咱们:

这个用最大堆完成的算法,它的复杂度是多少?我估量90%的人会答错。

Java言语完成:

Java 的完成和C言语的完成共同,不再撰述。

代码如下:

Python言语完成:

咱们用deapq来完成,因为deapq只支撑最小堆,因而咱们变通一下,构建堆的时分,刺进分量的负值,这样构建的最小堆等价与最大堆。终究,获取终究石头分量的时分,不要忘了再次转化过来。代码如下:


请关注微信公众号
微信二维码
不容错过
Powered By Z-BlogPHP