LeetCode笔记：Weekly Contest 213 比赛记录
LeetCode笔记：Weekly Contest 213 比赛记录
0. 赛后总结
这一次的比赛从排名上来说还算是OK，国内324，世界977，勉强算是挤进了前1000，不过过程上来说就是很不爽。
第三第四题一开始都想岔了，结果两个一开始都是遇到了超时问题，万幸第四题后来修改思路倒是改回来了，但是第三题想到正确思路的时候已经快没啥时间了，最后千赶万赶也没能在结束时间之前给出正确的代码实现。
最坑的是，最后结束之后检查了一下，发现思路是完全正确的，错误的原因在于粗心码漏了一行代码，一行代码，行代码，代码，码。。。
唉，心累。
1. 题目一
给出题目一试题链接如下：
1. 解题思路
这一题其实可以很难的，但是题目给了许多限制条件，硬生生把难度限制在了easy级别，那么我们也只需要按照easy级别的方法来做就行了：
- 给出一个index，找到所给的pieces中以
arr[index]开头的那一个，比较两者是否相同，如果不相同直接返回false，反之则更新index为加上这个piece之后的index。
2. 代码实现
给出最终的python代码实现如下：
class Solution:
def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
cache = {}
for x in pieces:
if x[0] in cache:
return False
cache[x[0]] = x
idx = 0
while idx < len(arr):
if arr[idx] not in cache:
return False
l = len(cache[arr[idx]])
if arr[idx:idx+l] != cache[arr[idx]]:
return False
idx += l
return True提交代码评测得到：耗时44ms，占用内存14MB。
不过当前提交的代码实现总量还不够，暂时不知道还有没有更好的代码实现，有兴趣的读者可以后续关注一下，这里就不再多做关注了。
2. 题目二
给出题目二试题链接如下：
1. 解题思路
这一题就是一道中规中矩的动态规划题目：
- 考察第i个字符，如果上一个使用的元音字符为k，那么可选择的元音字符就只能在其后方（含其本身），我们依次取用一遍就可以了。
2. 代码实现
给出最终的python代码实现如下：
class Solution:
def countVowelStrings(self, n: int) -> int:
@lru_cache(None)
def dp(idx, c):
if idx >= n:
return 1
elif c == 4:
return 1
ans = 0
for i in range(c, 5):
ans += dp(idx+1, i)
return ans
return dp(0, 0)提交代码评测得到：耗时36ms，占用内存14.4MB。
当前最优的代码实现耗时28ms，不过没太看懂他的思路，有兴趣的读者可以自行研究一下，这里就不再多做展开了。
3. 题目三
给出题目三试题链接如下：
1. 解题思路
这一题拿到题目的第一反应就是一道简单的动态规划题目，简直不用动脑子就能写出递推公式，然后就超时了。。。
后来仔细分析了一下题目，显然梯子这种大招肯定是用来救火的，那么，他的使用方式就应该是：
- 当垒砖块已经无法越过当前的壁垒时，就从之前填充的壁垒当中选取gap最大的一个壁垒，将砖块拆了使用梯子来进行替换，从而补充砖块来进行填充，直到梯子已经用尽且砖块无法填充下一个壁垒时，返回当前所在的位置即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
n = len(heights)
idx = 0
gap = []
tot_gap = 0
while idx < n-1:
if heights[idx+1] <= heights[idx]:
idx += 1
else:
tmp = heights[idx] - heights[idx+1]
tot_gap += tmp
heapq.heappush(gap, tmp)
while tot_gap + bricks < 0 and ladders > 0:
ladders -= 1
g = heapq.heappop(gap)
tot_gap -= g
if tot_gap + bricks < 0:
return idx
idx += 1
return idx提交代码评测得到：耗时468ms，占用内存28MB。
当前还没有足够的提交结果，因此，暂时不知道当前是否还有更加优雅高效的代码，有兴趣的读者可以后续自行关注一下。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
这一题也是一开始就想岔了，开始就想着使用dfs方式去遍历所有可能的路径，然后找出第k个指令进行输出，结果就呵呵了，测试样例好像只通过了5个吧，严重超时，简直不能看。
后来仔细想了一下，因为是按照字符进行排序的，因此H一定排在V前面，那么，我们只要计算出当一次操作执行了H操作之后后面有多少条指令，是否能够包含住第K条指令就可以一步一步推导出每一步所需的指令了。
2. 代码实现
因此，我们只需要按照上述思路来一步一步推到当前每一步需要执行的操作就可以了。
给出python代码实现如下：
class Solution:
def kthSmallestPath(self, destination: List[int], k: int) -> str:
n, m = destination
cnm = [[1 for _ in range(m+1)] for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
cnm[i][j] = cnm[i][j-1] * (i+j) // j
ans = ""
while m > 0 and k > 0:
if k > cnm[n][m-1]:
ans += "V"
k -= cnm[n][m-1]
n -= 1
else:
ans += "H"
m -= 1
return ans + "H" * m + "V" * n提交代码评测得到：耗时40ms，占用内存14.1MB。
当前最优的代码实现耗时36ms，但是看了一下他的核心解题思路和我们是完全一致的，因此这里就不再多做展开了。
腾讯云开发者
