首页 > 技术交流 > 阿里巴巴3月6日机试题

阿里巴巴3月6日机试题 内部员工回复

头像
臣巳水
编辑于 2021-03-07 17:58:22 APP内打开
赞 16 | 收藏 92 | 回复29 | 浏览6461
一共如下两道编程题,考场上时间只来得及动手写了第一题的代码,而且最后还是没有过。思路正确性也没法保证,还希望大佬多来指点,提前感谢

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。
这道题考场上没时间看懂题,暂时还没思路。还希望有大佬指导指导,再次提前感谢。

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



29条回帖

回帖
加载中...
话题 回帖

推荐话题

相关热帖

技术交流近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