华为上机题3——词语接龙（深搜java版本）
今天华为去机试，有3题，前两题比较简单所以就不记下来了，第三题其实也是可以的，不过可能是太久没有刷题，没有反应过来，思考了半天应该用那种数据结构去存它之类的。还有一些诸如nullpointererror这样的错误还一直出现，最后时间不够只完成了一半，估计悲剧了~~~不过不要紧，最主要是要总结一下，所以回来把它给完成了。。。编码编得还真不快，而且总觉得我写算法相关的代码不太爱调用函数，这种习惯不太好。。。看来自己还是多刷题去吧。。。≡(▔﹏▔)≡题意大概如下：输入两个或多个字符串（长度为4），用" "空格分开每一个字符串，保证在排列一定顺序后，前一个字符串的末尾字符是下一个字符串的首字符。分3种情况输出，我还是距离比较快一点：
输入：
第一种：ABCD FIIG DIIF
输出：ABCD DIIF FIIG
第二种：ABCD FIIA DIIF
输出：circle（因为这些字符串可以连成一个环）
第三种：ABCD HIII DIIF
输出：error （因为这些字符串连不了一条线上了）
算法：深度优先搜索策略（一开始还往着字典树的方向去想了。。。因为刚好最近有在看，但实际上直接深搜就可以了），如从ABCD开始搜，一直搜寻它下面第一个符合的字符串b，符合以后从这个字符串b继续开始往下搜，比起基于stack的深搜DFS我比较熟悉基于递归的深搜DFS，不过还是特地回来写了一写用stack的写法。。。
源码：
package com.java.study;
import java.util.Scanner;
import java.util.Stack;
class Node{
String str;
boolean visited;
}
public> public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String [] arr = sc.nextLine().trim().split(" ");
int len = arr.length;
Node[] node = new Node;
for(int i = 0 ; i < node.length;i++){
node = new Node();
node.str = arr;
node.visited = false;
}
StringBuffer sb = new StringBuffer();
String temp = null;
Stack<Node> stack = new Stack<Node>();
node.visited = true;
stack.push(node);
int count = 1;
int index = -1;
while(!stack.isEmpty()){
temp = stack.peek().str;
// System.out.println(temp+" "+count);
sb.append(temp+" ");
for(int i = 1 ; i < len;i++){
index = -1;
//如果当前节点没有被访问过而且它的首字母和前一个字串的尾字母一样的话
if(!node.visited && (temp.charAt(3)==node.str.charAt(0))){
count++;
index = i;
break;
}
}
stack.pop();//跳出循环表示已经访问过这个节点
if(index!=-1){//index!=1表示已经有一个节点符合要求
node.visited = true;
stack.push(node);
}
}
//count==len 表示所有的字串都访问过
if(count==len){
if(temp.charAt(3)==node.str.charAt(0))
System.out.println("circle");
else
System.out.println(sb.toString().trim());
}else{
System.out.println("error");
}
}
}
页:
[1]