amplitude 面试题目

不知道怎么做，一开始想用backtrack，但是感觉很麻烦，求高人见解！ 题目放在图片里了

你只需要算，每个颜色是多少个ends，然后最多允许2个是单数…
easy问题…

补充内容 (2022-03-21 08:18 +08:00):
不对… 想当然了… 算颜色的话，一个棍子两头不能连在一起… 你容我想想

补充内容 (2022-03-21 08:23 +08:00):
看起来又像我搞了半年没搞明白的二分法的题… 但是这里的特殊例子只有 棍子两头一个颜色该如何处理… 那就按照颜色分开，map<color, map<sticksId, count>>
这样的话，对于每个颜色先看是否是good，最多只允许2个颜色不是good… good的定义就是 颜色内部可以连在一起

ND0406 发表于 2022-03-20 17:17:06
你只需要算，每个颜色是多少个ends，然后最多允许2个是单数…
easy问题…

请问可以具体一些嘛，比如大致的code该怎么写？谢谢！

如图求解！感激不尽！提供一个思路就行，加米加米！

看着像是backtracking，提前把不同颜色代表的tuple的count存起来

有点Hamiltonian graph那味儿了。

我认为是用dfs里permutation的思路，用一个helper function来检查match就行

貌似input可以理解为一个邻接图，好像直接BFS就行了？
用一个set存visited node，新的node加到queue里的条件是没出现在visited里面过