LeetCode笔记：Biweekly Contest 41 比赛记录
LeetCode笔记：Biweekly Contest 41 比赛记录
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
第一题倒是一贯的挺简单的，最简单的思路就是直接做个二层循环就是了，不过我在比赛的时候想岔了，想着那样的算法复杂度恐怕有点高，就想着先将它转换为集合来处理，虽然也没啥问题，但是后来想想，完全没有对时间复杂度有所优化。
2. 代码实现
给出python代码实现如下：
class Solution:
def countConsistentStrings(self, allowed: str, words: List[str]) -> int:
cnt = 0
allowed = set(allowed)
for w in words:
if all(c in allowed for c in w):
cnt += 1
return cnt提交代码评测得到：耗时272ms，占用内存16.3MB。
当前的最优算法耗时220ms，但是本质上算法思路是完全相同的。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题比赛的时候脑子就是晕晕乎乎的，虽然知道直接暴力求解大概率会遇到超时问题，但是还是不信邪的作死试了一下，结果果然呵呵了。
后来仔细分析了一下题目，发现这一题事实上还是挺直观的。
我们考察任意第i个元素的情况，有：
如此一来，我们可以看到，只要事先求出所有元素的累积求和，就可以将二层循环退化为单层循环关系。
2. 代码实现
给出最终的python代码实现如下：
class Solution:
def getSumAbsoluteDifferences(self, nums: List[int]) -> List[int]:
n = len(nums)
cumsum = list(accumulate(nums))
res = [0 for i in range(n)]
for i in range(n):
res[i] = (i+1)*nums[i]-cumsum[i] + (cumsum[-1]-cumsum[i]) - (n-i-1)*nums[i]
return res提交代码评测得到：耗时948ms，占用内存29.5MB。
当前的最优算法实现耗时500ms，但是看了一下他们的算法思路，和我们的算法本质上是完全相同的，因此就不过多展开了，有兴趣的读者可以自行去看一下他们的细节实现。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
第三题讲真算是一道挺有趣的题目吧，你能够将最优策略想清楚，那么你就能很快地将答案给写出来，否则的话就呵呵了。
我们来考察每一次具体的操作，无论是Alice还是Bob进行一次操作（这里不妨设为Alice，操作为选取第i个石头），带来的影响都是：Alice将会获得相应的分数aliceValues[i]，而Bob将失去对应的分数bobValues[i]。因此，该次操作给Alice带来的实际收益应当为aliceValues[i] + bobValues[i]。
因此，我们对其进行一下排序就能够获得双方的最优选取策略，然后分别计算一下两者的分数就可以知道最终的游戏结果。
2. 代码实现
给出python代码实现如下：
class Solution:
def stoneGameVI(self, aliceValues: List[int], bobValues: List[int]) -> int:
delta = [(x+y, idx) for idx, (x, y) in enumerate(zip(aliceValues, bobValues))]
delta = sorted(delta, key=lambda x: (-x[0], x[1]))
# print(delta)
alice = 0
bob = 0
for i, (s, idx) in enumerate(delta):
if i % 2 == 0:
alice += aliceValues[idx]
else:
bob += bobValues[idx]
# print(alice, bob)
if alice > bob:
return 1
elif alice == bob:
return 0
else:
return -1提交代码评测得到：耗时1496ms，占用内存39.4MB。
当前的最优算法实现耗时1128ms，他和我们的思路是相同的，但是在具体的实操过程中，他们并没有像我们这样构造了一个delta进行排序，而是直接对idx进行了排序。
有兴趣的读者可以自行实现一下看看。
4. 题目四
给出题目四的试题链接如下：
1. 解题思路
2. 代码实现
我们可以快速地给出python代码实现如下：
class Solution:
def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:
n = len(boxes)
dp = [2 for _ in range(n)] + [0]
for i in range(n-2, -1, -1):
dp[i] = dp[i] + dp[i+1]
weight = boxes[i][1]
addition = 2
for j in range(i+1, n):
weight += boxes[j][1]
if weight > maxWeight or j-i+1 > maxBoxes:
break
if boxes[j][0] != boxes[j-1][0]:
addition += 1
dp[i] = min(dp[i], addition + dp[j+1])
return dp[0]不过，很不幸于到超时问题，41个测试样例只能通过37个，分析其算法复杂度，最优情况下可以为O(N)，但是在最差的情况下可以退化到O(N?maxBoxes)。
显然，问题就出在了这个地方，可惜我们到最后都没能解决这个问题。
3. 算法优化
后续看了一下leetcode-cn当中的相关题目解答，发现整体思路事实上确实还是之前的思路，也确实是针对动态规划的滑动窗口部分进行优化，具体的优化思路是通过有序队列的方式进行优化。
我们首先给出之前的递推公式如下：
其中，dp(i)表示从第i个箱子开始到最后所需要的最小运输次数，f(i,j)表示一次搬运从第i个箱子到第j个箱子所需要的运输次数。
我们可以将上述递推公式进行一定的变换：
其中diff(i)表示从第0个箱子到第i个箱子为止，相邻箱子的目标港口不相同的个数。
那么，我们就只要在合法的窗口范围内维护一个有序递减队列就可以了。
当然，如果你不知道有序队列是啥，那么暴力一点通过维护一个有序数组的方式来优化算法，应该也是可以的。
给出相应的python代码实现如下：
class Solution:
def boxDelivering(self, boxes: List[List[int]], portsCount: int, maxBoxes: int, maxWeight: int) -> int:
n = len(boxes)
w = list(accumulate([0] + [x[1] for x in boxes]))
d = [0] + list(accumulate([1 if boxes[i][0] != boxes[i+1][0] else 0 for i in range(n-1)]))
dp = [0 for _ in range(n+1)]
q = []
i = n-1
while i >= 0:
while q != [] and (q[-1][0] - i > maxBoxes or w[q[-1][0]] - w[i] > maxWeight):
q.pop()
while q != [] and q[0][1] >= dp[i+1] + d[i]:
q.pop(0)
q.insert(0, (i+1, dp[i+1] + d[i]))
dp[i] = q[-1][1] + 2 - d[i]
i -= 1
return dp[0]提交代码评测得到：耗时2376ms，占用内存65.2MB。
当前的最优算法实现耗时1900ms，它的代码有点长，就没有细看，如果有兴趣的读者可以自行去研读一下。
当然，如果可以的话能够在评论区留言说明一下的话就更好了?