2019 力扣杯全国秋季编程大赛 算是我大学以来第一次参加的算法编程比赛。由于并没有接触过算法竞赛方面的知识，总体感觉是五道题难度跨越特别大，前三题花了不到半个小时，后面的时间几乎都用在最后一题上。
题解 1. 猜数字
小A 和 小B 在玩猜数字。小B 每次从 1, 2, 3 中随机选择一个，小A 每次也从 1, 2, 3 中选择一个猜。他们一共进行三次这个游戏，请返回 小A 猜对了几次？
输入的guess数组为 小A 每次的猜测，answer数组为 小B 每次的选择。guess和answer的长度都等于3。
送分题，代码如下：
1 2 3 4 5 6 7 8 9 class Solution { public int game (int [] guess, int [] answer) { int res = 0 ; for (int i = 0 ; i < 3 ; i++) if (guess[i] == answer[i]) res++; return res; } }
2. 分式化简
化简如下分式：
$$
输入的cont代表连分数的系数（cont[0]代表上式的a0，以此类推）。返回一个长度为2的数组[n, m]，使得连分数的值等于n / m，且n, m最大公约数为1。
模拟题，从最里面的分式开始计算，题目中说明了cont[i] >= 0，因此不用考虑负数情况（当时在比赛时没有注意这一点，因此为考虑负数多花了些时间），最后分子分母同时除以最大公因数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution { private int gcd (int a, int b) { return b = = 0 ? a : gcd(b, a % b); } public int [] fraction(int [] cont) { int up = 1 , down = cont[cont.length - 1 ]; for (int i = cont.length - 2 ; i >= 0 ; i--) { int a = cont[i]; up += a * down; int tmp = up; up = down; down = tmp; } int gcd = gcd(up, down); return new int []{down / gcd, up / gcd}; } }
3. 机器人大冒险
力扣团队买了一个可编程机器人，机器人初始位置在原点(0, 0)。小伙伴事先给机器人输入一串指令command，机器人就会无限循环这条指令的步骤进行移动。指令有两种：
U: 向y轴正方向移动一格
R: 向x轴正方向移动一格。
不幸的是，在 xy 平面上还有一些障碍物，他们的坐标用obstacles表示。机器人一旦碰到障碍物就会被损毁。
给定终点坐标(x, y)，返回机器人能否完好地到达终点。如果能，返回true；否则返回false。
模拟题，机器人若能走到终点，那么需要的指令数一定恰好等于 x+y，模拟 x+y 次后判断是否处于终点位置，如果中途遇到障碍或者走出 (x, y) 范围则提前结束。
一开始将所有障碍坐标保存在 Map 中，用于加速判断当前坐标是否处在障碍上。
比赛中的一次罚时是因为最后直接 return true 没有判断是否位于终点… 做简单题也一定要细心不能大意。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public boolean robot (String command, int [][] obstacles, int x, int y) { Map<Integer, Set<Integer>> obsMap = new HashMap <>(); for (int i = 0 ; i < obstacles.length; i++) { int x1 = obstacles[i][0 ]; int y1 = obstacles[i][1 ]; if (!obsMap.containsKey(x1)) { obsMap.put(x1, new HashSet <>()); } obsMap.get(x1).add(y1); } int curX = 0 , curY = 0 ; for (int i = 1 ; i <= x + y; i++) { char step = command.charAt((i - 1 ) % command.length()); if (step == 'U' ) curY += 1 ; else curX += 1 ; if (obsMap.containsKey(curX) && obsMap.get(curX).contains(curY)) return false ; if (curX > x || curY > y) return false ; } return curX = = x && curY == y; } }
4. 覆盖
你有一块棋盘，棋盘上有一些格子已经坏掉了。你还有无穷块大小为1 * 2的多米诺骨牌，你想把这些骨牌不重叠 地覆盖在完好 的格子上，请找出你最多能在棋盘上放多少块骨牌？这些骨牌可以横着或者竖着放。
输入：n, m代表棋盘的大小；broken是一个b * 2的二维数组，其中每个元素代表棋盘上每一个坏掉的格子的位置。
输出：一个整数，代表最多能在棋盘上放的骨牌数。
限制：
1 <= n <= 8
1 <= m <= 8
0 <= b <= n * m
这题在比赛时并没有什么思路，后来看题解可以用状态压缩DP或者二分图匹配来做，二分图匹配的方法很巧妙，之后有空会把代码补上。
5. 发 LeetCoin 题目描述很长，可以看此链接 。
大意是说有一棵树（不一定是二叉树），树上的每个节点代表一个员工，树的层次就代表上下属关系。现在可以进行三种操作：
给某个节点（员工）发一定数量硬币。
给某棵子树的所有节点都发一定数量硬币。
查询某棵子树所有节点的硬币之和。
程序需要尽可能高效地完成这三种操作。
在执行具体操作前，我建立的数据结构包括：
all 数组：来记录每个节点的硬币数，初始均为0father 数组：记录每个节点的父节点编号（类似并查集中的数组）sons Map：记录每个节点的所有直接子节点集合totalSons 数组：记录以每个节点为根的子树一共有多少节点。这里会用 countSons() 函数递归计算。
当执行操作1时，步骤如下：
将 all 中对应节点硬币数增加；
在 all 数组中依次更新当前节点父节点的硬币数，直到到达根节点，这里会用到 father 数组。
当执行操作2时，步骤如下：
使用 update() 函数递归更新当前节点子树中所有节点硬币数，在更新时，使用 totalSons 数组可以直接计算出当前节点硬币数应该增加多少。
与操作1类似，依次更新父节点硬币数，不过这里更新时增加的值（addFatherCoin）与1中有所不同。
具体实现代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 class Solution { private int countSons (int k, Map<Integer, Set<Integer>> sons) { if (!sons.containsKey(k) || sons.get(k) == null || sons.get(k).isEmpty()) return 0 ; Set<Integer> sonSet = sons.get(k); int res = sonSet.size(); for (Integer son : sonSet) { res += countSons(son, sons); } return res; } private void update (int num, int coin, int [] totalSons, int [] all, Map<Integer, Set<Integer>> sons) { all[num] = (all[num] + coin) % 1000000007 ; if (totalSons[num] == 0 ) return ; all[num] = (all[num] + totalSons[num] * coin % 1000000007 ); for (int son : sons.get(num)) { update(son, coin, totalSons, all, sons); } } public int [] bonus(int n, int [][] leadership, int [][] operations) { int [] all = new int [n + 1 ]; int [] father = new int [n + 1 ]; Map<Integer, Set<Integer>> sons = new HashMap <>(); father[1 ] = -1 ; for (int i = 0 ; i < leadership.length; i++) { int a = leadership[i][0 ]; int b = leadership[i][1 ]; father[b] = a; if (!sons.containsKey(a)) sons.put(a, new HashSet <>()); sons.get(a).add(b); } int [] totalSons = new int [n + 1 ]; for (int i = 0 ; i < n; i++) { totalSons[i + 1 ] = countSons(i + 1 , sons); } List<Integer> res = new ArrayList <>(); for (int i = 0 ; i < operations.length; i++) { int op = operations[i][0 ]; int num = operations[i][1 ]; if (op == 1 ) { int coin = operations[i][2 ]; all[num] = (all[num] + coin) % 1000000007 ; int cur = father[num]; while (cur != -1 ) { all[cur] = (all[cur] + coin) % 1000000007 ; cur = father[cur]; } } else if (op == 2 ) { int coin = operations[i][2 ]; update(num, coin, totalSons, all, sons); int addFatherCoin = coin * (totalSons[num] + 1 ) % 1000000007 ; int cur = father[num]; while (cur != -1 ) { all[cur] = (all[cur] + addFatherCoin) % 1000000007 ; cur = father[cur]; } } else { res.add(all[num]); } } int [] resArr = new int [res.size()]; for (int i = 0 ; i < res.size(); i++) resArr[i] = res.get(i); return resArr; } }
后续 可能由于这次是 LeetCode 第一次举办的全国大赛所以大佬们并没有关注的原因，我最后竟然正好是第50名（能拿到奖品的最后一名） 。
第 1 名选手获得《计算机程序设计艺术》卷 1 - 卷 4A ；第 2-5 名选手，优先随机挑选以下图书，第 6-50 再做选择，数量有限，先选先得，图书包含：《程序员面试金典 · 第六版》、《算法 4》、《挑战程序设计 2》、《Python 深度学习》、《C++ Primer中文版（第5版）》、《Python机器学习手册：从数据预处理到深度学习》、《Effective C++：改善程序与设计的55个具体做法（第三版）》、《Python编程之美：最佳实践指南》、《Code：隐匿在计算机软硬件背后的语言（英文版）》。
虽然只剩下最后两本书可以选了，不过还是挺开心的。选了一本《程序员面试金典》，很快就收到了书，厚厚的一大本，之后找工作的时候有东西看了~
