Leetcode【56、670】
Leetcode【56、670】
echobingo
发布于 2019-10-12 17:33:27
发布于 2019-10-12 17:33:27
问题描述：【Sort】56. Merge Intervals
解题思路：
这道题是给一个区间集合，合并所有重叠区间。
首先可以想到按照区间的起始点进行升序排序。假设合并后的区间保存在数组 ans 中。从左到右遍历各个区间 interval，会有以下 3 种情况：
- ans = [[...], [...], [5, 9]]，interval = [6, 10]，因为 6 <= 9 并且 10 >= 9，因此有重叠部分，可以合并，只需要修改 ans 最后一个区间的终止点为 10 即可。
- ans = [[...], [...], [5, 9]]，interval = [10, 12]，因为 10 > 9，因此没有重叠部分，不能和前一个区间合并，需要在 ans 中添加 interval 即可。
- ans = [[...], [...], [5, 9]]，interval = [6, 8]，属于完全覆盖的情况，不需要进行任何操作。
这样，只需要遍历一次，就可以得到答案。时间复杂度主要来自于排序的开销 O(nlogn)，空间复杂度为 O(n)。
Python3 实现：
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
lens = len(intervals)
if lens == 0: return []
intervals.sort() # 按照第一维升序，第一维相同按照第二维升序
ans = [intervals[0]]
for i in range(1, lens):
interval = intervals[i]
if interval[0] <= ans[-1][1] and interval[1] >= ans[-1][1]:
ans[-1][1] = interval[1]
elif interval[1] > ans[-1][1]:
ans.append(interval)
return ans问题描述：【Greedy、Brute Force】670. Maximum Swap
解题思路：
这道题是给一个非负整数，对其中的两个数位最多允许交换一次，返回最大数字。
方法 1（贪心思想）：
这道题观察一下规律就可以得到方法：
- 对于 2736、7236 这种，对于每个数字 i（内层循环），需要找到后面的 i+1, i+2, .. n 中比 i 大的最大数字（外层循环），交换即可；如果没有找到，则需要移动到下一位 i+1 继续寻找。因此这里是两层循环。
- 对于 1939 这种，对于数字 1，我们不仅要找到最大数字 9， 还要交换最后一个 9，因此在 i+1, i+2, .. n 中找比 i 大的最大数字时，要从后往前遍历，找最后一个最大的数字，和它进行交换（贪心思想）。
- 对于 9876，因为对于每个数字 i，都没有办法在 i+1, i+2, .. n 中找到比 i 大的最大数字，因此返回原数字就行。
时间复杂度为 O(n^2)，因为要把数字拆成列表一个一个判断，因此空间复杂度为 O(n)。
class Solution:
def maximumSwap(self, num: int) -> int:
nums = [int(i) for i in list(str(num))]
for i in range(len(nums)):
mval = mind = -1
for j in range(len(nums)-1, i, -1):
if nums[j] > mval:
mval = nums[j]
mind = j
if nums[i] < mval:
nums[i], nums[mind] = nums[mind], nums[i]
break
res = 0
for i in range(len(nums)):
res = res * 10 + nums[i]
return res方法 2（暴力搜索）：
由于这道题最多只进行一次交换，因此可以双层循环，暴力每个交换位置 (i, j) 的所有情况，更新最大数字的结果进行。时间复杂度为 O(n^2)，空间复杂度为 O(n)。尽管是暴力，但是这种方法和方法 1 的执行时间差不多。
class Solution:
def maximumSwap(self, num: int) -> int:
nums = list(str(num))
res = nums[:] # 不交换
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
nums[i], nums[j] = nums[j], nums[i] # 进行交换
if nums > res: res = nums[:] # 更新最大数字
nums[i], nums[j] = nums[j], nums[i] # 恢复，交换回来
return int("".join(res))本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019.10.10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录