积木题（2017年秋季——某网站的面试笔试题）积木题

51 阅读 0 评论 34 点赞

我是靠谱客的博主曾经大山，最近开发中收集的这篇文章主要介绍积木题（2017年秋季——某网站的面试笔试题）积木题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

积木题

（2017年秋季——某网站的面试笔试题）

最近参加某大公司的在线笔试，遇到的几个算法题，感觉挺有意思的，所以贴出来和大家分享交流一下，一下是我个人的求解，不足之处，请各位看官多多回复指教

搭积木
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 65536KB；其他语言 589824KB

题目描述

一天，小明买了许多积木回家，他想把这些积木拼接在一起。每块积木有两个接口，每个接口我们用一个数字标记，规定只有当两块积木有相同数字标记的接口时，这两块积木才可以通过该接口拼接在一起。举例，有两块积木，接口数字分别为1，2和3，4，那么这两块积木无法拼接；若两块积木接口数字分别为1，2和2，3，那么这两块积木可以通过由数字2标记的接口拼接在一起。现在小明知道所有积木的数量和每块积木接口的数字标记，你能告诉他他可以将所有积木拼接成一个整体么？

输入

第一行一个整数t，表示测试数组组数1≤t≤10；接下来在每组测试数据中：第一行一个整数n，表示积木的数量1≤n≤100000，下面n行每行2个整数x，y，表示强调内容其中一块积木的两个接口的数字标记；1≤x，y≤100000;

输出

对于每组测试数据，输出”YES”，表示该组数据中的所有积木可以拼接成一个整体，”NO”表示不行。（注意输出不包括引号）

样例输入

样例输出

NO
YES

Hint

在第一组测试数据中，有3块积木，显然前两块是可以拼接在一起的，但是第3块无论如何也无法和前两块拼接，所以输出NO；第二组数据中我们可以这样拼接：5-1-1-2-2-3-3-5-5-4-4-6，因此输出YES。

求解过程

个人思路，仅供参考
通过对题目的分析，本题采用链表求解比较方便快捷。时间复杂度低，效率高。

第一步
将第一个数插入到链表中

第二步
接下来输入的这个数，从链表头部开始遍历链表，按照顺序插入到链表中。如果链表中存在此值，则说明找到了可以连接在一块的积木。即将原来链表中的此节点删除。

第三步
当遍历完所有的积木之后，计算链表长度，如果等于2，则表示可以将所有的积木串在一起，输入YES. 否则输入NO

结束 ^-^

JAVA实现具体代码

public class MyClass {
public static class Node {
int value;
Node next;
public Node() {
}
public Node(int value) {
this.next = null;
this.value = value;
}
}
public static void main(String[] args) {
System.out.println("=============start=============");
int mGroupNum;
Scanner scanner = new Scanner(System.in);
ArrayList<Integer> ns = new ArrayList<>();
mGroupNum = Integer.valueOf(scanner.nextInt());
//组的个数
int[] size = new int[mGroupNum];
String[] result = new String[mGroupNum];
for (int i = 0; i < mGroupNum; i++) {
size[i] = Integer.valueOf(scanner.nextInt());
//第I组的大小
Node head = null;
//每行读取两个数,空格隔开
String[] line = new String[2];
scanner.nextLine();
int one = Integer.valueOf(scanner.nextInt());
int two = Integer.valueOf(scanner.nextInt());
head = new Node();
//头结点不存放数值
Node temp = new Node(one);
head.next = temp;
Node node = new Node(two);
if (two > temp.value) {
temp.next = node;
} else {
head.next = node;
node.next = temp;
}
//temp.next = new Node(two);
for (int j = 1; j < size[i]; j++) {
//循环读取输入的结点数
//每行读取两个数,空格隔开
scanner.nextLine();
one = Integer.valueOf(scanner.nextInt());
two = Integer.valueOf(scanner.nextInt());
int[] item = new int[2];
item[0] = one;
item[1] = two;
for (int p = 0; p < 2; p++) {
Node pNode = head;
//处理结点
while (pNode != null) {
if (pNode.next.value == item[p]) {
pNode.next = pNode.next.next; //删除
break;
} else if (pNode.next.value > item[p]) {
Node node1 = new Node(item[p]);
node1.next = pNode.next;
pNode.next = node1;
break;
} else {
if (pNode.next.next == null) {
pNode.next.next = new Node(item[p]);
//加到最后
break;
} else {
pNode = pNode.next;
//指针后移
}
}
}
}
}
//第i组结束，判断并输出结果
if (getListLength(head) == 2) {
result[i] = "YES";
} else {
result[i] = "NO";
}
}
scanner.close();
//关闭输入
//打印结果
printResult(result);
}
/**
* 计算链表长度
*/
public static int getListLength(Node head) {
int len = 0;
while (head.next != null) {
len++;
head = head.next;
}
return len;
}
/**
* 打印结果
*
* @param result
*/
public static void printResult(String[] result) {
for (int i = 0; i < result.length; i++) {
System.out.println(result[i]);
}
}
}