题目连结:1046. Last Stone Weight
题目主题:Array, Heap(Priority Queue)
今天的重点一样在Heap (Priority Queue)这个主题上面,这次会分享Heap (Priority Queue)实际上长的样子及pop资料的过程。
上一篇分享了Heap的使用概念,另外也有提到Heap其实是一个Tree的结构,这次就拿一个范例,来看看将阵列放进箱子後,实际上会长成什麽样子。范例一样使用Min Heap来说明,以Python为例,当我们呼叫了heapify()实际上,到底对阵列做了什麽改变?而heappop()又是怎麽运作的呢?
范例资料:nums = [13, 14, 11, 1, 4, 6, 16]
当我们将这个nums的资料转成Min Heap後,也就是使用heapify(nums)後,实际上这个资料转换後的结构长相如下图。
这种树的原则是越上层的数字越小,越下层的数字越大,数字不见得会依照顺序排,但上层小、下层大的原则是一定的。假设是Max Heap,原则是越上层的数字越大,越下层的数字越小。
还记得前一篇讲到当我们对这个Min Heap取一笔资料时,一定会优先取得最小的数字,这个资料的取得过程,实际上运作如下图:
再让我们看一个例子,如果在取一笔资料,运作过程会如下图:
可以看到这个数字 11 被换到最上面以後,这次是往下层右子节点走,是因为 6 是它下层子节点中最小的,换完以後就停止了,因为没有下层没有子节点了。
可以在上面两个pop例子中看到,这棵树在取完资料的过程,会一直保持树的原则,越上层的数字越小,越下层的数字越大。
这是本系列文第一次看到树的结构,接下来会越来越多树的例子,在这边我们只要先知道Heap(Priority Queue)实际的长相及pop运作过程即可。
建议可以看看LeetCode原本的题目说明,这边是用我的方式说明题目,参考就好。
本题会输入一个stones阵列,这个阵列存放的每个值代表一颗石头的重量。
这是一个游戏,每回合会选两颗最重的石头互敲敲碎,假设最重的两颗石头分别为 x 及 y,敲碎的规则如下:
依照上面的规则,会一直玩到剩下一颗石头或是没有石头才会结束游戏。最终如果剩一颗石头,回传最後这颗石头的重量,若最终没有任何石头,直接回传0。
约束:
范例1
输入: stones = [2,7,4,1,8,1]
输出: 1
解释:
第一回合 最重两颗石头为 7 跟 8 ,敲完以後会拿到 1 这颗石头,放回stones中,剩[2,4,1,1,1]。
第二回合 最重两颗石头为 2 跟 4 ,敲完以後会拿到 2 这颗石头,放回stones中,剩[2,1,1,1]。
第三回合 最重两颗石头为 2 跟 1 ,敲完以後会拿到 1 这颗石头,放回stones中,剩[1,1,1]。
第四回合 最重两颗石头为 1 跟 1 ,敲完以後两颗都被销毁,stones中剩[1]。
最後回传这颗石头重量 1。
范例2
输入: stones = [1]
输出: 1
解释: 因为只有一颗石头,直接回传这颗石头的重量。
建议到这边先停下来,尝试自己解解看,若没有想法可再继续走下去。
范例: stones = [2,7,4,1,8,1]
上图范例可以看到,每个步骤会取得两颗石头,step2 开始会看到的绿色数字,就是前一步骤中y - x 得到的新石头重量。直接看step4 取到的 y 跟 x 都是1,因此直接抵销,最终step 5 剩一个石头,所以回传这颗石头结束。
若因为没想法而走到这边,建议看完想像以後再给自己一次机会试一次。
from heapq import _heapify_max, _heappop_max, heappush
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
# 跑一个回圈,到剩一颗石头或没石头时结束
while len(stones) > 1:
# 整理成Max Heap的结构
_heapify_max(stones)
# 最重的石头放 y
y = _heappop_max(stones)
# 第二重的石头放 x
x = _heappop_max(stones)
# 取得新重量
newWeight = y-x
# 若不是 0,要再把这颗有新重量的石头放回stones中
if newWeight > 0:
heappush(stones, newWeight)
# 若剩一颗,回传这颗石头重量
# 若没有剩任何石头回传 0
return stones[0] if len(stones) == 1 else 0
若内容有什麽问题或建议欢迎一起交流:)
感谢您今天愿意花时间看完这篇文章~~~~
Next:144. Binary Tree Preorder Traversal
>>: Day08 - [丰收款] 十六进位格式的後续探讨,字串传输容量倍增了!
人的科技文明发展始终来自於人性 在疫情的时代当中,当所有的一切都变得不再单纯时,或是当所有的一切都变...
前一篇内容设定了C#专案里的Generate NuGet package on build,让专案编...
到 Line Notify 点进连动好的服务後,可以看到他有产生一个 Client ID 和 Cli...
上一篇我们成功在 Next.js 安装 TailwindCSS,今天我们要实际来切版首页,显示文章列...
第四天的小试身手解答:将Unity介面改为2By3,Project从Two Column Layou...