讨论/题目交流/🏆2019 力扣杯 - 全国秋季编程大赛/
🏆2019 力扣杯 - 全国秋季编程大赛

image.png

你来写我来送: 欢迎大家在本条讨论下分享和编写本次 🏆 力扣杯大赛的解题思路 / 题解

在「圈子」内撰写题解文章的同学也可以将文章链接贴在本条讨论下,力扣君将在 2019 年 10 月 10 日下午 16:00 精选 两篇优质内容,分别送出 1 本 《程序员面试金典》。
1821567415874_.pic_hd.jpg

共 23 个回复

本届「力扣杯 - 全国秋季编程大赛」及往届力扣杯竞赛的题目现已更新至「力扣题库」中,扣友们可以即刻前往「🏆 2019 力扣杯 - 竞赛合集」进行练习。

恭喜 @haozheyan97 和 @Xdo 在本次「你来写我来送:力扣杯优质题解」评选活动中脱颖而出,力扣君将分别送出 1 本《程序员面试金典》。

相关内容推荐:
https://leetcode-cn.com/circle/discuss/1I3IVg/view/WSfk3R/
https://leetcode-cn.com/circle/discuss/1I3IVg/view/jKpaGN/

5

Problem 1
签到题,一个一个挨个比较就行。
时间复杂度 O(n)O(n)
空间复杂度 O(n)O(n)

