室内设计公司的运营模式,株洲网站排名优化,找能做网站的,软件网站关键词优化白银挑战-贪心高频问题
1. 区间问题
所有的区间问题#xff0c;参考下面这张图 1.1 判断区间是否重叠
LeetCode252 https://leetcode.cn/problems/meeting-rooms/
思路分析
因为一个人在同一时刻只能参加一个会议#xff0c;因此题目的本质是判断是否存在重叠区间
将区…白银挑战-贪心高频问题
1. 区间问题
所有的区间问题参考下面这张图 1.1 判断区间是否重叠
LeetCode252 https://leetcode.cn/problems/meeting-rooms/
思路分析
因为一个人在同一时刻只能参加一个会议因此题目的本质是判断是否存在重叠区间
将区间按照会议开始时间进行排序然后遍历一遍判断后面的会议开始的时候是否前面的还没有结束如果出现重叠返回false
代码实现
class Solution:def canAttendMeetings(self, intervals: List[List[int]]) - bool:intervals.sort(keylambda x: x[0])for i in range(1, len(intervals)):if intervals[i][0] intervals[i - 1][1]:return Falsereturn Trueclass Solution:def canAttendMeetings(self, intervals: List[List[int]]) - bool:intervals.sort(keylambda x: x[0])return all(intervals[i][0] intervals[i - 1][1] for i in range(1, len(intervals)))1.2 合并区间
LeetCode 56 https://leetcode.cn/problems/merge-intervals/
思路分析
首先对区间按照起始端点进行升序排序然后逐个判断当前区间是否与前一个区间重叠 如果不重叠直接加入结果集 如果重叠将当前区间与前一个区间进行合并
区间合并 区间1区间2 合并
[ 区间1起始时间max(区间1结束时间区间2结束时间) ]
代码实现
class Solution:def merge(self, intervals: List[List[int]]) - List[List[int]]:intervals.sort(keylambda x: x[0])merged []for interval in intervals:# 合并列表为空if not merged:merged.append(interval)# 当前区间与上一区间不重叠elif interval[0] merged[-1][1]:merged.append(interval)# 当前区间与上一区间重叠需要合并else:# 区间合并操作merged[-1][1] max(merged[-1][1], interval[1])return merged1.3 插入区间
LeetCode57 https://leetcode.cn/problems/insert-interval/
思路分析
区间已经按照起始端点升序排序我们直接遍历区间列表寻找新区间的插入位置即可
将新区间左边且相离的区间加入结果集接着判断当前区间是否与新区间重叠 重叠进行合并直到遍历到当前区间在新区间右边且相离加入合并后区间 不重叠直接加入新区间将新区间右边且相离的区间加入结果集
代码实现
class Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) - List[List[int]]:inserted []index 0n len(intervals)# 将新区间左边且相离的区间加入结果集while index n and intervals[index][1] newInterval[0]:inserted.append(intervals[index])index 1# 接着判断当前区间是否与新区间重叠# 重叠进行合并直到遍历到当前区间在新区间右边且相离加入合并后区间# 不重叠直接加入新区间while index n and intervals[index][0] newInterval[1]:newInterval[0] min(newInterval[0], intervals[index][0])newInterval[1] max(newInterval[1], intervals[index][1])index 1inserted.append(newInterval)# 将新区间右边且相离的区间加入结果集while index n:inserted.append(intervals[index])index 1return insertedclass Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) - List[List[int]]:inserted []index 0n len(intervals)while index n:if intervals[index][1] newInterval[0]:inserted.append(intervals[index])index 1elif intervals[index][0] newInterval[1]:newInterval[0] min(newInterval[0], intervals[index][0])newInterval[1] max(newInterval[1], intervals[index][1])index 1else:breakinserted.append(newInterval)inserted.extend(intervals[index:])return inserted2. 字符串分割
LeetCode763 https://leetcode.cn/problems/partition-labels/
思路分析
需要把同一个字母圈在同一个区间里
该遍历过程相当于要找每一个字母的边界如果找到之前遍历过的所有字母的最远边界说明这个边界就是分割点了。此时前面出现过所有字母最远也就到这个边界了。
具体做法
统计每一个字符最后出现的位置从头遍历字符并更新字符最远出现下标如果找到字符最远出现位置下标和当前下标相等则找到了分割点 代码实现
class Solution:def partitionLabels(self, s: str) - List[int]:ans []# 第一轮遍历统计每一个字符最后出现的位置char_dict {}for i in range(len(s)):char_dict[s[i]] i# 第二轮遍历begin_index -1char_far_index 0for i in range(len(s)):char_far_index max(char_far_index, char_dict[s[i]])if char_far_index i:ans.append(i - begin_index)begin_index ireturn ansclass Solution:def partitionLabels(self, s: str) - List[int]:last [0] * 26for i, char in enumerate(s):last[ord(char) - ord(a)] ipartition list()start, end 0, 0for i, char in enumerate(s):end max(end, last[ord(char) - ord(a)])if i end:partition.append(end - start 1)start end 1return partition3. 加油站问题
LeetCode134 https://leetcode.cn/problems/gas-station/
思路分析
很容易想到暴力解法从第一站开始尝试。缺点就是需要大量的重复计算 优化 总油量 - 总消耗 ≥ 0可以跑完一圈具体到每一段就是各个加油站的剩油量 rest[i] 相加一定是大于等于0的
每个加油站剩油量 rest[i] gas[i] - cost[i]i从0开始累加 rest[i] 得到当前油量 curSum一旦curSum小于0说明[0, i]区间都不能作为起始位置起始位置必须从i1开始重新算只有这样才能保证有可能完成
复杂度降低从O(n^2)降低到O(n) 代码实现 class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) - int:total_sum 0cur_sum 0start 0for i in range(len(gas)):cur_sum gas[i] - cost[i]total_sum gas[i] - cost[i]# 当前累加rest[i]和 cur_sum小于0if cur_sum 0:# 更新起始位置为 i1start i1# cur_sum从 0 开始cur_sum 0return -1 if total_sum 0 else start
