LeetCode笔记：Weekly Contest 239 比赛记录-一一网

【摘要】 LeetCode笔记：Weekly Contest 239 0. 赛后总结1. 题目一 1. 解题思路2. 代码实现 2. 题目二 1. 解题思路2. 代码实现 3. 题目三 1. 解题思路2. 代码实现 4. 题目四 1. 解题思路2. 代码实现 0. 赛后总结
今天总算是硬着头皮打了比赛了，总算没有又浪费一天，结果发现还不如不打呢，成绩烂的一批，简直惨不忍睹，…

LeetCode笔记：Weekly Contest 239

0. 赛后总结

今天总算是硬着头皮打了比赛了，总算没有又浪费一天，结果发现还不如不打呢，成绩烂的一批，简直惨不忍睹，只做出两题，唉……

希望后面状态能有所好转吧……

1. 题目一

给出题目一的试题链接如下：

5746. 到目标元素的最小距离

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)

  
 
  1
  2
  3
  4
  5

提交代码评测得到：耗时56ms，占用内存14.6MB。

2. 题目二

给出题目二的试题链接如下：

5747. 将字符串拆分为递减的连续值

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))

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16

提交代码评测得到：耗时32ms，占用内存14.2MB。

3. 题目三

给出题目三的试题链接如下：

5749. 邻位交换的最小次数

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

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32

提交代码评测得到：耗时1404ms，占用内存14.3MB。

4. 题目四

给出题目四的试题链接如下：

5748. 包含每个查询的最小区间

1. 解题思路

这一题比赛的时候毫无思路，但是赛后发现它和这次双周赛的最后一题的思路是异曲同工的，问题都在于不同阶段需要的排序特征是不同的，且queries是乱序的。

因此，我们首先将query加入其原始的index然后进行排序，然后就可以单向地对我们的有效区间列表进行维护。

我们同样先将有效区间进行排序。假设第i-1次query已经完成，我们来考察第i次query (q, idx)，此时，我们需要做的操作包括：

将所有左边界小于等于q的边界全部加入到有效区间当中；
在有效区间中将所有右边界小于q的区间全部从有效区间列表中移除；
将有效区间中的最小区间长度dis更新到原始的query所在的index（即idx）当中。

其中，对于1我们只需要单向滑动即可做到，而对于2，我们需要维护一个按照右边界位置有序排列的一个有效区间数组，而对于3，我们则需要同步地维护一个与2中的有效区间一致，但是按照区间长度进行排序的数组。

此时，我们就可以在 $\cdot 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

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19