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

image.png

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

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

展开讨论

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

第 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
展开全部 23 讨论