LeetCode笔记：Weekly Contest 224 比赛记录
LeetCode笔记：Weekly Contest 224 比赛记录
codename_cys
发布于 2021-03-27 22:29:46
发布于 2021-03-27 22:29:46
文章被收录于专栏：我的充电站
0. 赛后总结
这次的比赛结果而言真的是惨不忍睹，只做出两题，还错了两次，然后排名就真的惨不忍睹了，都没脸说成绩了，唉。。。
后面加油吧。。。
1. 题目一
给出题目一的试题链接如下：
1. 解题思路
这一题没啥说的，每个矩形的短边长就是能切出的最大正方形边长，然后对最大值统计一下频数就是最终的结果了。
2. 代码实现
给出python代码实现如下：
class Solution:
def countGoodRectangles(self, rectangles: List[List[int]]) -> int:
d = sorted(min(x) for x in rectangles)
cnt = Counter(d)
return cnt[d[-1]]提交代码评测得到：188ms，占用内存15.1MB。
2. 题目二
给出题目二的试题链接如下：
1. 解题思路
这一题事实上也没啥好说的，由于所有的数都不相同，因此如果两个不同的组合ab和cd乘积相同时，两者必不会有交叠。
因此，我们只需要统计每一个可能的成绩的组合次数即可。
2. 代码实现
给出python代码实现如下：
class Solution:
def tupleSameProduct(self, nums: List[int]) -> int:
nums = sorted(nums)
n = len(nums)
counter = defaultdict(int)
for i in range(n-1):
for j in range(i+1, n):
counter[nums[i]*nums[j]] += 1
cnt = 0
for x in counter.values():
cnt += x*(x-1) * 4
return cnt提交代码评测得到：耗时540ms，占用内存43MB。
3. 题目三
给出题目三的试题链接如下：
1. 解题思路
这一题算是这次比赛里面做的最为失败的一题吧，因为毫无思路，然后就被虐惨了。
现在也是看了leetcode上面别人写的算法解析才有了思路。
不过看过思路之后发现，这题确实还是蛮简单的，唉。。。
思路其实挺简单的，就是记录下每一行中每一列中的元素往上连续有多少个1，然后对其重新排个序，计算一下其中可能的最大矩阵面积大小即可。
由此得到的算法复杂度就是O(M⋅N)。
2. 代码实现
给出python代码实现如下：
class Solution:
def largestSubmatrix(self, matrix: List[List[int]]) -> int:
n, m = len(matrix), len(matrix[0])
up = [0 for _ in range(m)]
res = 0
for i in range(n):
up = [0 if y == 0 else x+1 for x, y in zip(up, matrix[i])]
tmp = sorted(up, reverse=True)
for j in range(m):
res = max(res, (j+1)*tmp[j])
if tmp[j]== 0:
break
return res提交代码评测得到：耗时1216ms，占用内存38.2MB。
4. 题目四
给出题目四的试题链接如下：
这一题放弃了，想了近一周，依然没有一个好的思路，试过dfs和bfs，前者一直遇到死循环没有debug出来问题，后者答案不对，真的是烦，暂时这里是放弃了，如果有读者有好的思路的话请务必不吝赐教一下，真心感谢，唉。。。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/01/21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
