阿里巴巴3月6日机试题

一共如下两道编程题,考场上时间只来得及动手写了第一题的代码,而且最后还是没有过。思路正确性也没法保证,还希望大佬多来指点,提前感谢

1. 一共有三种编号分别为1,2,3且数量不限的卡片。放入N*3的表格中,每一个格子只能放入一张卡片,并且要求相邻的上下左右的方格不能放入同一种数字的卡片,求有多少种可能的方案?
思路:一开始随手写了个DFS,直接超时。花了一点时间才在排列组合这个方向上想到一点思路。首先可以知道每一行其实只有两种不同的方法,即只有两种卡片(比如1,2,1)或者三种卡片(1,2,3)。一旦一行确定是只有两种卡片或者三种卡片,那么其下一行的数量是确定了的。假设当前这一行是只含有两种卡片的,那么下一行如果也只含有两种卡片,则有3种可能;如果下一行含有3种卡片,则有2种可能。那么当当前行含有三种卡片时,也可以这么分类得到下一行有4种可能(三种卡片和仅两种卡片各占2种可能)。
得到这个思路后,首先我们可以算出N行全为仅含两种卡片和全都是三种卡片的可能性。然后再计算N行中有M行为三种卡片的可能。这个思路直觉上是符合时间复杂度的,但是可惜考场上没时间验证了。

2. 有一个地铁网,并且每一条地铁都是环线。即假设一条线路为[1, 3, 5, 7],那么地铁的路线就是13571357...循环下去。如果两条线路有站台重合,就可以换乘,比如两条线路分别为[1, 3, 5, 7]和[2, 4, 5, 6],那么就可以在站台5进行换乘。一共有n条线路,小明想从s站到到t站台,求出最少需要乘坐几趟地铁才能到达,如果不能到达则输出-1。
这道题考场上没时间看懂题,暂时还没思路。还希望有大佬指导指导,再次提前感谢。

最后祈祷一下面试机会。千万不要因为笔试零分连面试机会都没有了😂😂😂



#阿里巴巴##笔试题目#
全部评论
这2个题 都acm原题吧。 以前训练赛都写过。。
6 回复
分享
发布于 2021-03-07 01:02
力扣1411, 力扣815
4 回复
分享
发布于 2021-03-06 23:25
小红书
校招火热招聘中
官网直投
第一题实际上可以抽象成一个数学问题,具体可以看我博客https://blog.csdn.net/weixin_43905212/article/details/114454963?spm=1001.2014.3001.5501 没做出来应该也能进入面试的,不用着急,后面好好表现就行了。
3 回复
分享
发布于 2021-03-06 21:03
第一题成功用矩阵快速幂写出来了,因为半年多没碰过c++,忘记有long long这回事,导致结果溢出,机试结束才发现搞得我想杀了我自己。
2 回复
分享
发布于 2021-03-06 20:53
同零分出圈
1 回复
分享
发布于 2021-03-06 20:45
第一题有测试用例吗
1 回复
分享
发布于 2021-03-06 20:52
同零分暴力超时 被带走了(
1 回复
分享
发布于 2021-03-06 21:36
第二题的话是不是可以先建图,然后跑优先队列优化的Dijkstra。。。。
1 回复
分享
发布于 2021-03-06 22:32
我0通过率,阿里笔试一小时游😭
1 回复
分享
发布于 2021-03-06 23:34
第一题其实发现规律很好写,贴一个代码。ABA行的排列最终可以得到3个ABA和两个ABC型的,而ABC型的排列最终可以得到2个ABA和两个ABC型的,每次保存上一次ABA和ABC型的数量,O(n)时间内就可以得到答案。
1 回复
分享
发布于 2021-03-07 00:54
记录的太详细了🤣就这感觉能做出来一道就稳了……
点赞 回复
分享
发布于 2021-03-06 20:41
同0分
点赞 回复
分享
发布于 2021-03-06 20:51
零分也带走了我
点赞 回复
分享
发布于 2021-03-06 20:51
牛客题霸可以多刷刷
点赞 回复
分享
发布于 2021-03-06 22:37
我交了白卷
点赞 回复
分享
发布于 2021-03-07 00:15
0通过率一轮游,告辞
点赞 回复
分享
发布于 2021-03-07 05:52
一个dp or 数学题,一个最短路
点赞 回复
分享
发布于 2021-03-07 08:04
你们考多久?
点赞 回复
分享
发布于 2021-03-07 08:14
已经很强了
点赞 回复
分享
发布于 2021-03-07 09:31
这里可是阿里😅
点赞 回复
分享
发布于 2021-03-07 11:01

相关推荐

16 89 评论
分享
牛客网
牛客企业服务