1、猫狗收容所
动物收容所。有家动物收容所只收容狗与猫，且严格遵守“先进先出”的原则。在收养该收容所的动物时，收养人只能收养所有动物中“最老”（由其进入收容所的时间长短而定）的动物，或者可以挑选猫或狗（同时必须收养此类动物中“最老”的）。换言之，收养人不能自由挑选想收养的对象。请创建适用于这个系统的数据结构，实现各种操作方法，比如enqueue、dequeueAny、dequeueDog和dequeueCat。允许使用Java内置的LinkedList数据结构。
enqueue方法有一个animal参数，animal[0]代表动物编号，animal[1]代表动物种类，其中 0 代表猫，1 代表狗。
dequeue*方法返回一个列表[动物编号, 动物种类]，若没有可以收养的动物，则返回[-1,-1]。
示例1：
输入：
["AnimalShelf", "enqueue", "enqueue", "dequeueCat", "dequeueDog", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [], [], []]
输出：
[null,null,null,[0,0],[-1,-1],[1,0]]
示例2：
输入：
["AnimalShelf", "enqueue", "enqueue", "enqueue", "dequeueDog", "dequeueCat", "dequeueAny"]
[[], [[0, 0]], [[1, 0]], [[2, 1]], [], [], []]
输出：
[null,null,null,null,[2,1],[0,0],[1,0]]
var AnimalShelf = function() {
this.animals = []
};
/**
* @param {number[]} animal
* @return {void}
*/
AnimalShelf.prototype.enqueue = function(animal) {
this.animals.push(animal)
};
/**
* @return {number[]}
*/
AnimalShelf.prototype.dequeueAny = function() {
if (this.animals.length === 0) return [-1, -1]
return this.animals.shift()
};
/**
* @return {number[]}
*/
AnimalShelf.prototype.dequeueDog = function() {
for (let i = 0; i < this.animals.length; i++) {
let item = this.animals[i]
if (item[1] === 1) {
this.animals.splice(i,1);
return item
}
}
return [-1, -1]
};
/**
* @return {number[]}
*/
AnimalShelf.prototype.dequeueCat = function() {
for (let i = 0; i < this.animals.length; i++) {
let item = this.animals[i]
if (item[1] === 0) {
this.animals.splice(i,1);
return item
}
}
return [-1, -1]
};
/**
* Your AnimalShelf object will be instantiated and called as such:
* var obj = new AnimalShelf()
* obj.enqueue(animal)
* var param_2 = obj.dequeueAny()
* var param_3 = obj.dequeueDog()
* var param_4 = obj.dequeueCat()
*/
2、接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
image.png
示例1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例2：
输入：height = [4,2,0,3,2,5]
输出：9
/**
* @param {number[]} height
* @return {number}
*/
var trap = function(height) {
if (height.length < 3) return 0
let sum = 0
let maxIndex = height.indexOf(Math.max(...height))
console.log(maxIndex, 'maxIndex')
let leftMax = maxIndex
let rightMax = maxIndex
while (leftMax - 1 > 0 ) {
let leftTotal = 0
let leftArr = height.slice(0, leftMax)
let left = height.indexOf(Math.max(...leftArr))
console.log(left, 'left', leftMax - 1, leftArr)
if (left !== leftMax - 1 && height[left] !== 0) {
for (let i = leftMax; i >= left ; i--) {
leftTotal += height[i]
}
leftTotal = leftTotal - (height[leftMax] - height[left])
sum = sum + Math.abs(height[left] * (leftMax - left + 1) - leftTotal)
console.log(sum, 'in -sum')
}
leftMax = left
}
console.log(sum, 'sum----')
while (rightMax + 1 <= height.length - 1) {
let rightTotal = 0
let rightArr = height.slice(rightMax+1)
let right = rightArr.indexOf(Math.max(...rightArr)) +rightMax+1
if (right !== rightMax + 1) {
for (let i = rightMax; i <= right; i++) {
rightTotal += height[i]
}
rightTotal = rightTotal - (height[rightMax] - height[right])
sum = sum + Math.abs(height[right] * (right - rightMax +1) - rightTotal)
}
rightMax = right
}
return sum
};
