Java 实习生面试题 - Hexor Chang
Java 实习生面试题
2012-02-28 11:33
Hexor Chang
阅读(1245)
评论(0)
编辑
收藏
举报
面试题之一 将类似于书籍目录的数组中的元素提取, 籍目录的数组中的元素提取, 并加入一个map结构中
题目要求:
如右图所示, 设目录的每一行都是一个String数组的一个元素,
缩进次数代表了这个元素所具有的空格个数.
要求实现的功能为生成一个map并输出,
map的key为子章节的名称,
value为父章节的名称,
如若没有父章节那么value = “null”
举例:
<“1 Introduction”,”null”>
<“1.1 Backgroud”,”1 Introduction”>
<“1.2 Audience”,”1 Introduction”>
…
…
…
思路:
看到这道题我的最直观的反映是使用树, 将整个数组建立成一个树, 最后返回所有的父节点-子节点对做为KV值. 虽然是一种解法, 但是整个过程过于复杂.
后来从面试官出得到的解法是用栈来实现. 由于自己本身的代码量较少, 也没有在实际中应用过栈来解决具体问题, 所以这个方法自己是没有想到的.
从这道题的思路来看, 对于栈的使用时机, 最好是有固定的一种节奏来出现一个个的元素, 并且元素有共同点, 再者就是有个能作为flag数字标记的值, 在本例中这个值就是每个元素前的空格个数了.
希望在以后的工作中积累更多使用栈来解决具体问题的经验.
具体实现:
主函数:
- 1 import java.util.HashMap;
2 import java.util.Map;
3 import java.util.Stack;
4
5 import org.xml.sax.HandlerBase;
6
7 /**
8 * @author hexor
9 *
10 * 面试题之一 将类似于书籍目录的数组中的元素提取, 并加入一个map结构中
11 *
12 * 例如:
13 * {"A"," Aa"," Aa1"," Ab","B"," Ba"," Ba1"," Ba2",
14 * "C"}
15 *
16 * 要求这样的Map: ("A","null") (" Aa","A") (" Aa1"," Aa")
17 * (" Ab","A") . . .
18 *
19 * 即: Map的key为子章节的名称, value为父章节的名称, 若没有父章节, 则value为"null"
20 *
21 * 已知规律: 数组元素前面的空格的数量
22 *
23 * 注意: 数组元素中的内容是没有规律的, 并没有第一个字母是大写ABC.., 第二个字母是 小写,
24 * 第三个是数字的规律,只有空格个数是有规律的
25 *
26 *
27 */
28 public class Test {
29
30 public static <E> void main(String[] args) {
31
32 // 给出的数组
33 String[] array = new String[] { "A", " Aa", " Aa1",
34 " Ab", "B", " Ba", " Ba1", " Ba2", "C" };
35
36 Test test = new Test();
37 MyStack stack = new MyStack(); // 用到的一个自定义的栈
38 Map<String, String> map = new HashMap<String, String>(); // 需要求得的map
39
40 for (int i = 0; i < array.length; i++) { // 遍历每个元素,并进行操作
41
42 int itemSpace = 0; // 每个元素拥有的空格数
43 itemSpace = test.getSpacesAmount(array[i]); // 获得这个元素的空格数
44
45 /*
46 * 栈为空,说明没有父章节;或者到达新的顶层章节,则清空栈
47 */
48 if (stack.isEmpty() || itemSpace == 0) {
49 map.put(array[i], "Null");
50 stack.clear();
51 stack.push(array[i]);
52 System.out.println(array[i] + "-Null");
53 continue;
54 }
55
56 /*
57 * 根据这个元素的空格数,与栈中元素比较, 并对栈进行操作 再将元素去掉前置空格后加入map,并输出
58 */
59 test.stackOperation(stack, itemSpace);
60 map.put(array[i].trim(), stack.peek().trim());
61 System.out.println(array[i].trim() + "-"
62 + stack.peek().trim());
63 stack.push(array[i]);
64
65 }
66
67 }
68
69 public int getSpacesAmount(String string) { // 求元素的空格个数
70 return string.lastIndexOf(" ") + 1;
71 }
72
73 public void stackOperation(MyStack stack,
74 int incomeSpacesAmount) {
75
76 int popTimes = stack.getPeekSpaceAmount()
77 - incomeSpacesAmount + 1;
78 for (int i = 0; i < popTimes; i++) {
79 stack.pop();
80 }
81 }
82 }
自定义栈:
- 1 import java.util.Stack;
2
3
4 public class MyStack extends Stack<String>{
5
6 /**
7 * 自定义能获得栈顶元素空格数的栈
8 */
9 private static final long serialVersionUID = 1L;
10
11 @Override
12 public boolean empty() {
13 // TODO Auto-generated method stub
14 return super.empty();
15 }
16
17 @Override
18 public synchronized String peek() {
19 // TODO Auto-generated method stub
20 return super.peek();
21 }
22
23 @Override
24 public synchronized String pop() {
25 // TODO Auto-generated method stub
26 return super.pop();
27 }
28
29 @Override
30 public String push(String item) {
31 // TODO Auto-generated method stub
32 return super.push(item);
33 }
34
35 @Override
36 public synchronized int search(Object o) {
37 // TODO Auto-generated method stub
38 return super.search(o);
39 }
40
41 public int getPeekSpaceAmount(){
42 return this.peek().lastIndexOf(" ") + 1;
43 }
44
45 }
版权声明：本文为hexor原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。