左神算法笔记——TreeMap的应用（大楼轮廓问题）
2020-04-11 本文已影响0人
yaco
——总结左神进阶班第四课相关内容
HashMap,TreeMap以及LinkedHashMap的区别
- HashMap:HashMap数据是无序的，底数用数组加链表维护，JDK1.8之后，改为数组+链表+红黑树的一种结构，根据键的hashCode进行数据的存取，对数据的访问速度非常快，在map中插入删除和定位元素，hashMap无疑是最好的选择。
- TreeMap:里面的数据是有序的，底层是一个红黑树，如果想按照自定义顺序或者自然顺序存储数据，TreeMap是一个最好的选择。
- LinkedHashMap:他是hashMap的一个子类，底层维护了一个双向链表，他可以实现输入的顺序和输出的顺序相同。
题目描述
大楼轮廓
测试样例额
基本思路
- 首先将给定数组拆分成我们想要的信息。
- 如
[1,3,3],将此轮廓的起始和终止位置都用单独的结构表示，这里用Node表示。所以可以拆分成Node1(1,3,up)——表示1位置有一条直线上去了和Node2(3,3,down)——表示3位置有一条直线下去了 - 同理，将给定数组中每个大楼的轮廓数组都改造出我们希望得到的Node信息。
- 得到Node信息的数组，并根据Node的位置进行排序，如果位置相等的情况下，则优先排列down.
// 定义位置信息类
public static class Node {
boolean isUp; // 该点是上还是下
int posi; // 该点的坐标位置
public int h; // 该点的高度
public Node(boolean bORe, int position, int height) {
isUp = bORe;
posi = position;
h = height;
}
}
// 定义一个比较器： 按照Node节点的posi位置来排序，如果两个点的位置相同，则向下的位置在前面
public static class NodeComparator implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
if (o1.posi != o2.posi) {
return o1.posi - o2.posi;
}
if (o1.isUp != o2.isUp) {
return o1.isUp ? -1 : 1;
}
return 0;
}
}
//------------将指定的大楼轮廓改造为Node信息--------------
Node[] nodes = new Node[buildings.length * 2];
for (int i = 0; i < buildings.length; i++) {
nodes[i * 2] = new Node(true, buildings[i][0], buildings[i][2]);
nodes[i * 2 + 1] = new Node(false, buildings[i][1], buildings[i][2]);
}
Arrays.sort(nodes, new NodeComparator());
- 然后维护两个TreeMap结构。
- TreeMap<Integer,Interger> htMap : 存放指定高度现有的个数。
- TreeMap<Integer,Interger> htMap : 存放指定位置的最大高度。
- 每次遍历Node[]的时候，如果碰到up时，检查当前的的htMap中是否存在此处Node的高度，如果不存在htMap的value直接赋值1，否则value增1；
- 如果碰到down时，检查当前的的htMap中是否存在此处Node的高度，如果存在htMap且value为1，则直接移除这个节点，因为此大楼轮廓已经走完了，否则value减1；
- 每次遍历Node时，都添加pmMap的值，因为它表示每个位置的最大高度。
TreeMap<Integer, Integer> htMap = new TreeMap<>(); // 代表某一个高度h出现的次数
TreeMap<Integer, Integer> pmMap = new TreeMap<>(); // 代表每个节点位置的当前最大高度
for (int i = 0; i < nodes.length; i++) {
if (nodes[i].isUp) {
if (!htMap.containsKey(nodes[i].h)) {
htMap.put(nodes[i].h, 1);
} else {
htMap.put(nodes[i].h, htMap.get(nodes[i].h) + 1);
}
} else {
if (htMap.containsKey(nodes[i].h)) {
if (htMap.get(nodes[i].h) == 1) { // 如果当前高度只有一个了，那么直接将此高度删除即可
htMap.remove(nodes[i].h);
} else {
htMap.put(nodes[i].h, htMap.get(nodes[i].h) - 1);
}
}
}
//-------更新当前位置的最大高度--------
if (htMap.isEmpty()) {
// 如果当前的htMap清空了，那么当前位置的最大高度置为0
pmMap.put(nodes[i].posi, 0);
} else {
// 如果htMap不为null，那么当前位置的最大高度就是htMap中的最大的键值
pmMap.put(nodes[i].posi, htMap.lastKey());
}
}
- 最后就是更新轮廓线，这时只需要pmMap即可，也就时每个位置的最大高度。
- 思路就是，一旦当前位置的最大高度改变了，那么轮廓线肯定也就出来了,当最大高度不改变，那么此处就没有轮廓线。
//----------- 生成结果集对象，只需要用到pmMap -----------------
List<List<Integer>> res = new ArrayList<>();
int start = 0;
int height = 0;
for (Integer curPosition : pmMap.keySet()) {
int curMaxHeight = pmMap.get(curPosition);
if(height != curMaxHeight){
if(height != 0){
List<Integer> newRecord = new ArrayList<>();
newRecord.add(start);
newRecord.add(curPosition);
newRecord.add(height);
res.add(newRecord);
}
start = curPosition;
height = curMaxHeight;
}
}
return res;
TreeMap的优势分析：
- 首先因为我们需要更新每个位置的最大轮廓，所以这步操作(
pmMap.put(nodes[i].posi, htMap.lastKey());)从htMap中直接获取当前存在的最大高度，特别简单。 - 其次，在最后进行ptMap的遍历更新轮廓线的时候，这个时候因为TreeMap遍历的key值也是有序的，刚好满足位置递增的要求
最后附上整体的代码：
// 定义位置信息类
public static class Node {
boolean isUp; // 该点是上还是下
int posi; // 该点的坐标位置
public int h; // 该点的高度
public Node(boolean bORe, int position, int height) {
isUp = bORe;
posi = position;
h = height;
}
}
// 定义一个比较器： 按照Node节点的posi位置来排序，如果两个点的位置相同，则向下的位置在前面
public static class NodeComparator implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
if (o1.posi != o2.posi) {
return o1.posi - o2.posi;
}
if (o1.isUp != o2.isUp) {
return o1.isUp ? -1 : 1;
}
return 0;
}
}
// 建立轮廓线的主函数
public static List<List<Integer>> buildingOutline(int[][] buildings) {
// 改造提供的原始轮廓线，并排序
Node[] nodes = new Node[buildings.length * 2];
for (int i = 0; i < buildings.length; i++) {
nodes[i * 2] = new Node(true, buildings[i][0], buildings[i][2]);
nodes[i * 2 + 1] = new Node(false, buildings[i][1], buildings[i][2]);
}
Arrays.sort(nodes, new NodeComparator());
//--------------------遍历Node数组，获取每个位置的最大高度-----------------------
TreeMap<Integer, Integer> htMap = new TreeMap<>(); // 代表某一个高度h出现的次数
TreeMap<Integer, Integer> pmMap = new TreeMap<>(); // 代表每个节点位置的当前最大高度
for (int i = 0; i < nodes.length; i++) {
if (nodes[i].isUp) {
if (!htMap.containsKey(nodes[i].h)) {
htMap.put(nodes[i].h, 1);
} else {
htMap.put(nodes[i].h, htMap.get(nodes[i].h) + 1);
}
} else {
if (htMap.containsKey(nodes[i].h)) {
if (htMap.get(nodes[i].h) == 1) { // 如果当前高度只有一个了，那么直接将此高度删除即可
htMap.remove(nodes[i].h);
} else {
htMap.put(nodes[i].h, htMap.get(nodes[i].h) - 1);
}
}
}
//-------更新当前位置的最大高度--------
if (htMap.isEmpty()) {
// 如果当前的htMap清空了，那么当前位置的最大高度置为0
pmMap.put(nodes[i].posi, 0);
} else {
// 如果htMap不为null，那么当前位置的最大高度就是htMap中的最大的键值
pmMap.put(nodes[i].posi, htMap.lastKey());
}
}
//----------- 生成结果集对象，只需要用到pmMap -----------------
List<List<Integer>> res = new ArrayList<>();
int start = 0;
int height = 0;
for (Integer curPosition : pmMap.keySet()) {
int curMaxHeight = pmMap.get(curPosition);
if(height != curMaxHeight){
if(height != 0){
List<Integer> newRecord = new ArrayList<>();
newRecord.add(start);
newRecord.add(curPosition);
newRecord.add(height);
res.add(newRecord);
}
start = curPosition;
height = curMaxHeight;
}
}
return res;
}
