美文网首页
2021-04-17算法打卡

2021-04-17算法打卡

作者: 北暖37 | 来源:发表于2021-04-19 14:55 被阅读0次

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

    相关文章

      网友评论

          本文标题:2021-04-17算法打卡

          本文链接:https://www.haomeiwen.com/subject/vfoulltx.html