一、树状数组练习题 有n头牛(编号为1~n)，每一头牛都有一个吃草区间[S, E]，如果对于牛i和牛j来说，它们的吃草区间满足下面的条件则证明牛i比牛j强壮：Si <= Sj and Ej <= Ei and Ei - Si > Ej - Sj。现在已知每一头牛的吃草区间，要求输出每头牛有几头牛比其强壮。 其中:1 <= N <= 100000, 0 <= S < E <= 100000
样例:
Sample Input
3 (3头牛） 1 2 牛的[s,e]值 0 3 3 4 0
Sample Output
1 0 0 (比第一头牛强的有一头,比第二头牛强的没有,比第三头牛强的没有)
import java.io.StreamTokenizer; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; import java.io.OutputStreamWriter; import java.io.IOException; import java.util.Arrays; class TNode implements Comparable{//表示一头牛 int s;//牛吃草的左端点 int e;//右端点 int label;//牛的序号 public int compareTo(Object o) { int v=((TNode)o).e; if(this.e!=v) //按右端点降序排列 return v-this.e; return this.s-((TNode)o).s;//右端点相等,按左端点升序排序 } public String toString(){ return ("["+s+","+e+"]"); } } public class Main{// static int N=100015; TNode[] cow; int cal[];//树状数组 int res[];//res[i]表示比牛i强壮的牛的个数 int maxn;//右端点的最大值 public Main(){ } private int lowbit(int t){//计算cal[t]展开的项数 return t&(-t); } private int Sum(int k){ //求前k项的和. int sum=0; while(k>0){ sum+=cal[k]; k=k-lowbit(k); } return sum; } private void update(int i,int x){ //增加某个元素的大小,给某个节点 i 加上 x while(i<=maxn){ cal[i]=cal[i]+x; //更新父节点 i=i+lowbit(i); } } public static void main(String args[]) throws IOException{ Main ma=new Main(); ma.go(); } public void go() throws IOException{ StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); while(true) { st.nextToken(); int n= (int) st.nval; //牛的个数 if(n==0) break; cow=new TNode[N]; cal=new int[N]; res=new int[N]; for(int i=0;i<N;i++){ cow[i]=new TNode(); // cal[i]=0; } for(int i=0;i<n;i++) {//读入牛的吃草区间 st.nextToken(); cow[i].s=(int) st.nval; st.nextToken(); cow[i].e=(int) st.nval; cow[i].s++; cow[i].e++; cow[i].label=i;//牛的原始序号 if(cow[i].e>maxn) maxn=cow[i].e;//最大右端点 } Arrays.sort(cow);//排序 // for(int i=0;i<n;i++) // System.out.println(cow[i]); for(int i=0;i<n;i++) { if(i!=0&&cow[i].s==cow[i-1].s&&cow[i].e==cow[i-1].e)//两头牛有相同的吃草区间 res[cow[i].label]=res[cow[i-1].label];//它们有相同的答案 else res[cow[i].label]=Sum(cow[i].s);//统计比cow[i].label这头牛强的牛的数目 update(cow[i].s,1);//更新 } System.out.printf("%d",res[0]); for(int i=1;i<n;i++) System.out.printf(" %d",res[i]); System.out.println(); } } }二、祖先问题
package day_6; import java.util.ArrayList; import java.util.List; public class Demo1 { public static void main(String[] args) { test01(); } // 形状普通的树 // 1 // / \ // 2 3 // / \ // 4 5 // / \ / | \ // 6 7 8 9 10 public static void test01() { TreeNode n1 = new TreeNode(1); TreeNode n2 = new TreeNode(2); TreeNode n3 = new TreeNode(3); TreeNode n4 = new TreeNode(4); TreeNode n5 = new TreeNode(5); TreeNode n6 = new TreeNode(6); TreeNode n7 = new TreeNode(7); TreeNode n8 = new TreeNode(8); TreeNode n9 = new TreeNode(9); TreeNode n10 = new TreeNode(10); n1.children.add(n2); n1.children.add(n3); n2.children.add(n4); n4.children.add(n6); n4.children.add(n7); n3.children.add(n5); n5.children.add(n8); n5.children.add(n9); n5.children.add(n10); System.out.println(getLastCommonParent(n1, n9, n10)); } /* * 获取两个节点的最低公共祖先 */ public static TreeNode getLastCommonParent(TreeNode root, TreeNode p1, TreeNode p2) { //path1和path2分别存储根节点到p1和p2的路径（不包括p1和p2） List<TreeNode> path1 = new ArrayList<TreeNode>(); List<TreeNode> path2 = new ArrayList<TreeNode>(); List<TreeNode> tmpList = new ArrayList<TreeNode>(); getNodePath(root, p1, tmpList, path1); getNodePath(root, p2, tmpList, path2); //如果路径不存在，返回空 if (path1.size() == 0 || path2.size() == 0) return null; return getLastCommonParent(path1, path2); } // 获取根节点到目标节点的路径 public static void getNodePath(TreeNode root, TreeNode target, List<TreeNode> tmpList, List<TreeNode> path) { //鲁棒性 if (root == null || root == target) return; tmpList.add(root); List<TreeNode> children = root.children; for (TreeNode node : children) { if (node == target) { path.addAll(tmpList); break; } getNodePath(node, target, tmpList, path); } tmpList.remove(tmpList.size() - 1); } //将问题转化为求链表最后一个共同节点 private static TreeNode getLastCommonParent(List<TreeNode> p1, List<TreeNode> p2) { TreeNode tmpNode = null; for (int i = 0; i < p1.size(); i++) { if (p1.get(i) != p2.get(i)) break; tmpNode = p1.get(i); } return tmpNode; } // 节点类 private static class TreeNode { int val; List<TreeNode> children = new ArrayList<TreeNode>(); public TreeNode(int val) { this.val = val; } @Override public String toString() { return val + ""; } } }