TreeMap, TreeSet原来用起来这么爽 - 未名空间MITBBS历史存档

TreeMap, TreeSet原来用起来这么爽# Java - 爪哇娇娃

p*32013-11-03 07:11

1 楼

原来java里有balanced的BST, 比C++的好用些，就是接口太多了，记不住。
写了一个求2d overlap矩形面积的题，
核心代码没多少，code都是定义各种结构各种override各种comparator去了:
public class EPI_14_20_3 {
static class Rectangle {
public int xBeg;
public int xEnd;
public int yBeg;
public int yEnd;

public Rectangle(int xb, int xe, int yb, int ye) {
xBeg = xb;
xEnd = xe;
yBeg = yb;
yEnd = ye;
}
}

static class EndPoint {
public int index;
public int pos;
public boolean beg;

public EndPoint(int i, int p, boolean b) {
index = i;
pos = p;
beg = b;
}

@Override
public int hashCode() {
return (index << 16 | index | pos | (beg ? 1 : 0) << 15);
}

@Override
public boolean equals(Object obj) {
EndPoint ed = (EndPoint)obj;
return index == ed.index && pos == ed.pos && beg == ed.beg;
}
}

static class EndPointComparator implements Comparator {
@Override
public int compare(EndPoint ed1, EndPoint ed2) {
return ed1.pos - ed2.pos;
}
}

static public int calcArea(Rectangle[] recs) {
if (null == recs || recs.length <= 0)
return 0;

List lst = new ArrayList();
for (int i = 0; i < recs.length; i++)
{
lst.add(new EndPoint(i, recs[i].xBeg, true));
lst.add(new EndPoint(i, recs[i].xEnd, false));
}

Collections.sort(lst, new EndPointComparator());
SortedSet set = new TreeSet(new
EndPointComparator());

int area = 0;
int prev = 0;
for (EndPoint point : lst) {
int diff = 0;
int pos = point.pos;
if (!set.isEmpty())
{
EndPoint ed1 = set.last();
EndPoint ed2 = set.first();
diff = ed1.pos - ed2.pos;
}

area += diff*(pos - prev);
prev = pos;

if (point.beg) {
set.add(new EndPoint(point.index, recs[point.index].yBeg,
true));
set.add(new EndPoint(point.index, recs[point.index].yEnd,
false));
}
else {
set.remove(new EndPoint(point.index, recs[point.index].yBeg,
true));
set.remove(new EndPoint(point.index, recs[point.index].yEnd,
false));
}
}

return area;
}

public static void main(String[] params) {
Rectangle recs[] = new Rectangle[5];
recs[0] = new Rectangle(1,4,1,3);
recs[1] = new Rectangle(3,5,0,4);
recs[2] = new Rectangle(2,6,2,6);
recs[3] = new Rectangle(7,10,2,4);
recs[4] = new Rectangle(8,9,1,6);

System.out.println(calcArea(recs));
}

}