LeetCode笔记：Weekly Contest 304

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

• 比赛链接：https://leetcode.com/contest/weekly-contest-304/

0. 小结

这一周的四道题倒是挺顺利地就搞定了，不过鉴于第一名也就花了5分钟，实在是也没啥成就感……

最近一段时间可能真的比较凌乱吧，房子快要到期了，然后忙忙碌碌地找新室友，公司里面也是刚好轮到on call，各种报警烦的一塌糊涂……

唯一的好消息大概就是最近终于重新做了一些模型方面的优化，不过时间紧任务重，结果方面目前还没有什么太过拿得出手的结果，不过总算能写代码就算是比较幸福的事情了……

anyway，算是自己发发牢骚吧，忘了在哪看到过说这世上其实没有长大这么一回事，说白了其实就是确实地认识到所有的事都需要自己来兜底了，所以发牢骚归发牢骚，抱怨过后一切依然照旧，总不能因为心累就放弃努力了吧，那就真的啥希望都没了……

1. 题目一

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

• 2357. Make Array Zero by Subtracting Equal Amounts

1. 解题思路

这一题只要对数字进行去重，然后找到所有的非零数字的个数即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        nums = set(nums)
        n = len(nums)
        return n if min(nums) != 0 else n-1

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

2. 题目二

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

• 2358. Maximum Number of Groups Entering a Competition

1. 解题思路

这一题事实上我们可以给出一个万能的数列构造方法，即：

• 我们对所有的数字进行从小到大有序排列，然后依次取1、2、3…个元素，直至无法取满元素之后将剩余的元素加入到最后一个堆之中。

由上述构造方法，我们总能够完成目标构造，且上述构造方式能够构造的堆一定是最多的。

因此，假设总元素个数为n，那么我们只需要找到一个最大的x，使得满足下式即可。

$$\frac{x(x+1)}{2}\le n$$

这就变成一道初中数学题目了……

2. 代码实现

给出python代码实现如下：

class Solution:
    def maximumGroups(self, grades: List[int]) -> int:
        n = len(grades)
        return int((math.sqrt(8*n+1)-1) / 2)

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

3. 题目三

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

• 2359. Find Closest Node to Given Two Nodes

1. 解题思路

这一题的话细节上其实有蛮多需要考察的特殊情况的，比如是否成环，是否联通等等，如果一开始没注意到这些的话还是比较容易答错的。不过我们可以给出一个较为一般的思路，从而使得无需对上述特殊情况进行考察。

具体而言，我们只要分别以两个node作为起点，然后考察所有其能够往后经历到达的点（到循环或者终点结束），记录下其距离，然后比较两个距离之中的较大值即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def closestMeetingNode(self, edges: List[int], node1: int, node2: int) -> int:
        n = len(edges)
        
        dis1 = [math.inf for _ in range(n)]
        dis = 0
        while edges[node1] != -1 and dis1[node1] == math.inf:
            dis1[node1] = dis
            dis += 1
            node1 = edges[node1]
        if dis1[node1] == math.inf:
            dis1[node1] = dis
        
        dis2 = [math.inf for _ in range(n)]
        dis = 0
        while edges[node2] != -1 and dis2[node2] == math.inf:
            dis2[node2] = dis
            dis += 1
            node2 = edges[node2]
        if dis2[node2] == math.inf:
            dis2[node2] = dis

        dis = math.inf
        res = -1
        for i in range(n):
            if max(dis1[i], dis2[i]) < dis:
                dis = max(dis1[i], dis2[i])
                res = i
        return res

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

4. 题目四

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

• 2360. Longest Cycle in a Graph

1. 解题思路

这一题和上一题的思路基本是一脉相承的，只需要以每一个点作为起点考察一下其是否成环，然后成环的话这个环的长度是多少，然后取出一个最大值即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def longestCycle(self, edges: List[int]) -> int:
        n = len(edges)
        dis = [-1 for _ in range(n)]
        res = -1
        for i in range(n):
            if dis[i] != -1:
                continue
            d = 0
            path = set()
            while edges[i] != -1 and dis[i] == -1:
                path.add(i)
                dis[i] = d
                i = edges[i]
                d += 1
            if i in path:
                res = max(res, d-dis[i])
        return res

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