这一周的四道题倒是挺顺利地就搞定了,不过鉴于第一名也就花了5分钟,实在是也没啥成就感……
最近一段时间可能真的比较凌乱吧,房子快要到期了,然后忙忙碌碌地找新室友,公司里面也是刚好轮到on call,各种报警烦的一塌糊涂……
唯一的好消息大概就是最近终于重新做了一些模型方面的优化,不过时间紧任务重,结果方面目前还没有什么太过拿得出手的结果,不过总算能写代码就算是比较幸福的事情了……
anyway,算是自己发发牢骚吧,忘了在哪看到过说这世上其实没有长大这么一回事,说白了其实就是确实地认识到所有的事都需要自己来兜底了,所以发牢骚归发牢骚,抱怨过后一切依然照旧,总不能因为心累就放弃努力了吧,那就真的啥希望都没了……
给出题目一的试题链接如下:
这一题只要对数字进行去重,然后找到所有的非零数字的个数即可。
给出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。
给出题目二的试题链接如下:
这一题事实上我们可以给出一个万能的数列构造方法,即:
由上述构造方法,我们总能够完成目标构造,且上述构造方式能够构造的堆一定是最多的。
因此,假设总元素个数为n,那么我们只需要找到一个最大的x,使得满足下式即可。
这就变成一道初中数学题目了……
给出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。
给出题目三的试题链接如下:
这一题的话细节上其实有蛮多需要考察的特殊情况的,比如是否成环,是否联通等等,如果一开始没注意到这些的话还是比较容易答错的。不过我们可以给出一个较为一般的思路,从而使得无需对上述特殊情况进行考察。
具体而言,我们只要分别以两个node作为起点,然后考察所有其能够往后经历到达的点(到循环或者终点结束),记录下其距离,然后比较两个距离之中的较大值即可。
给出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。
给出题目四的试题链接如下:
这一题和上一题的思路基本是一脉相承的,只需要以每一个点作为起点考察一下其是否成环,然后成环的话这个环的长度是多少,然后取出一个最大值即可。
给出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。