2021-04-17算法打卡

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
};