0
在解決此問題中:http://www.cs.duke.edu/csed/newapt/drawtree.html我編寫了下面的代碼,但它似乎運行速度太慢。有沒有更快的方法檢查所有的孩子節點W/O使用FOR循環?隊列會有幫助嗎?如何提高遞歸函數的運行時間
public class DrawTree {
HashMap<String, ArrayList<String>> map =
new HashMap<String, ArrayList<String>>();
ArrayList<String> drawing = new ArrayList<String>();
String root;
public String[] draw(int[] parents, String[] names) {
for(int x=0; x<parents.length; x++)
{
int parentindex = parents[x];
//root name
if(parentindex==-1)
{
root=names[x];
if(!map.containsKey(names[x]))
{
map.put(names[x], new ArrayList<String>());
}
continue;
}
//add parent, child to map
if (!map.containsKey(names[parentindex]))
map.put(names[parentindex],
new ArrayList<String>());
map.get(names[parentindex]).add(names[x]);
}
sketch("",root,false);
return drawing.toArray(new String[drawing.size()]);
}
//***IMPROVE RUN TIME - different algorithm??***
//method takes root and prefix?
public void sketch(String parent, String child, boolean addPipe){
StringBuilder toAdd = new StringBuilder();
//don't need to add connector pipe
if(!addPipe)
{
//number of spaces to add to prefix
int spaces = parent.indexOf('-')+1;
//add spaces to prefix
while(spaces>0)
{
toAdd.append(" ");
spaces--;
}
toAdd.append("+-"+child);
}
//index of pipe in parent, -1 if parent doesn't have pipe
int parentPipe = parent.indexOf('|');
//need to add connector pipe & parent has pipe
// (is a child of a subtree)
if(parentPipe>0)
{
//number of spaces to add to prefix
int spaces = parent.indexOf('-')+1;
//add spaces to prefix
while(spaces>0)
{
if(spaces==parentPipe) toAdd.append('|');
else toAdd.append(" ");
spaces--;
}
toAdd.append("+-"+child);
}
//need to add pipe and parent doesn't have pipe
if(addPipe && parentPipe<0)
{
int spaces = parent.indexOf('-')+1;
while(spaces>0)
{
if(spaces==2) toAdd.append('|');
else toAdd.append(" ");
}
toAdd.append("+-"+child);
}
//add child to list of tree drawing
String node = toAdd.toString();
drawing.add(node);
//System.out.println(node);
//loop through list of children, passing each recursively
//...count level?
if(map.containsKey(child))
{
//System.out.println("map works");
for(int x = 0; x<map.get(child).size(); x++)
{
boolean pipe = false;
if(x<(map.get(child).size()-1)) pipe=true;
//System.out.println(map.get(child).get(x));
sketch(node, map.get(child).get(x), pipe);
}
}
}
此問題更適合[codereview.se](http://codereview.stackexchange.com/)。 – cheeken
定義爲「慢」的基礎是什麼?你有沒有特別的時機? – kosa
map.containsKey(key)有一個改進。它幾乎與map.get(key)一樣。調用containsKey並逐個獲取是沒有意義的。更好地使用'List list = map.get(key); if(list == null){list = new ArrayList (); map.put(key,list);} list.add(something);' –