LeetCode笔记：Biweekly Contest 43 比赛记录

codename_cys

发布于 2021-03-27 22:32:03

2320

发布于 2021-03-27 22:32:03

文章被收录于专栏：我的充电站

1. 题目一

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

5633. 计算力扣银行的钱

1. 解题思路

这一题没啥好说的，就是按照题目的意思直接按周求解一下即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def totalMoney(self, n: int) -> int:
        res = 0
        for i in range(n):
            res += (i // 7 + 1) + i % 7
        return res

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

当前最优的解法耗时36ms，但是本质上也没啥差别就是了，有兴趣的读者可以自行去看一下，这里就不多做展开了。

2. 题目二

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

5634. 删除子字符串的最大得分

1. 解题思路

这一题的解题思路事实上也还好，只要想通一点：

使用贪心算法优先将高分的操作全部执行不会影响最终的结果。

因此，我们只需要实现一个贪心算法来进行操作即可，即是说，当ab的分数高于ba时，就将所有的ab全部进行删除，然后删除所有的ba即可得到最终的最高分值，反之亦然。

2. 代码实现

给出python代码实现如下：

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        res = 0
        if x <= y:
            s1 = []
            for c in s:
                if c == "a" and s1 and s1[-1] == "b":
                    s1.pop()
                else:
                    s1.append(c)
            res += y * (len(s) - len(s1)) // 2
            s2 = []
            for c in s1:
                if c == "b" and s2 and s2[-1] == "a":
                    s2.pop()
                else:
                    s2.append(c)
            res += x * (len(s1) - len(s2)) // 2
        else:
            s1 = []
            for c in s:
                if c == "b" and s1 and s1[-1] == "a":
                    s1.pop()
                else:
                    s1.append(c)
            res += x * (len(s) - len(s1)) // 2
            s2 = []
            for c in s1:
                if c == "a" and s2 and s2[-1] == "b":
                    s2.pop()
                else:
                    s2.append(c)
            res += y * (len(s1) - len(s2)) // 2
        return res

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

当前的最优解法耗时296ms，大致看了一下，感觉思路上应该是没啥差别，不过细节没有详细看，有兴趣的读者可以自行研读一下，如果可以的话也希望在评论区指导一二。

3. 题目三

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

5635. 构建字典序最大的可行序列

1. 解题思路

这一题可以采用深度优先遍历，即从首位开始，在每一个未填的位置优先填入最大的可填值，直至第一次填充完成时，返回这个填充结果就是可以得到的最大结果。

2. 代码实现

给出python代码实现如下：

class Solution:
    def constructDistancedSequence(self, n: int) -> List[int]:
        res = [0 for _ in range(2*n-1)]
        status = [0 for _ in range(n+1)]
        
        def dfs(idx):
            nonlocal res
            if idx >= 2*n-1:
                return True
            for i in range(n, 0, -1):
                if status[i] == 1:
                    continue
                if i != 1 and idx + i < 2*n-1 and res[idx+i] == 0:
                    res[idx] = i
                    res[idx+i] = i
                    status[i] = 1
                    nxt_idx = res.index(0) if 0 in res else 2*n-1
                    success = dfs(nxt_idx)
                    if success:
                        return True
                    status[i] = 0
                    res[idx] = 0
                    res[idx+i] = 0
                elif i == 1:
                    res[idx] = i
                    status[i] = 1
                    nxt_idx = res.index(0) if 0 in res else 2*n-1
                    success = dfs(nxt_idx)
                    if success:
                        return True
                    status[i] = 0
                    res[idx] = 0
            return False

        dfs(0)
        return res

提交代码评测得到：耗时52ms，占用内存14.2MB。为当前最优的代码实现。

4. 题目四

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

5636. 重构一棵树的方案数

1. 解题思路

这里，我们先抛砖引玉一下吧，讲一下我们的思路。

首先，很明显可以看出的一点是：

如果某一个节点是根节点，那么它必然与所有的节点均有连接关系，因此，我们可以根据连接的其他节点的数目直接找到根节点；
如果根节点只有一个，我们将所有与根节点相关的连接全部去掉，就会得到一片森林，其中每一棵树都可以递归的调用上述算法看他是否存在连接，以及是否存在多种连接；
如果根节点有多个，那么我们同样可以删除所有包含这些节点的连接，同样可以得到一片森林，只不过，只要下述的森林中的树都可以构建，那么就有多种连接方式。

而判断去掉了根节点连接之后的所有节点哪些可以归于同一棵树的方法可以采用dsu算法。

这样，我们就可以写出一个递归调度算法。

2. 代码实现

给出python代码实现如下：

class DSU:
    def __init__(self, N):
        self.dsu = [i for i in range(N)]
        
    def find(self, k):
        if self.dsu[k] == k:
            return k
        self.dsu[k] = self.find(self.dsu[k]) 
        return self.dsu[k]
    
    def union(self, a, b):
        x = self.find(a)
        y = self.find(b)
        if x != y:
            self.dsu[y] = x
        return

class Solution:
    def checkWays(self, pairs: List[List[int]]) -> int:
        counter = defaultdict(int)
        for x, y in pairs:
            counter[x] += 1
            counter[y] += 1
        n = len(counter)
        if all(x == n-1 for x in counter.values()):
            return 2 if n >= 2 else 1
        if not any(x == n-1 for x in counter.values()):
            return 0

        roots = [x for x in counter if counter[x] == n-1]
        # print(pairs, n, counter, counter.values(), [x for x in counter.values() if x == n-1])
        
        pairs = [[x, y] for x, y in pairs if x not in roots and y not in roots]
        dsu = DSU(501)
        for x, y in pairs:
            dsu.union(x, y)
        pairs_group = defaultdict(list)
        for x, y in pairs:
            pairs_group[dsu.find(x)].append([x, y])
        if len(pairs_group) == 0:
            return 1 if len(roots) == 1 else 2
        res = []
        for p in pairs_group.values():
            cnt = self.checkWays(p)
            if cnt == 0:
                return 0
            res.append(cnt)
        return 1 if all(x == 1 for x in res) and len(roots) == 1 else 2

可惜，80个测试样例中只通过了77个，遇到了超时问题。

3. 算法优化

可惜了，想了两天，结果还是没有一个好的解答，最后还是看了别人的解答，然后就被震惊了，发现他们的解法真心优雅。

首先，还是我们之前的思路，不过他们提出了两个更为重要的中间结论：

如果有两个相互联通的点拥有相同的连接数目，则他们必然是互易的，即交换两个节点不会对最终的结果产生影响，此时，如果可以存在某种连接方式，那么他的种类必然多于1种；
儿子节点的连接数量总是不多于父亲节点的连接数量的，因此，当我们从连接最多的节点向下遍历其连接点时，总是可以将其父节点更新为更下层的这个新的节点。

因此，我们给出他们的python代码实现如下：

class Solution:
    def checkWays(self, pairs: List[List[int]]) -> int:
        cnt = collections.defaultdict(int)
        edges = collections.defaultdict(set)
        for u, v in pairs:
            cnt[u] += 1
            cnt[v] += 1
            edges[u].add(v)
            edges[v].add(u)
            
        nodes = sorted(cnt.keys(), key = lambda x: cnt[x], reverse = True)
        if cnt[nodes[0]] != len(nodes) - 1: return 0
        
        unique = True
        for x, y in pairs:
            if cnt[x] == cnt[y]:
                unique = False
                break

        pa = collections.defaultdict(int)
        pa[nodes[0]] = 0
        for o in nodes:
            for ch in edges[o]:
                if pa[ch] != pa[o]: return 0
                pa[ch] = o
                edges[ch].remove(o)
        
        return 1 if unique else 2

提交代码评测得到：耗时1588ms，占用内存43.7MB。属于当前最优的一批算法实现。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/01/11 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

python

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

python

登录后参与评论

0 条评论

热度