阿里笔试 20210306

因为电脑有问题，所以没参加这一次笔试，不过还是补一下题以备下次
耗时 58 分钟（不过真正笔试可能会更紧张，而且实际题目可能更难以理解）

具体题目啥样不确定，不过网上有人给出了大概的题意，可以近似猜出来题目内容

作者：瑶瑶135755
链接：https://www.nowcoder.com/discuss/607423?type=2&order=3&pos=7&page=1&channel=-1&source_id=discuss_tag_nctrack
来源：牛客网

不讲武德，两道hard
第一题：声哥，何人听我楚声狂，他现在有3种数字卡片，卡片上的数字分别为1，2，3，，他想将这些数字放入N3的方格中，方格上下左右的格子不允许有重复的数字。请问有几种方法？
输入格式：先输入n，代表一共有n组数，然后输入n行的m，代表m3.（群友提示我，1411好像是原题，cao。
https://leetcode-cn.com/problems/number-of-ways-to-paint-n-3-grid/

第二题声哥，何人听我楚声狂想找一条最短回学校的路线，他回了哈尔冰，现在哈尔冰有一个地铁交通网，巴拉巴了，力扣815改编， https://leetcode-cn.com/problems/bus-routes/，815是给你数组，起始位置和终点位置
但是他的输入格式是，先输入n，代表一共有n组数，然后输出m,s,t 其中s和t代表起始位置和终点位置。m代表一共有m个地铁航班。接下来再输入m*2行，第一行是一个数字k，代表有k个停靠站点，第二行才是所有停靠站点。加了一点难度就是如何把他给你的航班输入到力扣那个数组中，反正我是菜鸡，都不会。

作者：臣巳水
链接：https://www.nowcoder.com/discuss/607438?type=2&order=3&pos=6&page=1&channel=-1&source_id=discuss_tag_nctrack
来源：牛客网

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

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

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

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

第一题

大概意思是给定三种卡片，让他们填充 $3 \times N$ 的方块，要求上下左右类型不同，求方案数

是 LeetCode 1411.给 N x 3 网格图涂色的方案数

这题实际上是个找规律题目，我们假定三种卡片是 1 2 3

那么对于 $1 \times 3$ 的范围，有如下 12 种可能：


1 2 1	1 2 3	1 3 1	1 3 2
2 1 2	2 1 3	2 3 1	2 3 2
3 1 2	3 1 3	3 2 1	3 2 3

然后我们需要考虑不同的数字后面可以如何往后续

比如，第一列是 1 2 1，那么第二列的第一、三行就不能是 1、第二行不能是 2，共有 5 种可能；而相应的 1 2 3，对应 4 种可能。

由于 1 2 3 本身是等价的，那么我们可以将一列分成两种类型：使用两个数字的（如 1 2 1）和使用三个数字的（如 1 2 3）

可以看出，第一列共有 6 个两个数字，6 个三个数字
而所有两个数字可以往后续 3 个两个数字和 2 个三个数字
所有三个数字可以往后续 2 个两个数字和 2 个三个数字

那么问题就解决了，可以设定一个函数get(N)，返回N对应的两个数字和三个数字的个数
其内部实现为：
获取get(N-1)的结果a2、a3，然后得到r2=a2*3+a3*2、r3=a2*2+a3*2，返回r2、r3即可

最后的结果就是得到的两个结果相加

（有一说一，这道题虽然是困难，但是并不是特别难，应该把 $N=1$ 的 12 种情况画出来，尝试下第二列基本上就能看出来规律）

const m = 1e9 + 7

func numOfWays(n int) int {
    a, b := do(n)
    return (a+b)%m
}

func do(n int) (r2 int, r3 int) {
	if n == 0 {
		r2 = 0
		r3 = 0
		return
	}
	if n == 1 {
		r2 = 6
		r3 = 6
		return
	}

	n2, n3 := do(n - 1)
	r2 = ((n2*3)%m + (n3*2)%m)%m
	r3 = ((n2*2)%m + (n3*2)%m)%m
	return
}

第二题

