提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

LeetCode笔记：Weekly Contest 267

笔记 代码
2023-03-15 22:08:34 时间

1. 题目一

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

1. 解题思路

要等第k个人买完票，那么他必须要买tickets[k]轮，其前面所有的人如果买的票少于他，那么全部需要考虑在内，而其他人只需要等他们买完相同多张票即可。

而对于后方的人，有效轮次则为tickets[k]-1轮。

2. 代码实现

给出python代码实现如下：

class Solution:
    def timeRequiredToBuy(self, tickets: List[int], k: int) -> int:
        _max = tickets[k]
        return sum([min(x, _max) for x in tickets[:k+1]] + [min(x, _max-1) for x in tickets[k+1:]])

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

2. 题目二

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

1. 解题思路

这一题我的思路比较暴力，就是按照其题意暴力解答即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None
        
        vals = []
        while head:
            vals.append(head.val)
            head = head.next
        
        i, j, n = 0, 1, len(vals)
        res = []
        while i < n:
            if j % 2 == 1:
                res = res + vals[i: i+j]
            else:
                res = res + vals[i: i+j][::-1]
            i += j
            j = min(j+1, n-i)
        
        head = ListNode(res[0])
        p = head
        for val in res[1:]:
            node = ListNode(val)
            p.next = node
            p = node
        return head

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

3. 题目三

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

1. 解题思路

这一题同样暴力求解即可。

我们首先将字符串进行分割，得到matrix，然后按照题意进行解码即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def decodeCiphertext(self, encodedText: str, rows: int) -> str:
        n = len(encodedText)
        m = n // rows
        rows = min(m, rows)
        s = []
        for i in range(rows):
            s.append(encodedText[i*m:(i+1)*m][i:])
        
        if s == []:
            return ""
        
        res = ""
        for j in range(len(s[0])):
            for i in range(rows):
                if j < len(s[i]):
                    res += s[i][j]
        return res.rstrip()

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

4. 题目四

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

1. 解题思路

这一题我的思路就是一个dsu的思路，还是很暴力的，对于查找那一块并没有优化，就是对于每一个限制都进行一次判断，不过判断本身使用dsu进行。

另外就是，这里的dsu进行了一定的修改，因为需要操作是可逆的，因此，在中间的查找过程我们故能够更新dsu的key节点，否则就会出现不可逆的情况。

但是如果一直不更新dsu的中心节点，那么就会出现超时，因此这里比较无奈的在每次加入新的连接之后都会强制刷一遍节点，来更新中心节点。

万幸这样可以勉强通过测试。

2. 代码实现

给出python代码实现如下：

class DSU:
    def __init__(self, n):
        self.dsu = [i for i in range(n)]
        
    def find(self, x, update=False):
        if self.dsu[x] == x:
            return x
        if not update:
            return self.find(self.dsu[x], False)
        else:
            self.dsu[x] = self.find(self.dsu[x], True)
            return self.dsu[x]

class Solution:
    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:
        dsu = DSU(n)
        res = []
        for u, v in requests:
            uk = dsu.find(u, True)
            vk = dsu.find(v, True)
            dsu.dsu[uk] = vk
            if any(dsu.find(x, False) == dsu.find(y, False) for x, y in restrictions):
                res.append(False)
                dsu.dsu[uk] = uk
            else:
                for i in range(n):
                    dsu.find(i, True)
                res.append(True)
        return res

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

相关文章