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

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

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