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。