# # Leetcode 第239场周赛题解

## # Problem A - 到目标元素的最小距离 (opens new window)

• 时间复杂度$\mathcal{O}(N)$
• 参考代码的空间复杂度为$\mathcal{O}(N)$，实际只需要保存当前最优结果，所以最优的空间复杂度是$\mathcal{O}(1)$

class Solution:
def getMinDistance(self, nums: List[int], target: int, start: int) -> int:
return min([abs(i - start) for i in range(len(nums)) if nums[i] == target])

1
2
3

## # Problem B - 将字符串拆分为递减的连续值 (opens new window)

• 时间复杂度$\mathcal{O}(|S|\cdot2^{|S|})$，但实际上会远远小于这一上界。
• 空间复杂度$\mathcal{O}(|S|)$

class Solution:
def dfs(self, s: str, start: int, last: int):
if self.ans:
return

n = len(s)
if start == n:
self.ans = True
return

now = 0
hi = n if start != 0 else n - 1
for i in range(start, hi):
now = now * 10 + ord(s[i]) - ord('0')
if start == 0 or now == last - 1:
self.dfs(s, i + 1, now)
if start != 0 and now >= last:
return

def splitString(self, s: str) -> bool:
if len(s) == 1:
return False

self.ans = False
self.dfs(s, 0, 0)
return self.ans

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

## # Problem C - 邻位交换的最小次数 (opens new window)

### # 方法一：模拟

1. 利用next_permutation求出目标排列。
2. 贪心进行交换。
• 时间复杂度$\mathcal{O}(|S|^2+|S|K)$
• 空间复杂度$\mathcal{O}(|S|)$

class Solution {
public:
int getMinSwaps(string num, int k) {
string target(num);
for (int i = 0; i < k; ++i)
next_permutation(target.begin(), target.end());

int ans = 0, n = num.size();
for (int i = 0; i < n; ++i) {
if (num[i] != target[i]) {
int j = i + 1;
while (num[j] != target[i])
j++;
for (; j > i; --j)
swap(num[j], num[j - 1]), ans++;
}
}

return ans;
}
};

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

## # Problem D - 包含每个查询的最小区间 (opens new window)

• 时间复杂度$\mathcal{O}(N\log N+Q\log Q+Q\log N)$
• 空间复杂度$\mathcal{O}(N)$

class Solution {
public:
vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
int n = intervals.size(), q = queries.size();
vector<int> ans(q);

vector<int> order(q);
for (int i = 0; i < q; ++i)
order[i] = i;
sort(order.begin(), order.end(), [&](int i, int j){
return queries[i] < queries[j];
});

sort(intervals.begin(), intervals.end());
set<pair<int, int>> s;
int ptr = -1;

for (int i : order) {
int qi = queries[i];
while (ptr + 1 < n && intervals[ptr + 1][0] <= qi) {
ptr++;
s.emplace(intervals[ptr][1] - intervals[ptr][0] + 1, intervals[ptr][1]);
}

while (!s.empty() && s.begin()->second < qi)
s.erase(s.begin());

if (s.empty())
ans[i] = -1;
else
ans[i] = s.begin()->first;
}

return ans;
}
};

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
33
34
35
36