# Leetcode 第253场周赛题解

# Problem A - 检查字符串是否为数组前缀 (opens new window)

# 方法一：模拟

• 时间复杂度$\mathcal{O}(|S|)$
• 空间复杂度$\mathcal{O}(1)$

class Solution {
public:
bool isPrefixString(string s, vector<string>& words) {
int n = s.size();
int ptr = 0;
for (string &word : words) {
int m = word.size();
int i = 0;
while (i < m && ptr < n && word[i] == s[ptr])
i++, ptr++;
if (i == m && ptr == n)
return true;
if (i != m)
return false;
}
return false;
}
};

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

# Problem B - 移除石子使总数最小 (opens new window)

# 方法一：贪心+优先队列

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

class Solution {
public:
int minStoneSum(vector<int>& piles, int k) {
priority_queue<int> pq;
for (int pile : piles)
pq.emplace(pile);
while (k > 0) {
k--;
int t = pq.top();
pq.pop();
pq.emplace(t - t / 2);
}
int ans = 0;
while (!pq.empty())
ans += pq.top(), pq.pop();
return ans;
}
};

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

# Problem C - 使字符串平衡的最小交换次数 (opens new window)

# 方法一：贪心

• 时间复杂度$\mathcal{O}(|S|)$
• 空间复杂度$\mathcal{O}(1)$

class Solution {
public:
int minSwaps(string s) {
int n = s.size();
int bal = 0, ans = 0;
int ptr = n - 1;
for (char c : s) {
if (c == '[')
bal++;
else {
if (bal > 0) {
bal--;
} else {
ans++;
while (s[ptr] != '[')
ptr--;
s[ptr] = ']';
bal++;
}
}
}
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

class Solution {
public:
int minSwaps(string s) {
int bal = 0, ans = 0;
for (char c : s) {
if (c == '[')
bal++;
else if (bal > 0)
bal--;
else
ans++, bal++;
}
return ans;
}
};

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

# Problem D - 找出到每个位置为止最长的有效障碍赛跑路线 (opens new window)

# 方法一：动态规划（最长不下降子序列）

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

class Solution {
public:
vector<int> longestObstacleCourseAtEachPosition(vector<int>& obstacles) {
int n = obstacles.size();
vector<int> ans(n);
vector<int> LIS;
int i = 0;
for (int obstacle : obstacles) {
auto it = upper_bound(LIS.begin(), LIS.end(), obstacle);
if (it == LIS.end()) {
LIS.emplace_back(obstacle);
ans[i] = LIS.size();
} else {
ans[i] = it - LIS.begin() + 1;
*it = obstacle;
}
i++;
}
return ans;
}
};

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