题目要求:
如右图所示, 设目录的每一行都是一个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 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 map = new HashMap (); // 需要求得的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 } 自定义栈:
MyStack.java 1 import java.util.Stack; 2 3 4 public class MyStack extends Stack{ 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 }