Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-01-05 13:50:47
※ 引述《fxfxxxfxx (爱丽丝)》之铭言:
: 452. Minimum Number of Arrows to Burst Balloons
给你一个二维阵列points,points[i]={x1, x2}表示第i个气球的水平座标,我们将
气球依照水平座标重叠,假设我们开一枪可以贯穿一整排的气球,求出我们最少要开
几枪才可以把气球都打烂。
Example:
Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: 气球按照下列方式排成一列
[10 11 12 13 14 15 16]
[2 3 4 5 6 7 8]
[1 2 3 4 5 6]
[7 8 9 10 11 12]
我们第一次射击射6位置可以打破points[1]和points[2]
第二次射击可以打破points[0]和points[3],最少共需要两次射击,所以返回2。
Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: 气球按照下列方式排成一列
[1 2]
[3 4]
[5 6]
[7 8]
每个气球不重叠,共需要四次射击
思路:
1.一开始是想把points排序之后的每个区间合并然后算有多少个不交替的区间,
但是像是[1 2] [2 3] [3 4] 虽然可以合并但是其实需要射两次,所以换个方
向思考。
2.我们把气球的最右边想像成“最晚必须要射击的地方”,然后按照最右边座标
排序,以 [[10,16],[2,8],[1,6],[7,12]] 来说,排序完之后长这样:
[1 2 3 4 5 6]
[2 3 4 5 6 7 8]
[7 8 9 10 11 12]
[10 11 12 13 14 15 16]
3.我们从左到右一路射过去,每次都射击当前气球的最右边,排序完之后可以明显观察到
你射最右边的同时会射到其他气球的左边部分,遇到小于的就表示重叠了该个气球可跳
过,而当左边的座标小于下一个气球的右边座标的时候,表示后面没有气球了,下一次
的射击位置将改为下个气球的最右边,重复动作直到气球射完为止。
Java Code:

Links booklink

Contact Us: admin [ a t ] ucptt.com