LeetCode笔记：Weekly Contest 219 比赛记录_错中求解的解题思路

• LeetCode笔记：Weekly Contest 219
  • 0. 赛后总结
  • 1. 题目一
    • 1. 解题思路
    • 2. 代码实现
  • 2. 题目二
    • 1. 解题思路
    • 2. 代码实现
  • 3. 题目三
    • 1. 解题思路
    • 2. 代码实现
  • 4. 题目四
    • 1. 解题思路
    • 2. 代码实现

0. 赛后总结

这一次的比赛怎么说呢，感觉有点不尴不尬的。

要说吧，4道题也都做出来了，耗时老实说也没有特别长，不算错误惩罚的话其实也就56分钟，不到1个小时，整体虽然没有挤进国内前100，好歹也有前4%（116/3682），世界排名也是311/9290，也属于前4%，照说应该是一次不错的发挥了。

但是吧，就是感觉不舒服，第三题第四题做的实在太纠结了，尤其是第三题，虽然说一次过了，但是用的是最暴力的迭代算法，讲道理能过完全是运气好，我本来完全没报希望的，只是因为实在想不到更好的算法了。

第四题也是，虽说最后以两次错误的代价提交成功了，但是看错题目实在是硬伤，而且算法也不算多少优雅，还是用的非常暴力的迭代求解的算法。

唉，回头等比赛结束之后好好地研究一下别人的解法学习一下吧。

1. 题目一

给出题目一的试题链接如下：

• 5625. 比赛中的配对次数

1. 解题思路

这一题思路很直接，就是直接按照规则一路往下就行了。

2. 代码实现

给出python代码实现如下：

class Solution:
    def numberOfMatches(self, n: int) -> int:
        res = 0
        while n != 1:
            res += n // 2
            n = (n+1) // 2
        return res
1
2
3
4
5
6
7

提交代码评测得到：耗时20ms，占用内存14.3MB。属于当前最优代码实现。

2. 题目二

给出题目二的试题链接如下：

• 5626. 十-二进制数的最少数目

1. 解题思路

这一题乍看之下有点复杂，但其实仔细一想异常简单，显然，由于二进制数只能由1、0组成，因此，对于任意一个数，假设这个数字中最大的比特数为k，则至少需要k个十-二进制数才能够分解这个数字。

而另一方面，如果我们采用如下规则进行数字拆解：

• 当且仅当数字中最大位数的位置取1，其他位置取0，构建一个十-二进制数，然后减去这个数字；

重复上述操作，可以看到，当k次操作之后，总能够将这个数字变为0。

综上，k就是最终的答案。

2. 代码实现

因此，我们可以快速地给出python代码实现如下：

class Solution:
    def minPartitions(self, n: str) -> int:
        return max(int(x) for x in n)
1
2
3

提交代码评测得到：耗时188ms，占用内存14.7MB。

当前的最优代码实现耗时仅52ms，但是本质来说算法思路是完全一致的，不过他们没有将每一个bit都进行整形转换，而是利用了ascii码中的顺序关系简化了代码。

给出他们的代码实现如下：

class Solution:
    def minPartitions(self, n: str) -> int:
        return ord(max(n)) - ord('0')
1
2
3

3. 题目三

给出题目三的试题链接如下：

• 5627. 石子游戏 VII

1. 解题思路

这一题比赛中我是用最为暴力地迭代方法进行求解的，因为递推公式还是很好写出来的。

假设在每一轮操作（Alice和Bob各自进行一次操作）当中，Alice选择的元素为$a$，Bob选择的元素为$b$，而在他们进行操作之前的元素总和为$s$，则Alice得分为$s-a$，Bob的得分为$s-a-b$，该轮操作导致的两人的分差变化为$b$

因此，我们可以快速地写出每一次操作的递推公式如下：

dp(i, j) = max(min(stones[j]+dp(i+1, j-1), stones[i+1] + dp(i+2, j)), min(stones[i]+dp(i+1, j-1), stones[j-1] + dp(i, j-2)))
1

其中，四种情况分别代表：

1. Alice优先取第i个元素：
   1. Bob取第j个元素；
   2. Bob取第i+1个元素；
2. Alice优先取第j个元素；
   1. Bob取第i个元素；
   2. Bob取第j-1个元素；

2. 代码实现

给出python代码实现如下：

class Solution:
    def stoneGameVII(self, stones: List[int]) -> int:
      
        @lru_cache(None)
        def dp(st, ed):
            if st >= ed:
                return 0
            else:
                return max(min(stones[ed]+dp(st+1, ed-1), stones[st+1] + dp(st+2, ed)), min(stones[st]+dp(st+1, ed-1), stones[ed-1] + dp(st, ed-2)))
            
        return dp(0, len(stones)-1)
1
2
3
4
5
6
7
8
9
10
11

提交代码评测得到：耗时4480ms，占用内存608.7MB。

当前的最优代码实现耗时4092ms，而且看他的实现也没觉得多好，但是我总觉得应该有更加优雅的实现方法，唉，过两天再看看有没有更好的解法吧。

4. 题目四

给出题目四的试题链接如下：

• 5245. 堆叠长方体的最大高度

1. 解题思路

这一题坦率地说感觉也是应该有更好的解题方法的，可惜我这边实在是没想到什么更好更优雅的解题方法，只能用暴力求解的方法硬怼。

不过幸运的是，终究还是怼出来了就是了。

对于这一题，核心在于两点：

1. 排序
2. 递推关系

首先，由于题目限制说一个长方体$j$要能够叠放在另一个长方体$i$的话，要求：
{ w i ≥ w j l i ≥ l j h i ≥ h j \left\{

$$\begin{aligned} w_i &\geq w_j \\ l_i &\geq l_j \\ h_i &\geq h_j \end{aligned}$$ \right. ⎩⎪⎨⎪⎧​wi​li​hi​​≥wj​≥lj​≥hj​​

因此，我们对长方体按照边长进行排序，显然最终的结果必然是排序后结果的一个子序列。

另一方面，我们来讨论递推关系，他有以下一些情况：

1. 当前长方体不使用的情况；
2. 当前长方体使用的情况，此时根据长宽高的选择又可以分为三种情况。

综上，我们就可以给出最终的递推关系。

2. 代码实现

给出python的代码实现如下：

class Solution:
    def maxHeight(self, cuboids: List[List[int]]) -> int:
        n = len(cuboids)
        cuboids = sorted([sorted(x, reverse=True) for x in cuboids], reverse=True)
        # print(cuboids)
        
        @lru_cache(None)
        def dp(idx, a, b, c):
            if idx >= n:
                return 0
            res = dp(idx+1, a, b, c)
            aa, bb, cc = cuboids[idx]
            if cc <= c and ((aa <= a and bb <= b) or (aa <= b and bb <= a)):
                res = max(res, cc + dp(idx+1, aa, bb, cc))
            if bb <= c and ((aa <= a and cc <= b) or (aa <= b and cc <= a)):
                res = max(res, bb + dp(idx+1, aa, cc, bb))
            if aa <= c and ((bb <= a and cc <= b) or (bb <= b and cc <= a)):
                res = max(res, aa + dp(idx+1, bb, cc, aa))
            return res
                
        return dp(0, 101, 101, 101)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

提交代码评测得到：耗时404ms，占用内存35.4MB。

当前最优的代码实现耗时132ms，大致看了一下，感觉思路上和我们是一致的，不过细节实现上有所差别，感觉比我们的更加简明一些，不过细节没有细看，有兴趣的读者可以自行研究一下。