淘宝笔试 编程 讨论
1 一篇英文文章内容，用最高效的数据结构和算法 打印出这篇英文文章里边出现的英文单词 和 它出现的次数，并说下你用的数据结构和算法
2 有一棵树 每个节点存放着字符串或者是整数，将这棵树上的数据和树的结构存储在一个文件并且在需要要恢复的时候能够进行恢复
大家踊跃发言，也许灵感就产生了
[解决办法]
测试了好几种读取统计方法FileInputStream,DataInputStream,BufferedReader,RandomAccessFile,FileChannel,FileChannel Map , 目前发现下面这种做法时间最少，效率最高。
public static Map test() throws IOException {
HashMap<String ,Integer> hashMap = new HashMap<String ,Integer>();
FileChannel fc = new RandomAccessFile(new File("c:/test.txt"), "rw")
.getChannel();
ByteBuffer buffer = fc.map(FileChannel.MapMode.READ_WRITE, 0, fc.size());
byte b = 0;
StringBuffer sb = new StringBuffer();
boolean flagOther = true; //刚刚读取的字符是否为非单词字符（其他字符），这里假设单词字符只允许 a-z A-z - 27种
while(buffer.hasRemaining()){
b = buffer.get();//
if(b>=97&&b<=122
[解决办法]
b>=65&&b<=90
[解决办法]
b == 45){
sb.append((char)b);
if(flagOther == true)flagOther = false;//只要读到单词字符，就认为没有读到 其他字符
}
else {
if(flagOther == false){//前面读到的是单词字符，这一次读到其他字符，就将把缓冲区内容它打印出来
System.out.println(sb.toString());
String tempWord = sb.toString();
hashMap.put(tempWord, hashMap.containsKey(tempWord)? hashMap.get(tempWord) + 1:1);
sb.delete(0,sb.length());
flagOther = true;//因为读到其他字符，所以将它设为真
}
}
}
System.out.println(sb.toString());//已经到了文件尾
sb.delete(0,sb.length());
fc.close();
return hashMap;
}
public static void main(String[] args) {
String str = "Do you know? you are a good boy. very good. Do you want to play with me";
testReg(str.toLowerCase());
}
public static void testReg(String str) {
Matcher matcher = Pattern.compile("\\b(\\w+?)\\b").matcher(str);
boolean find = matcher.find();// 是否找到匹配结果
String word = null;
int i = 0;
if (find) {
word = matcher.group(1);// 第一个单词
Pattern pattern = Pattern.compile("\\b" + word + "\\b");// 用第一个单词构建一个新的正则表达式
Matcher matcher2 = pattern.matcher(str);
while (matcher2.find()) {
i++;// 找到匹配结果，+1操作
}
System.out.println("word:" + word + " count:" + i);// 打印结果
testReg(matcher2.replaceAll(""));// 把单词替换为空，递归调用
}
}
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.List;
public class Test2 {
public static void main(String[] args) throws Exception{
int id = 1;
ArrayList<Tree> trees = new ArrayList<Tree>();
trees.add(new Tree(0,-1,false,"根结点"));//建立几个测试数据
trees.add(new Tree(1,0,false,"根结点左孩子"));
trees.add(new Tree(2,0,true,"根结点右孩子"));
trees.add(new Tree(3,1,true,"根结点左孩子1号孙子"));
trees.add(new Tree(4,1,true,"根结点左孩子2号孙子"));
trees.add(new Tree(5,1,true,"根结点左孩子3号孙子"));
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream("c:/tree.txt"));
oos.writeObject(trees);
oos.close();
ObjectInputStream ois = new ObjectInputStream(new FileInputStream("c:/tree.txt"));
trees = (ArrayList<Tree>)ois.readObject();
for(int i=0; i<trees.size(); i++){
System.out.println("*********************第" +i + "棵子树**************************");
display(trees,trees.get(i), 0);
}
}
static void display(ArrayList<Tree> trees,Tree tree, int level){//展示以tree为根结点的子树
for(int i=0; i<level; i++)System.out.print("--");
System.out.println(tree);
if(tree.isLeaf)
return;
for(Tree tempTree : trees)
if(tempTree.parent == tree.id) display(trees,tempTree,level+1);
}
//...其他操作，插入子树，删除子树...由于题意没要求，我就不写了
}
class Tree implements Serializable{
int id;
int parent;// 树的父亲
boolean isLeaf;//是否叶子结点
String str;
//可以添加冗余字段childList，在这里也不写了
public Tree(int id, int parent, boolean isLeaf, String str) {
this.id = id;
this.parent = parent;
this.isLeaf = isLeaf;
this.str = str;
}
public String toString(){
return " id = " + id + " str = " + str;
}
}
/*
*********************第0棵子树**************************
id = 0 str = 根结点
-- id = 1 str = 根结点左孩子
---- id = 3 str = 根结点左孩子1号孙子
---- id = 4 str = 根结点左孩子2号孙子
---- id = 5 str = 根结点左孩子3号孙子
-- id = 2 str = 根结点右孩子
*********************第1棵子树**************************
id = 1 str = 根结点左孩子
-- id = 3 str = 根结点左孩子1号孙子
-- id = 4 str = 根结点左孩子2号孙子
-- id = 5 str = 根结点左孩子3号孙子
*********************第2棵子树**************************
id = 2 str = 根结点右孩子
*********************第3棵子树**************************
id = 3 str = 根结点左孩子1号孙子
*********************第4棵子树**************************
id = 4 str = 根结点左孩子2号孙子
*********************第5棵子树**************************
id = 5 str = 根结点左孩子3号孙子
*/