出题
下午,群里面有同学出了一个简单的算法题,意思是一个房间内,有多个1立方米的箱子,多个箱子可以垂直落在一起,问:剩下的空间可以存多少立方的水(如图)。
自己算法一直不好,但是用进废退,脑子还是得多适应以下这种算法的问题。
简单来说,大家做惯了各自字符串,数组,链表的题,出题者希望通过一个变种的方式影响以下做题者的思路。 简单梳理了一下,其实这个题可以是个数组题,就是将横坐标作为索引,纵坐标箱子的高度作为数组值,于是可以简单的变为:[0,1,0,4,1,0,1,3 ...]
根据木桶理论可以知道,影响盛水多少是由最短的一看板子决定的,于是思路是,求得指定索引区间内,数组中的第一高度和第二高度,这两个index的步长作为宽,第二高度作为高,再减去区间内的所有箱子得到最终的值:
宽 * 高 - 占有的箱子
private static int sum = 0; private static List list = new ArrayList(); list.add(0); list.add(1); list.add(0); list.add(4); list.add(1); list.add(0); list.add(1); list.add(3); list.add(0); list.add(6); list.add(0); list.add(1); list.add(0); list.add(3);
getSum(0, list.size() - 1);
System.out.println("sum:" + sum);
通过递归方式,得到给定区间内的对高值和第二高值,并求出中间面积
private static void getSum(int start, int end) { // 获取第一高点和第二高点
int firstIndex = 0; int firstH = 0; int secondIndex = 0; int secondH = 0; int h = 0; for (int i = start; i <= end; i++) {
h = Integer.parseInt(list.get(i).toString()); if (h > firstH) {
firstH = h;
firstIndex = i;
}
} for (int i = start; i <= end; i++) { if (i == firstIndex) continue;
h = Integer.parseInt(list.get(i).toString()); if (h > secondH) {
secondH = h;
secondIndex = i;
}
} int left = firstIndex >= secondIndex ? secondIndex : firstIndex; int right = secondIndex >= firstIndex ? secondIndex : firstIndex; if (right - left == 1) return; // 获取全部面积
h = firstH > secondH ? secondH : firstH; int skip = right - left - 1; int count = skip * h; // 删除掉占用的块
int remove = removeBlock(left + 1, right);
sum += count;
sum -= remove; if (left - start > 1)
getSum(start, left + 1); if (end - right > 1)
getSum(right - 1, end);
}
删除区间内的实体箱子
private static int removeBlock(int start, int end) { int remove = 0; for (int i = start; i < end; i++) {
remove += Integer.parseInt(list.get(i).toString());
} return remove;
}
© 著作权归作者所有