2022-9-25keep笔试第二题求解
题目描述：现有一个无向图，9个节点，分别编号1到9，m条边。任意两个节点只有0或者1条边，不存在自己到自己的边。然后有8个小球，用数字表示，且数字不重复，范围为1到9。将8个小球依次放在节点1到节点8上。问多少次操作，能让所有小球移动到对应数字的节点上。一次操作指将一个小球移动到相邻且没有小球的节点上。如果不能，则返回-1.
输入：[[1,2],[1,3],[1,9],[2,9],[3,9]], [3,9,2,4,5,6,7,8]
输出：5
解释：因为4，5，6，7，8五个球已经在对应数字的节点上，只需移动3，9，2。第一步，将2号球移动到9；第二步，将3号球移动到3；第三步，将9号球移动到1；第四步，将2号球移动到2；第五步，将9号球移动到9.
实在是没有头绪，求大佬给个思路。
贴一下自己的代码，感觉移动-1，0，1次的情况很好判断，所以只判断了这三种情况，过来34%.
public int solve (int[][] edges, int[] balls) {
// write code here
Set<Integer> st = new HashSet<>();
for (int i = 1; i < 10; i++) {
st.add(i);
}
for (int i = 0; i < edges.length; i++) {
if(st.contains(edges[i][0])) st.remove(edges[i][0]);
if(st.contains(edges[i][1])) st.remove(edges[i][1]);
}
int cnt = 0;
for (int i = 0; i < balls.length; i++) {
if(balls[i] != i+1) {
cnt++;
if(st.contains(i+1)) {
cnt = -1;
break;
}
}
}
return cnt;
} 
大疆公司氛围 168人发布