java最优算法讨论

有一字符串，格式为
   1,2@1,3@1,7@2@1,5@1,12@9@1,16@10@5@1

上面字符串每个逗号分隔开的单独部分都是一颗树形结构的层级关系表示。比如说5@1是说自己的节点id为5，父级节点id为1.其他类似。

     问题是，怎么根据上面一个字符串构建出该字符串对应的tree来。
1
--2
----7
--3
--5
----16
--12


不是二叉树。无限级分类

或者说这些字符串其实是一棵无限级分类树的不连续的几个节点

所谓“不连续”具体体现在：该字符串用逗号分隔成数组后有几个元素，最后画出的tree里就应该有几个节点。比如说该题目的字符串画出的tree里有且只有 1、2、3、7、5、12、16 这几个节点（即分隔后数组每个元素的第一个数字）。而10和9 这两个节点是不显示的（没有以他们开头的元素所以被跳过了）。

 

而且由于不连续，所以代表最原始tree根节点的 “1” 是可能不出现在字符串里的。比如说：

 

" 2@1,3@1,5@1,12@9@1,16@10@5@1 "

画出的应该是

--2
--3
--5
----16
--12

 

 

我给出一个自己的笨方法。

 

 

package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class Test {
	
	public static int getLen(String str){
		return str.length()-str.replaceAll("@", "").length();
	}
	
	public static String removePre(String str){
		return str.split("--")[str.split("--").length-1];
	}	
	
	public static void main(String[] a){
		String str="7@2@1,2@1,3@1,11@3@1,5@1,62@85@11@3@1,12@9@1,8@16@10@5@1";
		String[] strs=str.split(",");
		
		HashMap<Integer,ArrayList<String>> map=new HashMap<Integer,ArrayList<String>>();
		ArrayList<Integer> deep=new ArrayList<Integer>();
		for(int i=0;i<strs.length;i++){
			int len=getLen(strs[i]);
			if(!deep.contains(len)){
				deep.add(len);
			}
			ArrayList<String> temp=map.get(len);
			if(temp==null){
				temp=new ArrayList<String>();
			}
			temp.add(strs[i]);
			map.put(len, temp);
		}
		Object[] deeps=deep.toArray();
		Arrays.sort(deeps);
		
		
		ArrayList<String> tree=new ArrayList<String>();
		for(int i=0;i<deeps.length;i++){			
			ArrayList<String> temp=map.get(deeps[i]);
			for(int m=0;m<temp.size();m++){
				String node=temp.get(m);
				int index=tree.size();
				for(int n=0;n<tree.size();n++){
					if(node.endsWith("@"+removePre(tree.get(n)))){
						index=n+1;
						node="--"+node;
					}
				}
				tree.add(index,node);
			}
			
		}
		
		for(int i=0;i<tree.size();i++){
			System.out.println(tree.get(i).split("@")[0]);
			
		}
	}

}

 

 

 

设计树节点数据结构， 压栈, 取 node 如（2@1），树遍历，添加节点。。。

 

学习中....

用二叉树应该可以搞定

设计模式里有个组合模式的。那个就是为了解决树形问题而存在的。
二叉树不行吧，人家没说一定是一棵二叉树。

不是二叉。无限级分类

不太理解你的意思。能否具体点。

另外题目的字符串不一定是连续的。或者说这些字符串其实是一棵无限级分类树的不连续的几个节点。

随便写了一个，唯一的要求是不会在树中同时出现 2@1,2@4@1等这样的数据
如果想构建以上情况的树。需要从根节点逐级遍历构建

package test;

import java.util.HashSet;
import java.util.Set;

public class Node {
	public Node parent;
	public String value;
	public Set<Node> childs = new HashSet<Node>();

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((value == null) ? 0 : value.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Node other = (Node) obj;
		if (value == null) {
			if (other.value != null)
				return false;
		} else if (!value.equals(other.value))
			return false;
		return true;
	}

	@Override
	public String toString() {
		return "Node [childs=" + childs + ", parent=" + parent + ", value="
				+ value + "]";
	}

}

package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

public class Main {
	public Node root;
	private List<Node> nodes = new ArrayList<Node>();

	public void init(String str) {
		String[] strs = str.split(",");
		for (int i = 0; i < strs.length; i++) {
			int index = strs[i].indexOf("@");
			if (index == -1) {
				root = new Node();
				root.value = strs[i];
				nodes.add(root);
			} else {
				String[] ns = strs[i].split("@");
				for (int j = 0; j < ns.length; j++) {
					Node node = new Node();
					node.value = ns[j];
					if (!nodes.contains(node)) {
						nodes.add(node);
					}
				}

				create(Arrays.asList(ns), 0);
			}
		}

		print(root, "");
	}

	public void print(Node node, String str) {
		System.out.println(str + node.value);
		for (Iterator<Node> iterator = node.childs.iterator(); iterator
				.hasNext();) {
			Node child = iterator.next();
			print(child, leftPad(str));
		}
	}

	public String leftPad(String str) {
		return "--" + str;
	}

	public Node create(List<String> list, int index) {
		Node node = null;
		if (index < list.size()) {
			node = getNodeByStr(list.get(index));
			if (node.parent == null) {
				node.parent = create(list, ++index);
			}
			if (node.parent != null) {
				node.parent.childs.add(node);
			}
		}
		return node;
	}

	public Node getNodeByStr(String str) {
		for (int i = 0; i < nodes.size(); i++) {
			Node node = nodes.get(i);
			if (node.value.equals(str)) {
				return node;
			}
		}
		throw new RuntimeException("not such node " + str);
	}

	public static void main(String[] args) {
		String str = "1,2@1,3@1,7@2@1,5@1,12@9@1,16@10@5@1";
		new Main().init(str);
	}
}

我的题目说的可能太不清楚了。字符串是一棵无限级tree里的部分 不连续 的节点，split(",")后数组有几个元素新画出来的tree就应该有几个节点。对于“1,2@1,3@1,7@2@1,5@1,12@9@1,16@10@5@1”中的9、10是不能够出现在结果tree里的。另外，“1”这个最原始的跟节点是有可能不出现在字符串里的。