Problem 2
还是签到,但是记住要将每一个分子分母取反并用 gcd 化简,好在最后全是正数省略了许多判断。
时间复杂度 O(n log(max(n))O(n\ log(max(n))
空间复杂度 O(1)O(1)

Problem 3
这个题直接模拟的话会不知道什么时候停止。而因为每次循环都会使得机器人向右和向上移动同样的格子数。经过若干次循环后,我们可以将新的起点当做原点,所有障碍物向左向下平移即可形成和初始状态相同(相似)的状态。
因此在开始的时候就可以判断机器人经过平移后每个障碍物是否会在机器人的路线上。只需要模拟一次就可以。
时间复杂度 O(∣command∣2)O(|command| ^ 2)
空间复杂度 O(∣command∣2)O(|command| ^ 2)

Problem 4
这个是典型的轮廓线动态规划题目。每次放置考虑从上到下,从左至右放置。按照这种规律放的话,每次放置,只需要记录从上一行的该格子到该格子前一个的状态。使用状态压缩转为 2 进制即可很方便使用 dp 进行转移。

But... 如果说记录全盘的状态,则状态数会高达 O(2mn)O(2^{mn}),在这道题的范围下,状态数堪比棋盘上的麦粒那么多。显然,需要一定技巧来减少需要记录的状态量。

dp_graph.jpg

具体说一下,就是这个题目,当我们放置每个方块的时候,只有 3 种,不放,横放和竖放。如图所示,当我们考虑在绿色格子 K0 放置的时候,能否放骨牌和灰色格子无关而只与五个红色格子的状态有关(注 1)(即如果 K5 号格没有骨牌才能竖放,K1 号格没有才能横放)。也就是说,K0 处能否放骨牌,会涉及到至多前 m 个格子的状态,因此用一个 m 维向量来表示即可(转换为 2 进制就可以作为数组下标)。当状态为 (K5, K4, K3, K2, K1) 会转移到一个新的状态 (K4, K3, K2, K1, K0)。根据具体的数值即可推算出结果。

P.S.

  1. 注意因为动态规划的顺序,横放只可以向左放,竖放只能向上放。

时间复杂度 O(m∗n∗2m)O(m * n * 2 ^ m)
空间复杂度使用普通数组则为 O(m∗n∗2m)O(m * n * 2 ^ m)
滚动数组则为 O(2m)O(2 ^ m)。

Problem 5
感觉这个题比第四题还要简单一些。
这道题是在树上操作,而每一次操作都只涉及单点和子树问题。
我们知道,处理子树问题如果能把树化为一维数组来做就可以了。而很明显这道题使用 DFS 序列这种做法,先做一次 DFS,将每个点入栈和出栈的 timestamp 记录下来,这个 timestamp 之间就是以该点为根的子树。将 DFS 序列作为新的序列,使用线段树就可以了。
时间复杂度 O(n log n+q log n)O(n\ log\ n + q\ log\ n)
空间复杂度 O(n log n)O(n\ log\ n)

25

我来分享一下我的代码和思路,自我感觉还是比较清晰的
来自菜鸡的题解

第一题 主要是拼手速

class Solution {
public:
    int game(vector<int>& guess, vector<int>& answer) {
        int num = 0;
        for(int i=0; i<3; i++)
            if(guess[i] == answer[i]) num++;
        return num;
    }
};

第二题 主要是根据公式进行计算,然后化简即可

可以看出每次去计算的时候都有

Snipaste_2019-09-27_22-14-34.jpg
计算后,反转一下 分子 分母 并化简,然后继续获得新的 b 重复操作
至于这三个字母为什么是这个顺序,主要是当时比赛的时候随便写的,23333

class Solution {
public:
    // 传入引用,同步更改传入的实参
    void simp(int &a, int &b) {
        // __gcd 是 C++ 封装好的求最大公约数的函数,直接调用即可
        int g = __gcd(a, b);
        a /= g, b /= g;
    }
    vector<int> fraction(vector<int>& cont) {
        int a = cont.back(), b, c = 1;
        for(int i=cont.size()-2; i>=0; i--) {
            b = cont[i];
            if(b == 0) swap(a, c);
            else {
                int tem = a;
                a = a*b + c;
                c = tem;
                simp(a, c);
            }
        }
        simp(a, c);
        return {a, c};
    }
};

第三题

主要需要把机器人的一轮操作记录一下,形成一个范围,
然后把障碍物以及终点根据距离相应地映射到这个范围内比较一下

class Solution {
public:
    bool robot(string co, vector<vector<int>>& ob, int x, int y) {
        int len = co.size(), a = 0, b = 0, m, n;
        // 根据坐标点的 x+y 大小把障碍点排序
        sort(ob.begin(), ob.end(), [](vector<int> &a, vector<int> &b) {return a[0]+a[1] < b[0]+b[1];});
        // 通过一个哈希表来记录 记录一轮操作走过的范围
        unordered_set<int> hashSet;
        hashSet.insert(0);
        for(auto &ch:co) {
            if(ch == 'U') b++;
            else a++;
            // 字符串最长不超过 1000 
            hashSet.insert(a*1000 + b);
        }
        // 把终点映射到机器人的一轮操作范围内,查看机器人能够经过终点
        m = x - (x + y) / len * a;
        n = y - (x + y) / len * b;
        // 到达不了终点
        if(hashSet.find(m*1000 + n) == hashSet.end()) return false;
        for(int i=0; i<ob.size(); i++) {
            // 终点前面的障碍都碰不到
            // 当前障碍的距离大于终点,说明已经到了终点
            if(ob[i][0] + ob[i][1] > x + y) return true;
            m = ob[i][0] - (ob[i][0] + ob[i][1]) / len * a;
            n = ob[i][1] - (ob[i][0] + ob[i][1]) / len * b;
            // 提前碰到障碍
            if(hashSet.find(m*1000 + n) != hashSet.end()) return false;
        }
        return true;
    }
};

第四题

比赛的时候并没有 AC
赛后看了大佬的代码以及 二分匹配的匈牙利算法 后写的 AC 代码

class Solution {
public:
    bool dfs(int u, vector<bool> &rep, vector<vector<int>> &G, vector<int> &mat) {
        for(int i=0; i<G[u].size(); i++) {
            int v = G[u][i];
            if(!rep[v]) { // 结点如果没有在交替路径中
                rep[v] = true;
                // 如果当前结点没有匹配,就进行匹配,或者交替路径交换
                if(mat[v] == -1 || dfs(mat[v], rep, G, mat)) {
                    mat[u] = v; // 进行匹配点的记录
                    mat[v] = u;
                    return true;
                }
            }
        }
        return false;
    }
    void getRes(int &res, int N, vector<vector<int>> &G) {
        // 初始化匹配点都是-1
        vector<int> mat(N, -1);
        for(int i=0; i<N; i++) 
            if(mat[i] == -1) {
                vector<bool> rep(N, false);
                // 每一次增广路径遍历之后,使得匹配点的对数加1
                if(dfs(i, rep, G, mat)) res++;
            }
    }
    int domino(int n, int m, vector<vector<int>>& b) {
        int N = n*m, u, v, res = 0;
        vector<vector<int>> G(N);
        vector<vector<bool>> used(n, vector<bool>(m, false));
        for(auto &it:b)
            used[it[0]][it[1]] = true;
        
        for(int i=0; i<n; i++) 
            for(int j=0; j<m; j++) 
                if(!used[i][j]) {
                    u = i*m+j;
                    if(j+1 < m && !used[i][j+1]) {
                        v = i*m + j + 1;
                        G[u].push_back(v);
                        G[v].push_back(u);
                    }
                    if(i+1 < n && !used[i+1][j]) {
                        v = i*m + m + j;
                        G[u].push_back(v);
                        G[v].push_back(u);
                    }
                }
        getRes(res, N, G);
        return res;
    }
};

第五题

这一题,我的代码复杂度相当高,所以代码看起来比较精简,属于卡着线过的 704ms
这一题,我查询的复杂度为 O(1)O(1),整加一个人的钱数的复杂度为 O(M)O(M),M 为最深的层数
增加一群人的钱数的复杂度为 O(M∗N)O(M * N),N 为人数

class Solution {
public:
    const int mod = 1e9 +7;
    void dfs(vector<vector<int>>& gr, vector<int>& fa, vector<long long> &res, int x, int y) {
        // 增加当前点的每个人以及对应上司的奖金
        up(gr, fa, res, x, y);
        for(int i=0; i<gr[x].size(); i++)
            // 递归遍历每个点
            dfs(gr, fa, res, gr[x][i], y);
    }
    void up(vector<vector<int>>& gr, vector<int>& fa, vector<long long> &res, int cur, int mon) {
        // 增加每个人以及对应上司的奖金
        while(cur != 0) {
            res[cur] = (res[cur] + mon) % mod;
            cur = fa[cur];
        }
    }
    vector<int> bonus(int n, vector<vector<int>>& le, vector<vector<int>>& op) {
        // 建立基于邻接表的图,因为没有环,所以其实是棵树
        vector<vector<int>> graph(n+1);
        // 每个节点以及子节点的奖金值
        vector<long long> res(n+1, 0);
        // 保存每个节点的父节点
        vector<int> fa(n+1, 0);
        // 建立连接,以及更新父节点
        for(auto &it:le) graph[it[0]].push_back(it[1]), fa[it[1]] = it[0];
        vector<int> ret;
        for(auto &it:op) {
            // 根据命令不同,进行对应操作
            if(it[0] == 1) up(graph, fa, res, it[1], it[2]);
            else if(it[0] == 2) dfs(graph, fa, res, it[1], it[2]);
            else ret.push_back(res[it[1]] % mod);
        }
        return ret;
    }
};
17

第一次参与这种比赛,水平还差很多啊。什么时候放出题目和测试用例?

14

第三题 机器人大冒险 老是超时 哭了我都

12

做完的时候一看最后一题的通过人数54,还以为进不了前50,结果成绩出来,5题做完就行,白嫖一本书和7天会员就很开心

10

1. 猜数字

原题链接

挨个比较。

class Solution:
    def game(self, guess: List[int], answer: List[int]) -> int:
        res = 0
        for i in range(3):
            if guess[i] == answer[i]:
                res += 1
        return res

2. 分式化简

原题链接

是一个不 “取反、相加” 的循环。

class Solution:
    def fraction(self, cont: List[int]) -> List[int]:
        length = len(cont)
        res = [cont[length - 1], 1]
        for i in range(length - 2, -1, -1):
            # 取反
            cur = cont[i]
            left = cur * res[0]
            res = [res[1] + left, res[0]]
        
        return res

3. 机器人大冒险

原题链接

先记录一波数据:

  1. 把执行一次命令能走到的点都记录下来,记为 path
  2. 把命令中 R 的次数记作 px,U 的次数记作 py

那么拿到一个点 (x, y) 时,求出需要循环执行命令的次数:

r = min(x // px, y // py)

循环 r 次命令后剩余的步数为:(x - r * px, y - r * py)。若 (x - r * px, y - r * py) 在 path 中,则说明可以走到点 (x, y)。

class Solution:
    def robot(self, command: str, obstacles: List[List[int]], x: int, y: int) -> bool:
        path = set()
        path.add((0, 0))
        
        px = 0
        py = 0
        for c in command:
            if c == "R":
                px += 1
            else:
                py += 1
            path.add((px, py))
            
        def can_arrive(x, y):
            x_round = x // px
            y_round = y // py
            r = min(x_round, y_round)
            lx = x - r * px
            ly = y - r * py
            if (lx, ly) in path:
                return True
            else:
                return False
        
        if not can_arrive(x, y):
            return False
        
        for ob in obstacles:
            if ob[0] > x or ob[1] > y:
                continue
            if can_arrive(ob[0], ob[1]):
                return False
        
        return True

4. 覆盖

原题链接

状态压缩 + 动态规划完成状态转移。

一个格子无非只有如下几种情况:

  1. 放骨牌
    1. 横着放
    2. 竖着放
  2. 不放骨牌
    1. 不是坏格子,选择不放
    2. 是坏格子,不可以放

来看一个 n = 3, m = 3 的栗子:

dp-state.png

我们从上往下、从左往右对所有格子进行遍历。此时我们遍历到黄色格子 0,判断该格子能否放置骨牌:

  1. 如果格子 0 是一个坏掉的格子:不能放置骨牌
  2. 如果格子 0 不是一个坏格子:
    1. 如果上侧的格子 3 是一个未被占用的好格子:格子 0 可以竖放骨牌
    2. 如果左侧的格子 1 是一个未被占用的好格子:格子 0 可以横放骨牌
    3. 如果上侧格子 3 和左侧格子 1 都无法放置骨牌:格子 0 无法放置骨牌

由此,我们可以发现,对于一个格子来说,它的前 m 个格子的状态决定了该格子放置骨牌的可能性。

状态表示

由于需要记录 m 个格子的状态,而一个格子又只有 2 种状态(放骨牌或不放骨牌),很自然地想到可以用 m 位二进制数 来表示这 m 个格子的状态。

  • 0 表示格子不放置骨牌
  • 1 表示格子放置骨牌

m 个格子就有 2m2^m 种状态。

状态转移

我们从始至终都只需要用到所遍历到格子的前 m 个格子的状态,因此需要不断更新这 m 个格子的状态,即进行状态转移。上述栗子中,(3, 2, 1) 格子的状态就需要转移为 (2, 1, 0) 格子的状态。

这个步骤用位运算实现:

  1. 坏格子:砍掉状态最高位 -> 左移 1 位 -> 最低位置 1
  2. 不放骨牌:砍掉状态最高位 -> 左移 1 位
  3. 横放骨牌:砍掉状态最高位 -> 左移 1 位 -> 最低两位置 1
  4. 竖放骨牌:砍掉状态最高位 -> 左移 1 位 -> 最低位置 1

动态规划

如果一个格子有多种放置骨牌的方法,又该怎么办?答案是用动态规划选择能放置最多骨牌数量的最优解。

我们开辟一个 2m2^m 大小的数组空间 dp。数组的下标为状态值,数组的值用于表示该状态下能摆放的最多骨牌数,当值为 -1 时表示该状态为非法状态。

步骤总结

  1. 从左往右、从上往下遍历格子(意图为计算下一个状态 next_dp)
  2. 在当前格子中遍历所有 2m2^m 种状态
  3. 若状态非法,继续步骤 2
  4. 若状态合法,根据状态转移计算出下一个状态 next_state 以及该状态下对应的 dp

实现

复杂度为 O(m∗n∗2m)O(m * n * 2^m)。

class Solution:
    def domino(self, n: int, m: int, broken: List[List[int]]) -> int:
        # broken 记录
        broken_map = dict()
        for b in broken:
            if b[0] not in broken_map:
                broken_map[b[0]] = dict()
            broken_map[b[0]][b[1]] = True
            
        """
        是坏格子
        """
        def is_broken(a, b):
            if a in broken_map and b in broken_map[a]:
                return True
            else:
                return False
            
        """
        获取下一个状态
        put: 0-不放,1-横放,2-竖放,3-坏格子
        """
        def next_state(state, put):
            # 去除高位
            state = ~(1 << (m - 1)) & state
            
            if put == 0:
                # 不放牌
                return state << 1
            elif put == 1:
                # 横着放
                return ((state | 1) << 1) | 1
            elif put == 2:
                # 竖着放
                return (state << 1) | 1
            else:
                # 坏格子
                return (state << 1) | 1
            
        # 创建 dp
        dp = [-1] * (1 << m)
        dp[(1 << m) - 1] = 0 # 全 1 的置 0
        
        for i in range(n):
            for j in range(m):
                next_dp = [-1] * (1 << m)
                # 遍历所有状态
                for state in range(1 << m):
                    # 非法状态
                    if dp[state] == -1:
                        continue
                    
                    if is_broken(i, j):
                        # 是坏格子
                        next_dp[next_state(state, 3)] = max(next_dp[next_state(state, 3)], dp[state]) # 是从 dp 转义还是保持现状
                        continue
                       
                    # 不放
                    next_dp[next_state(state, 0)] = max(next_dp[next_state(state, 0)], dp[state])
                    
                    # 可以竖放
                    if i != 0 and (1 << (m - 1)) & state == 0:
                        next_dp[next_state(state, 2)] = max(next_dp[next_state(state, 2)], dp[state] + 1)
                    
                    # 可以横放
                    if j != 0 and 1 & state == 0:
                        next_dp[next_state(state, 1)] = max(next_dp[next_state(state, 1)], dp[state] + 1)
                
                dp = next_dp
                        
        return max(dp)

5. 发 LeetCoin

原题链接

把题中所有上级下级关系转化为一棵树。如果每次操作和查询都挨个遍历树的所有子节点是不现实的,分分钟超出时间限制。为了节省时间,我们需要对每个节点单独记录几个属性:

  1. 节点的父节点(用于向上更新父节点值)parent
  2. 节点和其子节点的 coin 总数 coin
  3. 通过操作 2 操作该节点时下发的 coin 数量 children_coin
  4. 该节点包含的子节点数 count

假设我们对节点 node 执行以下操作:

操作 1

操作 1 发放 val 数量的 LeetCoin:

  1. 更新 node 节点的 coin += val
  2. 更新其所有父节点的 coin += val

操作 2

操作 2 发放 val 数量的 LeetCoin,节点 node 共有 node.count 个子节点,因此共加上 LeetCoin all_coin = node.count * val 个:

  1. 更新 node 节点的 coin += all_coin
  2. 更新 node 节点的所有父节点 coin += all_coin
  3. 更新 node 节点的 children_coin += val

操作 3

node 节点与其子节点的所有 LeetCoin 和为:

node.coin + (node.parent.children_coin * node.count + node.parent.parnet.children_coin * node.count ......)

因为每个节点的 children_coin 代表对子节点产生的 LeetCoin 影响,因此计算每个节点与其子节点的 LeetCoin 之和时,需要往前遍历它的所有父节点,并加上 children_coin * node.count。

代码实现

class Node:
    def __init__(self):
        self.parent = None # 父节点
        self.children = [] # 子节点数组
        self.coin = 0 # 子树总coin
        self.children_coin = 0 # 2 操作分配的 coin(影响到所有子树)
        self.count = 1 # 子树节点数

class Solution:
    def bonus(self, n: int, leadership: List[List[int]], operations: List[List[int]]) -> List[int]:
        # 初始化数据
        nodes = dict()
        for i in range(1, n + 1):
            nodes[i] = Node()
        
        # 记录从属关系
        for leader, worker in leadership:
            lnode = nodes[leader]
            wnode = nodes[worker]
            lnode.children.append(wnode)
            wnode.parent = lnode
            
        """
        计算 count
        """
        def cal_count(root):
            for child in root.children:
                cal_count(child)
                root.count += child.count
            return
          
        """ 
        更新父项
        """
        def update_parents(node, coin):
            while node:
                node.coin += coin
                node = node.parent
        
        """
        获取查询结果
        """
        def get_res(node):
            res = node.coin
            node_count = node.count
            parent = node.parent
            while parent:
                res += parent.children_coin * node_count
                parent = parent.parent
            return res
        
        # 计算 count
        cal_count(nodes[1])
        
        res = []
        for op in operations:
            worker = op[1]
            if op[0] == 1:
                # 操作 1:个人发放
                nodes[worker].coin += op[2]
                update_parents(nodes[worker].parent, op[2]) # 更新它的所有父节点
            elif op[0] == 2:
                # 操作 2:团队发放
                all_coin = nodes[worker].count * op[2]
                # 当前节点加上数量
                nodes[worker].children_coin += op[2]
                nodes[worker].coin += all_coin
                # 更新父节点
                update_parents(nodes[worker].parent, all_coin)
            else:
                res.append((get_res(nodes[worker])) % (10**9 + 7))
        return res
10

平心而论,这次比赛的题都是比较常规的,没有偏题怪题。

第 1 题

送分题,直接两个数组按照相同下标比较是否相同。

第 2 题

也是送分题,数组从后往前计算分数值即可,每次计算之后互换分子和分母并约分。

第 3 题

第一眼看可能稍有难度,其实只要分析清楚题目,也不难。返回 true 的条件是机器人在没有碰到障碍物之前到终点,返回 false 的条件有两种,一是机器人尚未到终点就碰到障碍物,二是机器人肯定无法到达终点。关于 true 的判断很简单,只要在某一时刻机器人所在位置和终点坐标相等即可。关于 false 的判断相对复杂,以下分别说明。
返回 false 的第一种情况,机器人尚未到终点就碰到障碍物,可以通过 Map 将每个 xx 坐标映射到该 xx 坐标上的障碍物的 yy 坐标,加上泛型是 Map<Integer, List<Integer>>,机器人每走一步,可以得到 xx 坐标和 yy 坐标,通过 Map 得到该x坐标上的障碍物分别对应哪些 yy 坐标,如果当前 yy 坐标在该 List 中,则为碰到障碍物。
返回false的第二种情况其实很好判断,机器人只能向上或向右移动,如果机器人已经在终点的上方或右方(两者只要满足一个),就意味着机器人不可能到达终点。

第 4 题

个人认为是这次比赛最难的题。解法有多种,其中的一种解法是对格子进行染色然后计算二分图最大匹配,染色的方法是黑白交替染色,每张多米诺骨牌必定覆盖一个黑格和一个白格。计算二分图最大匹配的方法有多种,例如最大流或者匈牙利算法。

第 5 题

虽然是最后一题,但是个人认为难度不及第4题。这道题比较容易遇到的问题是超出时间限制,考虑到记录硬币数量的操作中对于每个人都要记录,不可节省时间,应该考虑在查询操作中节省时间,如果查询时只需要查询一个人,则可显著节省时间。为了做到查询时只需要查询一个人,需要记录每个人作为根节点的子树一共有多少个节点,例如一个节点有两个子节点且两个子节点都是叶子节点,则该节点作为根节点的子树一共有 33 个节点,显然当人数是n时,节点 11 作为根节点的子树就是整棵树,一共有 nn 个节点。
操作 1: 是只给一个人增加硬币数量,记录方法是从增加硬币的人开始,其所有父节点(指父节点、父节点的父节点等,以此类推直到根节点)的所有人都增加相应的硬币数量。
操作 2: 是给一个人及其手下的所有人增加硬币数量,记录方法是这个人以及这个人的所有父节点和所有子节点(即该节点作为根节点的子树中的所有节点)都要增加硬币,具体增加值为硬币数量乘以相应的节点的子树节点数。
操作 3: 直接通过查询对应的节点即可,此时每个节点记录的是每个人及其手下所有人拥有的硬币数量之和。

6

手速不行,水平不行,技不如人,甘拜下风

10

好想结识前3的大佬问一问他们学习的心得

3