浏览 2388 次
锁定老帖子 主题:写了个递归算法,欢迎大家来拍砖
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2011-10-12
/** * 一个递归算法,将一个PropertyDO(地域)的列表merge成一个PropertyDO * @author hemaodong * @param propertyDO1 * @param propertyDO2 * @return propertyDO1 */ private static PropertyDO mergeArea(List<PropertyDO> propertyDOs) { if (null != propertyDOs && propertyDOs.size() == 1) { return propertyDOs.get(0); } int i = propertyDOs.size(); PropertyDO propertyDO1 = propertyDOs.get(i-2); PropertyDO propertyDO2 = propertyDOs.get(i-1); // 将propertyDO2转化成MAP,便于检索,如果propertyDO2中存在propertyDO1的值, // 则将propertyDO2中的该值移除,若循环检索完后propertyDO2中还有值,则将 // propertyDO2中的值循环添加至propertyDO1中并返回,至此就完成了地域的merge Map<Long, EnumDO> map = convert2Map(propertyDO2); for (EnumDO enumDO : propertyDO1.getValuesAsList()) { if (null != map.get(enumDO.getId())) { map.remove(enumDO.getId()); } } if (map != null && map.size() != 0) { for (Long key : map.keySet()) { propertyDO1.getValuesAsList().add(map.get(key)); } } PropertyDO temp = propertyDO1; propertyDOs.remove(propertyDO1); propertyDOs.remove(propertyDO2); propertyDOs.add(temp); mergeArea(propertyDOs); return propertyDOs.get(0); } /** * @author hemaodong * @param propertyDO2 * @return */ private static Map<Long, EnumDO> convert2Map(PropertyDO propertyDO) { Map<Long, EnumDO> map = new HashMap<Long, EnumDO>(); for (EnumDO enumDO : propertyDO.getValuesAsList()) { map.put(enumDO.getId(), enumDO); } return map; } @SuppressWarnings("serial") public static void main(String args[]) { final PropertyDO do1 = new PropertyDO(); List<EnumDO> enumDOlist1 = new ArrayList<EnumDO>(){ { EnumDO enumDO1 = new EnumDO(1l, "1"); EnumDO enumDO2 = new EnumDO(2l, "2"); EnumDO enumDO3 = new EnumDO(3l, "3"); add(enumDO1); add(enumDO2); add(enumDO3); } }; do1.setValuesAsList(enumDOlist1); final PropertyDO do2 = new PropertyDO(); List<EnumDO> enumDOlist2 = new ArrayList<EnumDO>(){ { EnumDO enumDO3 = new EnumDO(3l, "3"); EnumDO enumDO4 = new EnumDO(4l, "4"); EnumDO enumDO5 = new EnumDO(5l, "5"); add(enumDO3); add(enumDO4); add(enumDO5); } }; do2.setValuesAsList(enumDOlist2); final PropertyDO do3 = new PropertyDO(); List<EnumDO> enumDOlist3 = new ArrayList<EnumDO>(){ { EnumDO enumDO3 = new EnumDO(3l, "3"); EnumDO enumDO4 = new EnumDO(4l, "4"); EnumDO enumDO5 = new EnumDO(5l, "5"); add(enumDO3); add(enumDO4); add(enumDO5); } }; do3.setValuesAsList(enumDOlist3); final PropertyDO do4 = new PropertyDO(); List<EnumDO> enumDOlist4 = new ArrayList<EnumDO>(){ { EnumDO enumDO3 = new EnumDO(7l, "7"); EnumDO enumDO4 = new EnumDO(8l, "8"); EnumDO enumDO5 = new EnumDO(9l, "9"); add(enumDO3); add(enumDO4); add(enumDO5); } }; do4.setValuesAsList(enumDOlist4); List<PropertyDO> propertyDOs = new ArrayList<PropertyDO>(){ { add(do1); add(do2); add(do3); add(do4); } }; System.out.println(mergeArea(propertyDOs).getValuesAsList().size()); } 欢迎大家提供更好的算法 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2011-10-13
不推荐使用递归,不太容易懂。
以下是我的代码,我不知道你的EnumDO和PropertyDO是什么样的。 我只是根据调用的方法建立一个简单的数据类。 package model.test; import java.util.ArrayList; import java.util.Collection; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; public class TEST { /** * 不使用递归以减少内存开销,亦使得程序易于理解 */ private static PropertyDO mergeArea(List<PropertyDO> propertyDOs) { if (null == propertyDOs) return null;// 判断数组是否为空,你原先的判断是有漏洞的。 // 使用map来去重。 Map<Long, EnumDO> enumDOs = new HashMap<Long, EnumDO>(); for (PropertyDO propertyDO : propertyDOs) { for (EnumDO enumDO : propertyDO.getValuesAsList()) { enumDOs.put(enumDO.getId(), enumDO); } } return new PropertyDO(enumDOs.values()); } @SuppressWarnings("serial") public static void main(String args[]) { final PropertyDO do1 = new PropertyDO(new ArrayList<EnumDO>() { { add(new EnumDO(1l, "1")); add(new EnumDO(2l, "2")); add(new EnumDO(3l, "3")); } }); final PropertyDO do2 = new PropertyDO(new ArrayList<EnumDO>() { { add(new EnumDO(3l, "3")); add(new EnumDO(4l, "4")); add(new EnumDO(5l, "5")); } }); final PropertyDO do3 = new PropertyDO(new ArrayList<EnumDO>() { { add(new EnumDO(3l, "3")); add(new EnumDO(4l, "4")); add(new EnumDO(5l, "5")); } }); final PropertyDO do4 = new PropertyDO(new ArrayList<EnumDO>() { { add(new EnumDO(7l, "7")); add(new EnumDO(8l, "8")); add(new EnumDO(9l, "9")); } }); List<PropertyDO> propertyDOs = new ArrayList<PropertyDO>(); Collections.addAll(propertyDOs, do1,do2,do3,do4); System.out.println(mergeArea(propertyDOs).getValuesAsList().size()); } } class EnumDO { long id; String name; public EnumDO(long l, String string) { this.id = l; this.name = string; } public Long getId() { return this.id; } } class PropertyDO { List<EnumDO> list; public PropertyDO(Collection<EnumDO> enumDOs) { this.list = new ArrayList<EnumDO>(enumDOs); } public List<EnumDO> getValuesAsList() { return list; } } |
|
返回顶楼 | |
发表时间:2011-10-14
最后修改:2011-10-14
给你做个code review。。。
1. private static PropertyDO mergeArea(List<PropertyDO> propertyDOs) { if (null != propertyDOs && propertyDOs.size() == 1) { return propertyDOs.get(0); } 。。。 mergeArea(propertyDOs); return propertyDOs.get(0); } 最后两行明明就可以直接写成 return mergeArea(propertyDOs); 然后一眼就看出是个尾递归。尾递归通常都能很方便地转换为使用循环的非递归实现,有些语言都能自动帮你优化,不过java不行,所以其实应该尽量用改用循环实现。 2. 既然你有 null != propertyDOs && propertyDOs.size() == 1 这样的判断,说明你认为propertyDOs可能为null。然后你跟着就来一行 int i = propertyDOs.size(); 这里直接就抛NPE了。 3. 这个convert2Map是个私有方法,对于当前的类来说是可控代码。它明明不可能返回null,后面为什么要做非null判断呢。而且foreach循环(或者下面第4点的修改)已经处理了map.size()==0的情况,所以 if (map != null && map.size() != 0) 这个判断纯属多余。 4. for (Long key : map.keySet()) { propertyDO1.getValuesAsList().add(map.get(key)); } 为什么不 for (EnumDO v : map.values()) { ...add(v); } 或者直接 propertyDO1.getValuesAsList().addAll(map.values()); 5. 你明明已经拿着propertyDO1的引用,干嘛要先把它赋值给temp,List.remove又不会干掉这个propertyDO1。 |
|
返回顶楼 | |