LeetCode笔记：Weekly Contest 239 比赛记录
LeetCode笔记：Weekly Contest 239 比赛记录
- LeetCode笔记：Weekly Contest 239
- 0. 赛后总结
- 1. 题目一
- 1. 解题思路
- 2. 代码实现
- 2. 题目二
- 1. 解题思路
- 2. 代码实现
- 3. 题目三
- 1. 解题思路
- 2. 代码实现
- 4. 题目四
- 1. 解题思路
- 2. 代码实现
0. 赛后总结
今天总算是硬着头皮打了比赛了，总算没有又浪费一天，结果发现还不如不打呢，成绩烂的一批，简直惨不忍睹，只做出两题，唉……
希望后面状态能有所好转吧……
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
第一题依然是中规中矩，找到所有等于target的数字的index，然后按照与start的距离的绝对值进行排序，最后取出第一个元素与start之间的距离绝对值即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def getMinDistance(self, nums: List[int], target: int, start: int) -> int:
cache = [idx for idx, x in enumerate(nums) if x == target]
cache = sorted(cache, key=lambda x: abs(x-start))
return abs(cache[0] - start)提交代码评测得到：耗时56ms，占用内存14.6MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题的思路其实也挺直接的，由于要求所有的数字是连续递减的，因此，我们只要把第一个数字确定下来，后面的数字就都能确定了，那么，我们只需要遍历一下第一个数字的所有可选值，然后看一下后面能否成功构建就行了。
2. 代码实现
给出python代码实现如下：
class Solution:
def splitString(self, s: str) -> bool:
s = s.lstrip('0')
n = len(s)
def dp(s, val):
if s == "":
return True
s = s.lstrip("0")
if val == 0 and s == "":
return True
if not s.startswith(str(val)):
return False
return dp(s[len(str(val)):], val-1)
return any(dp(s, int(s[:i])) for i in range(1, n))提交代码评测得到：耗时32ms，占用内存14.2MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题的思路倒是挺直接的，首先就是找到比原数大的第k个数，然后要做的就是找到从原始数字变换成目标数字所需要的变换次数。
其中，前者可以通过题目1830. 使字符串有序的最少操作次数给出的方法进行实现。
而关于后者，我们可以直接采用暴力方式进行实现……
是的，直接暴力求解，唉，比赛的时候死活没敢去尝试，总觉得会超时，结果呵呵了……
2. 代码实现
给出python代码实现如下：
class Solution:
def getMinSwaps(self, num: str, k: int) -> int:
n = len(num)
src = [c for c in num]
tgt = [c for c in num]
def get_next_larger(s):
i = n-1
for i in range(n-1, 0, -1):
if s[i] > s[i-1]:
break
j = i
while j < n and s[j] > s[i-1]:
j += 1
j -= 1
s[i-1], s[j] = s[j], s[i-1]
s[i:] = s[i:][::-1]
return s
for i in range(k):
tgt = get_next_larger(tgt)
res = 0
for i in range(n):
if src[i] == tgt[i]:
continue
for j in range(i+1, n):
if tgt[j] == src[i]:
break
res += j-i
tgt.insert(i, tgt.pop(j))
return res提交代码评测得到：耗时1404ms，占用内存14.3MB。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题比赛的时候毫无思路，但是赛后发现它和这次双周赛的最后一题的思路是异曲同工的，问题都在于不同阶段需要的排序特征是不同的，且queries是乱序的。
因此，我们首先将query加入其原始的index然后进行排序，然后就可以单向地对我们的有效区间列表进行维护。
我们同样先将有效区间进行排序。假设第i-1次query已经完成，我们来考察第i次query (q, idx)，此时，我们需要做的操作包括：
- 将所有左边界小于等于
q的边界全部加入到有效区间当中； - 在有效区间中将所有右边界小于
q的区间全部从有效区间列表中移除； - 将有效区间中的最小区间长度
dis更新到原始的query所在的index（即idx）当中。
其中，对于1我们只需要单向滑动即可做到，而对于2，我们需要维护一个按照右边界位置有序排列的一个有效区间数组，而对于3，我们则需要同步地维护一个与2中的有效区间一致，但是按照区间长度进行排序的数组。
此时，我们就可以在 O(N⋅logN)的时间复杂度范围内完成上述题目了。
2. 代码实现
给出python代码实现如下：
class Solution:
def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
res = [-1 for _ in queries]
queries = sorted([(q, idx) for idx, q in enumerate(queries)])
intervals = sorted(intervals)
used, dis = [], []
flag, n = 0, len(intervals)
for q, idx in queries:
while used != [] and used[0][0] < q:
r, l = heapq.heappop(used)
dis.pop(bisect.bisect_left(dis, r-l+1))
while flag < n and intervals[flag][0] <= q:
if intervals[flag][1] >= q:
heapq.heappush(used, (intervals[flag][1], intervals[flag][0]))
bisect.insort(dis, intervals[flag][1]-intervals[flag][0]+1)
flag += 1
if len(used) != 0:
res[idx] = dis[0]
return res提交代码评测得到：耗时3328ms，占用内存53.5MB。
腾讯云开发者
