# # Leetcode 第272场周赛题解

## # Problem A - 找出数组中的第一个回文字符串 (opens new window)

### # 方法一：模拟

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

class Solution:
def firstPalindrome(self, words: List[str]) -> str:
return ([word for word in words if word == word[::-1]] + [""])[0]

1
2
3

## # Problem B - 向字符串添加空格 (opens new window)

### # 方法一：模拟

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

class Solution:
def addSpaces(self, s: str, spaces: List[int]) -> str:
t = ' '.join(s[i:j] for i, j in zip(spaces[:-1], spaces[1:]))
return s[:spaces[0]] + (' ' if t != '' else '') + t + ' ' + s[spaces[-1]:]

1
2
3
4

## # Problem C - 股票平滑下跌阶段的数目 (opens new window)

### # 方法一：动态规划

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

class Solution {
public:
long long getDescentPeriods(vector<int>& prices) {
long long ans = 0;
int acc = 1, last = 0;
for (int price : prices) {
if (price == last - 1)
ans += ++acc;
else
ans += acc = 1;
last = price;
}

return ans;
}
};

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

## # Problem D - 使数组 K 递增的最少操作次数 (opens new window)

### # 方法一：最长不下降子序列

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

class Solution {
int increasing(vector<int> &a) {
int n = a.size();
vector<int> LIS;
for (int ai : a) {
auto it = upper_bound(LIS.begin(), LIS.end(), ai);
if (it == LIS.end())
LIS.push_back(ai);
else
*it = ai;
}
return n - LIS.size();
}

public:
int kIncreasing(vector<int>& arr, int k) {
int ans = 0;
for (int i = 0; i < k; ++i) {
vector<int> v;
for (int j = i; j < arr.size(); j += k)
v.push_back(arr[j]);
ans += increasing(v);
}
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