js.水壶问题

/**

 * @param {number} x

 * @param {number} y

 * @param {number} target

 * @return {boolean}

 */

var canMeasureWater = function(x, y, target) {

    let stack = [[0,0]]

    let set = new Set()

    while(stack.length>0){       

        // 出栈,取出a和b的值

        let [a,b] = stack.shift()       

        // 循环结束条件

        if(a==target||b==target||a+b==target) return true

        // 已经出现过的水壶状态,进入下次循环

        if(set.has(''+[a,b])) continue

        //以下为分析中的六种情况

        if(a<x) stack.push([x,b])

        if(b<y) stack.push([a,y])

        if(a!=0) {

            stack.push([0,b])

            if(b!=y) {

                let diff = a+b<y?a:y-b

                stack.push([a-diff,b+diff])

            }

        }

        if(b!=0) {

            stack.push([a,0])

            if(a!=x) {

                let diff = a+b<x?b:x-a

                stack.push([a+diff,b-diff])

            }

        }

        // 将这次的[a,b]加入set

        set.add(''+[a,b])

    }

    return false

};

上一篇:Vue -- 总结 10


下一篇:Java和Ts构造函数的区别