Last active
August 29, 2015 14:27
-
-
Save omengye/5268de0158c4dff81a71 to your computer and use it in GitHub Desktop.
合并时间段或时间点
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package algorithms; | |
| import java.util.ArrayList; | |
| import java.util.Arrays; | |
| import java.util.List; | |
| class Tree { | |
| public class TimeTree { | |
| private String value; | |
| private String type; | |
| private TimeTree left; | |
| private TimeTree right; | |
| private int num; | |
| public int getNum() { | |
| return num; | |
| } | |
| public void setNum(int num) { | |
| this.num = num; | |
| } | |
| public String getValue() { | |
| return value; | |
| } | |
| public void setValue(String value) { | |
| this.value = value; | |
| } | |
| public String getType() { | |
| return type; | |
| } | |
| public void setType(String type) { | |
| this.type = type; | |
| } | |
| public TimeTree getLeft() { | |
| return left; | |
| } | |
| public void setLeft(TimeTree left) { | |
| this.left = left; | |
| } | |
| public TimeTree getRight() { | |
| return right; | |
| } | |
| public void setRight(TimeTree right) { | |
| this.right = right; | |
| } | |
| } | |
| public List<String> periodType = Arrays.asList("begin","end"); | |
| //添加节点 | |
| public TimeTree putTime(TimeTree tree, String time, String type) { | |
| if (tree == null) { | |
| tree = new TimeTree(); | |
| tree.setValue(time); | |
| tree.setType(type); | |
| tree.setNum(1); | |
| } | |
| else if (tree.value.compareTo(time) > 0) { | |
| tree.left = putTime(tree.left, time, type); | |
| } | |
| else if (tree.value.compareTo(time) < 0) { | |
| tree.right = putTime(tree.right, time, type); | |
| } | |
| else if (tree.value.compareTo(time) == 0 | |
| && (!tree.type.equals(type) && periodType.contains(tree.type) && periodType.contains(type))) { | |
| --tree.num; | |
| if (tree.num == 0){ | |
| tree.setType("point"); | |
| } | |
| } | |
| else if (tree.value.compareTo(time) ==0 | |
| && tree.type == type) { | |
| tree.setNum(1+tree.getNum()); | |
| } | |
| else if (tree.value.compareTo(time) ==0 | |
| && tree.type.equals("point")) { | |
| } | |
| return tree; | |
| } | |
| public static void main(String args[]) { | |
| Tree tree = new Tree(); | |
| TimeTree node = null; | |
| node = tree.putTime(node, "03", "begin"); | |
| node = tree.putTime(node, "07", "end"); | |
| node = tree.putTime(node, "03", "begin"); | |
| node = tree.putTime(node, "04", "end"); | |
| node = tree.putTime(node, "02", "begin"); | |
| node = tree.putTime(node, "03", "end"); | |
| node = tree.putTime(node, "07", "begin"); | |
| node = tree.putTime(node, "08", "end"); | |
| node = tree.putTime(node, "04", "point"); | |
| node = tree.putTime(node, "07", "point"); | |
| node = tree.putTime(node, "02", "point"); | |
| node = tree.putTime(node, "10", "point"); | |
| node = tree.putTime(node, "06", "begin"); | |
| node = tree.putTime(node, "09", "end"); | |
| List<String[]> btList = new ArrayList<>(); | |
| tree.orderTree(node, btList); | |
| List<Periods> periodList = tree.TransList(btList); | |
| for (Periods period: periodList) { | |
| System.out.print(period.getBegin() + ","); | |
| System.out.print(period.getEnd()); | |
| System.out.println(); | |
| } | |
| } | |
| //二叉树中序排序 | |
| public void orderTree(TimeTree node, List<String[]> btList) { | |
| if (node.getLeft() != null) { | |
| orderTree(node.getLeft(), btList); | |
| } | |
| for (int i=0; i<node.num; ++i) { | |
| String[] nodes = new String[]{node.getValue(),node.getType()}; | |
| btList.add(nodes); | |
| } | |
| if (node.getRight() != null) { | |
| orderTree(node.getRight(), btList); | |
| } | |
| } | |
| // | |
| public class Periods { | |
| private String begin; | |
| private String end; | |
| public String getBegin() { | |
| return begin; | |
| } | |
| public void setBegin(String begin) { | |
| this.begin = begin; | |
| } | |
| public String getEnd() { | |
| return end; | |
| } | |
| public void setEnd(String end) { | |
| this.end = end; | |
| } | |
| } | |
| //游标提取 | |
| public List<Periods> TransList(List<String[]> orderList) { | |
| List<Periods> periodList = new ArrayList<>(); | |
| int beginNum = 0; | |
| int endNum = 0; | |
| String beginValue = ""; | |
| boolean flag = false; | |
| for (String[] order: orderList) { | |
| if (!flag) { | |
| if (order[1].equals("begin")) { | |
| beginValue = order[0]; | |
| ++beginNum; | |
| flag = true; | |
| } | |
| else if (order[1].equals("point")) { | |
| Periods periods = new Periods(); | |
| periods.setBegin(order[0]); | |
| periods.setEnd(order[0]); | |
| periodList.add(periods); | |
| flag = true; | |
| } | |
| } | |
| else if (order[1].equals("begin")) { | |
| ++beginNum; | |
| } | |
| else if (order[1].equals("end") && beginNum != endNum) { | |
| ++endNum; | |
| } | |
| if (order[1].equals("end") && beginNum == endNum) { | |
| Periods periods = new Periods(); | |
| periods.setBegin(beginValue); | |
| periods.setEnd(order[0]); | |
| periodList.add(periods); | |
| //重设 | |
| beginNum = 0; | |
| endNum = 0; | |
| beginValue = ""; | |
| flag = false; | |
| } | |
| } | |
| return periodList; | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment