跟随carl代码随想录刷题 语言:python
55. 跳跃游戏
题目:给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标。 👉示例 1: 输入:nums = [2,3,1,1,4] 输出:true 解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。 👉示例 2: 输入:nums = [3,2,1,0,4] 输出:false 解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。
题目分析
转化为覆盖问题
完整代码如下
class Solution:
def canJump(self, nums: List[int]) -> bool:
cover = 0
if len(nums) == 1:
return True
i = 0
while i <= cover:
cover = max(i+nums[i], cover)
if cover >= len(nums) - 1:
return True
i += 1
return False
45. 跳跃游戏 II
题目:给你一个非负整数数组 nums ,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数 到达数组的最后一个位置。 假设你总是可以到达数组的最后一个位置。 👉示例 1: 输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2 。 从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。 👉示例 2: 输入: nums = [2,3,0,1,4] 输出: 2
题目分析
以最小的步数增加最大的覆盖范围,直到覆盖范围覆盖了终点。 待分析……
完整代码如下
class Solution:
def jump(self, nums: List[int]) -> int:
if len(nums) == 1:
return 0
ans = 0
curDistance = 0
nextDistance = 0
for i in range(len(nums)):
nextDistance = max(i + nums[i], nextDistance)
if i == curDistance:
if curDistance != len(nums) - 1:
ans += 1
curDistance = nextDistance
if nextDistance >= len(nums) - 1: break
return ans
452. 用最少数量的箭引爆气球
题目:有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭,若有一个气球的直径的开始和结束坐标为 xstart,xend, 且满足 xstart ≤ x ≤ xend,则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后,可以无限地前进。 给你一个数组 points ,返回引爆所有气球所必须射出的 最小 弓箭数 。 👉示例 1: 输入:points = [[10,16],[2,8],[1,6],[7,12]] 输出:2 解释:气球可以用2支箭来爆破: -在x = 6处射出箭,击破气球[2,8]和[1,6]。 -在x = 11处发射箭,击破气球[10,16]和[7,12]。 👉示例 2: 输入:points = [[1,2],[3,4],[5,6],[7,8]] 输出:4 解释:每个气球需要射出一支箭,总共需要4支箭。 👉示例 3: 输入:points = [[1,2],[2,3],[3,4],[4,5]] 输出:2 解释:气球可以用2支箭来爆破:
- 在x = 2处发射箭,击破气球[1,2]和[2,3]。
- 在x = 4处射出箭,击破气球[3,4]和[4,5]。
题目分析
- python知识介绍:对二维数组进行排序
二维数组.sort()
- 执行
key = lambda 函数 x: x[0] 表示对二维数组中的每个元组的第一维排序x: x[1] 表示对二维数组中的每个元组的第二维排序- eg:对
points = [[10,16], [2,8], [1,6], [7,12]] 排序
points.sort(key = lambda x: x[0])
- [[
1 ,6], [2 ,8], [7 ,12]], [10 ,16]] # 对左边界排序 points.sort(key = lambda x: x[1])
- [[1,
6 ], [2,8 ], [7,12 ], [10,16 ]] # 对右边界排序
解题思路: 气球被引爆的条件:
- 题目中说
xstart <= x <= xend 可以被引爆 - 因此引爆情况有两种:
- 区间重合,eg:
[1, 3], [2, 5] - 区间相邻,eg:
[1, 2], [2, 3] - 代码
point[i][0] <= point[i-1][1] # 后一个气球的左边界start 小于等于 前一个气球的右边界end- 更新 后一个气球的右边界end:
point[i][1] = point[i-1][1]
完整代码如下
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if len(points) == 0: return 0
points.sort(key=lambda x: x[0])
count = 1
for i in range(1, len(points)):
if points[i][0] > points[i - 1][1]:
count += 1
else:
points[i][1] = min(points[i - 1][1], points[i][1])
return count
435. 困难 无重叠区间
题目:给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。 👉示例 1: 输入: intervals = [[1,2],[2,3],[3,4],[1,3]] 输出: 1 解释: 移除 [1,3] 后,剩下的区间没有重叠。 👉示例 2: 输入: intervals = [ [1,2], [1,2], [1,2] ] 输出: 2 解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。 👉示例 3: 输入: intervals = [ [1,2], [2,3] ] 输出: 0 解释: 你不需要移除任何区间,因为它们已经是无重叠的了。
题目分析
- 目标:求需要移除的
交叉区间 的数量 - 可以转化为:求
return ——总区间数 - 非交叉区间 的数量
本题和452.用最少数量的箭引爆气球 非常像,弓箭的数量 是交叉区间数量+相邻区间数量 。而本题中在判断条件加个等号变成>= (认为只要区间2的左端点 大于等于 区间1的右端点 ,就是不重合的区间数 。然后用总区间数 减去不重合的区间数 就是要移除的区间数量 了。
完整代码如下
class Solution:
def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
if len(intervals) == 0:
return 0
intervals.sort(key=lambda x: x[0])
count = 1
for i in range(1, len(intervals)):
if intervals[i][0] >= intervals[i - 1][1]:
count += 1
else:
intervals[i][1] = min(intervals[i - 1][1], intervals[i][1])
return len(intervals) - count
763. 划分字母区间
题目:字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中 。返回一个表示每个字符串片段的长度的列表。 👉示例: 输入:S = “ababcbacadefegdehijhklij” 输出:[9,7,8] 解释: 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。 每个字母最多出现在一个片段中。 像 “ababcbacadefegde”, “hijhklij” 的划分是错误的,因为划分的片段数较少。
题目分析
本题是分割字符串,不过不用回溯。
如果找到之前遍历过的所有字母的最远边界,说明这个边界就是分割点了。
- 可以分为如下两步:
- 统计每一个字符最后出现的位置
- 从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点
将区间按左边界从小到大排序,找到边界将区间划分成组,互不重叠。找到的边界就是答案。
完整代码如下
class Solution:
def partitionLabels(self, s: str) -> List[int]:
hash = [0]*26
for i in range(len(s)):
hash[ord(s[i]) - ord('a')] = i
result = []
left = 0
right = 0
for i in range(len(s)):
right = max(right, hash[ord(s[i]) - ord('a')])
if i == right:
result.append(right - left + 1)
left = i + 1
return result
56. 合并区间
题目:以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。 👉示例 1: 输入:intervals = [[1,3],[2,6],[8,10],[15,18]] 输出:[[1,6],[8,10],[15,18]] 解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]. 👉示例 2: 输入:intervals = [[1,4],[4,5]] 输出:[[1,5]] 解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。
题目分析
完整代码如下
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if len(intervals) == 0:
return intervals
intervals.sort(key=lambda x:x[0])
result = []
result.append(intervals[0])
for i in range(1, len(intervals)):
last = result[-1]
if last[1] >= intervals[i][0]:
result[-1] = [last[0], max(last[1], intervals[i][1])]
else:
result.append(intervals[i])
return result
|