参加2020Jam初赛记录与部分题目解答

╰+攻爆jí腚メ 2023-07-24 14:39 8阅读 0赞

Google Jam大赛是谷歌举办的一年一届的在线答算法题的的比赛。初赛比赛时长27小时，一共有5道算法题，总分100分，获得分数30分和以上者，就能晋级下一轮比赛。在这27小时内，选手可以多次进入jam的比赛链接，查看题目和提交代码，每道题可以提交多次。提交后，页面会实时反馈代码运行测试用例结果（通过/未通过），不过不会展示测试结果集。参加Jam的选手，进入前一千名有T恤发放；前三名奖励现金，一般参加人数达数万人，基本没有拿奖的可能了。我在赛事开始前看到了GDG公众号关于JAM的赛事信息推送，于是抱着闲着也是闲着，不如试试水的心态报名参加2020年的Jam。

我大约花了5-6小时，只做对两题，拿到27分，不能进入下一轮比赛了。虽然结果并不好，不过那天过的十分充实，让我感到很愉快，以后一定多多参加类似的算法大赛，愉快自己。下面介绍一下这三道题和我的解题思路，原题目和我的代码会放到github上，[github地址][github]。

**第一题 矩阵计算(7分)**

题目意思是，给定n个int类型矩阵，计算每个矩阵对角线的和（左上角到右下角），并计算矩阵中存在重复数的行数和列数，例如：

*输入*

3
    4
    1 2 3 4
    2 1 4 3
    3 4 1 2
    4 3 2 1
    4
    2 2 2 2
    2 3 2 3
    2 2 2 3
    2 2 2 2
    3
    2 1 3
    1 3 2
    1 2 3

*输出*

Case #1: 4 0 0
    Case #2: 9 4 4
    Case #3: 8 0 2

`4 0 0`代表第一个矩阵的对角线上的数之和是4，存在重复数字的行数是0，存在重复数字的列数是0。

**解题思路**

这题的不难，只要把数据接收存储就可以了。我是用一个二维数组的list来存矩阵数据，根据二维数组的下标就能算出题目的答案了。

**第二题 字符串的处理**

给定一串纯数字的字符串，在每个字符串左右加上数量相同的左右括号，括号的深度和数字相同，如`((2))`多个数字之间的括号可以合并，如`((2(3)))`。给出一个字符串，求出符合条件的加括号的字符串中长度最短的字符串。如`0((2)1), (((3))1(2)), ((((4)))), ((2))((2))(1)`都是符合条件的字符串，但是第四个不是最短的，因为`((22)1)`更短，案例：

*输入*

4
    0000
    101
    111000
    1

*输出*

Case #1: 0000
    Case #2: (1)0(1)
    Case #3: (111)000
    Case #4: (1)

**解题思路**

这道题我的解题思路是，把字符串分一个数字数组，从第一个数字开始，添加`()`形成字符串，再把下一个数字加入进来，继续处理新的`()`，用例子说明容易理解一点。比如对应字符串`312`，处理逻辑分3步。

*  第一步：把`3`处理括号得到`(((3)))`
 *  第二步：把`(((3)))`加入第二个数`1`得到`(((3))1)`
 *  第三步：把`(((3))1)`加入第三个数`2`得到`(((3))1(2))`

这个加新数得到最短长度的深度括号的字符串的逻辑是这样的，如`AB`数加`C`，分`B<C`, `B==C`, `B>C`三种情况处理括号。

*  `B < C`: `B`右侧的`C`个`)`移动到`C`的右侧。如`((2))`加新数字`1`后为，将`2`右侧的`1`个`)`移动到`1`的右侧，得到`((2)1)`。
 *  `B == C`: `B`右侧所有的`)`都移动到`C`的右侧。如`((2))`加新数字`1`后为`((22))`。
 *  `B < C`: `B`右侧的`)`全部删除，添加`C - B`个`(`，`C`右侧添加`C`个`)`。如`((2))`加新数字`3`的步骤，1. 删除`2`右边的`)`，得`((23`；2. `2`右边添加`3 - 2`个`(`，的`((2(3`；3. `3`右侧添加`3`次个`)`，得`((2(3)))`。

不断加新数并按上面的逻辑的到新字符串，直到所有的数字都添加完，就得到最终的最短的字符串。

**第三题 安排活动**

给定一列活动的时间段，把这些计划分配给C和J两个人去完成，但是一个人不能同时完成拥有时间冲突的两项活动。如有三个活动18:00 - 20:00, 19:00 - 21:00 和 22:00 - 23:00，一种安排方式是C去完成18:00 - 20:00这个活动，J去完成19:00 - 21:00 和 22:00 - 23:00这两个活动。当然，C去完成19:00 - 21:00 和 22:00 - 23:00，J去完成18:00 - 20:00也是可以的。如果有三个活动的时间段互相冲突，则这些活动就无法被分配，如18:00 - 20:00, 19:00 - 21:00，19:00 - 22:00。

可以安排的活动列表，输出活动由C和J的一种执行顺序；如果活动列表不能分配，输出`IMPOSSIBLE`。

*输入*

4
    3
    360 480
    420 540
    600 660
    3
    0 1440
    1 3
    2 4
    5
    99 150
    1 100
    100 301
    2 5
    150 250
    2
    0 720
    720 1440

*输出*

Case #1: CJC
    Case #2: IMPOSSIBLE
    Case #3: JCCJJ
    Case #4: CC

**解题思路**

这题我没有做对，思路错误。

我的思路是，设为A和B两个list，把活动一个一个往里面添加，如果该活动在A中存在一个冲突的活动，就把离不冲突的最近的那个活动放在队列A；另一个放在B，如果队列B也存在一个冲突的，就把A中冲突的放在B中，如果继续存在冲突，则认为无法安排。

正确思路可能是，每进一个新的活动，判断是否A，B列表是否都存在与之冲突的活动，都不存在则插入队列A；如果A存在，B不存在则插入队列B；如果A，B中都存在冲突的活动，将这些冲突的活动都拿出来比较，查看它们之间是否互相冲突，如果冲突则说明活动无法安排；如果不冲突，则把这些活动放到队列B中（如果B中有冲突，放入A，把A冲突翻入B，直到没有冲突），把插入的活动放到A。

[github]: https://github.com/programluo/google-jam-2020