大概意思是，有在一个城市中有很多条地铁线路，每个线路对应多个站点。部分站点可能属于多个线路，为换乘站。
求从出发点到目的地最多需要坐多少次地铁

题目是魔改的 LeetCode 815.公交线路

按照帖子里说的，这道题除了输入方式外，应该和 Leetcode 差不多。虽然没特别看懂他们的解释，不过猜测应该是类似 ACM 那种先输入数据组数 $n$ ，然后每一组数据包括 $m$ 、 $s$ 、 $t$ 。下面 $2 \times m$ 行，第一行是一个站点数 $k$ ，第二行对应 $k$ 的站点序号
唔，虽然几年没写 ACM 题了，不过处理起来不算特别复杂，还是能接受的

大概思路其实也不算太复杂（就是实现起来烦人）
原理上，我们可以将每一条线路缩成一个点，这个点可能和多个线路联通，然后做一个 BFS 即可（要是地铁带费用，就得用 Dijkstra，感觉更“困难”（突然想起来 Go 没优先队列的模板））

虽然是这么个思路，不过自己实现的时候没有用上面的方案，而是对每个站点做了个 map，可以查询每个站点属于那几个线路（如果只对应一个线路，那么后面就不需要考虑他了，除非他就是终点，不然没用）
然后 BFS 从起点开始遍历，每次取队首的站点，看它属于哪几条线路，每条线路对应哪几个点，将其中还未遍历过的站点加入队列

为了避免队伍太庞大，并且尽早获得结果，所有判断是否访问过和判断是否已到达重点，写在了当前节点的下一个节点的遍历中间（按照之前的习惯基本上都是在取出当前节点才判断的）
不过这么优化在 LeetCode 会超时，还需要考虑几种特殊情况

起点就是终点
起点和终点在同一条线路
起点和终点不连通

前两个都很好判断，第三个使用并查集即可

PS: 严格上来说，应该还能再优化优化。执行速度在 LeetCode 排名并不高。不过还有“最后 5 min”的时候，实在来不及想别的办法了，只能赶快写了个并查集把 $-1$ 给优化了

import (
	"container/list"
)

type Obj struct {
	Station int
	Dis     int
}

func getF(x int, f map[int]int) int {
	_, exist := f[x]
	if !exist {
		f[x] = x
	}
	if x == f[x] {
		return x
	}
	f[x] = getF(f[x], f)
	return f[x]
}

func numBusesToDestination(routes [][]int, source int, target int) int {
	if source == target {
		return 0
	}

	f := make(map[int]int)

	connect := func(x, y int) {
		xx := getF(x, f)
		yy := getF(y, f)
		f[xx] = yy
	}

	// 每个站点对应的线路列表
	m := make(map[int][]int)
	for idx, route := range routes {
		hasSource := false
		hasTarget := false
		pre := -1
		for _, s := range route {
			if s == source {
				hasSource = true
			}
			if s == target {
				hasTarget = true
			}

			if pre != -1 {
				connect(pre, s)
			}
			pre = s

			_, exist := m[s]
			if exist {
				m[s] = append(m[s], idx)
			} else {
				m[s] = []int{idx}
			}
		}
		if hasSource && hasTarget {
			return 1
		}
	}

	if getF(source, f) != getF(target, f) {
		return -1
	}

	vis := make(map[int]struct{})
	q := list.New()
	q.PushBack(Obj{
		Station: source,
		Dis:     0,
	})

	for k, v := range m {
		if len(v) <= 1 {
			// 站点无法到达其他线路，可以直接忽略
			vis[k] = struct{}{}
		}
	}

	for q.Len() != 0 {
		head := q.Front()
		q.Remove(head)

		obj := head.Value.(Obj)
		t := obj.Station
		d := obj.Dis

		// 当前点未到达过
		// 检查所有可以从这个点前往的点
		for _, rid := range m[t] {
			// 当前点所在的所有线路
			for _, s := range routes[rid] {
				// 线路所有站点
				if s == target {
					return d + 1
				}

				_, visited := vis[s]
				if !visited {
					q.PushBack(Obj{
						Station: s,
						Dis:     d + 1,
					})
					vis[s] = struct{}{}
				}
			}
		}
	}
	return -1
}