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