# # Leetcode 第213场周赛题解

## # Problem A - 能否连接形成数组 (opens new window)

• 时间复杂度$O(N+M)$=$O(N)$$N$$arr$的长度。
• 空间复杂度$O(M)$$M$$pieces$的长度。

class Solution {
public:
bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
int n = arr.size(), m = pieces.size();
unordered_map<int, int> mp;
for (int i = 0; i < m; ++i)
mp[pieces[i][0]] = i;
for (int i = 0; i < n; ++i) {
if (!mp.count(arr[i]))
return false;
int j = mp[arr[i]];
for (int k = 1; k < pieces[j].size(); ++k) {
if (arr[i + k] != pieces[j][k])
return false;
}
i += pieces[j].size() - 1;
}
return true;
}
};

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

## # Problem B - 统计字典序元音字符串的数目 (opens new window)

### # 方法一 动态规划

$dp[i][j]$表示最后一个字母不大于$j$个元音字母的长度为$i$的字符串数目。显然，我们有转移：

$dp[i][j]=dp[i-1][j] + dp[i][j-1]$

• 时间复杂度$O(CN)$，本题中$C=5$
• 空间复杂度$O(C)$

$dp2[i][j]=\sum_{k=0}^jdp2[i-1][j]$

class Solution {
public:
int countVowelStrings(int n) {
vector<int> dp(5, 1);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= 4; ++j)
dp[j] += dp[j - 1];
return dp[4];
}
};

1
2
3
4
5
6
7
8
9
10

### # 方法二 组合计数

$a+e+i+o+u=N$

$a'=a+1,e'=e+1,\dots,u'=u+1$

$a'+e'+i'+o'+u'=N+5$

class Solution:
def countVowelStrings(self, n: int) -> int:
return math.comb(n + 4, 4)

1
2
3

## # Problem C - 可以到达的最远建筑 (opens new window)

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

class Solution {
public:
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
int n = heights.size();
int need = 0;
priority_queue<int, vector<int>, greater<>> pq;
for (int i = 0; i + 1 < n; ++i) {
int delta = heights[i + 1] - heights[i];
if (delta <= 0)
continue;
pq.push(delta);
int small = pq.top();
pq.pop();
need += small;
if (need > bricks)
return i;
}
}
return n - 1;
}
};

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

## # Problem D - 第 K 条最小指令 (opens new window)

• 时间复杂度$O(N+M)$
• 空间复杂度$O(N+M)$

class Solution:
def kthSmallestPath(self, destination: List[int], k: int) -> str:
ans = []
v, h = destination

fac = [1]
for i in range(v + h):
fac.append(fac[-1] * (i + 1))
def comb(n, k):
return fac[n] // fac[n - k] // fac[k];

L = 1
for i in range(v + h):
if v == 0:
ans.append('H')
continue
if h == 0:
ans.append('V')
continue
left = comb(v + h - 1, h - 1)
if L + left > k:
ans.append('H')
h -= 1
else:
ans.append('V')
L += left
v -= 1
return ''.join(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