[LeetCode] Maximum Value of K Coins From Piles

這是遞迴方式的寫法, 但我可能存太多垃圾資訊,當k值變大之後,會發生heap allocation錯誤的問題,也受限於遞迴的限制當k變大效率非常差…..
看來又要動態規劃(哭), 晚點再來補上改善版

/**
 * @param {number[][]} piles
 * @param {number} k
 * @return {number}
 */
var maxValueOfCoins = function (piles, k) {
    let rootNode = new node(piles.length, k);
    let maxResult = addAllChildrenForThisNode(rootNode, piles, 0);
    console.log(rootNode.toObject())
    return maxResult
};
function addAllChildrenForThisNode(node, piles, maxResult) {
    for (let i = 0; i &lt; node.pilesPointer.length; i++) {
        if (node.pilesPointer[i] + 1 &lt; piles[i].length) {
            let y = node.pilesPointer[i] + 1;
            let newNode = node.addChild(piles[i][y], i, y);
            console.log(newNode.deep)
            if(newNode.deep &lt; newNode.maxSelectNum){
                maxResult = addAllChildrenForThisNode(newNode, piles, maxResult)
            }else{
                maxResult = Math.max(newNode.currentValue, maxResult)
            }
        }
    }
    return maxResult
}
function node(pilesNum, maxSelectNum) {
    this.currentValue = 0;
    //樹的鏈結資料
    this.deep = 0;
    this.parent = undefined;
    this.children = [];
    //x代表在哪個piles, y代表在該piles的深度
    this.indexX = undefined;
    this.indexY = undefined;
    //用來儲存這個node位置所有的piles的y座標
    this.pilesPointer = new Array(pilesNum).fill(-1);
    this.maxSelectNum = maxSelectNum;
    this.addChild = function (num, indexX, indexY) {
        let child = new node(this.pilesPointer.length, this.maxSelectNum);
        child.deep = this.deep + 1;
        child.parent = this;
        child.currentValue = this.currentValue + num;
        child.indexX = indexX;
        child.indexY = indexY;
        child.pilesPointer = this.pilesPointer.slice(0);
        child.pilesPointer[child.indexX] = indexY;
        this.children.push(child);
        return child
    }
    this.toObject = function () {
        let children = [];
        for (let child of this.children) {
            children.push(child.toObject())
        }
        return {deep:this.deep, value: this.currentValue , children: children}
    }
}

console.log(maxValueOfCoins([[80,62,78,78,40,59,98,35],[79,19,100,15],[79,2,27,73,12,13,11,37,27,55,54,55,87,10,97,26,78,20,75,23,46,94,56,32,14,70,70,37,60,46,1,53]],5))

/**

* @param {number[][]} piles

* @param {number} k

* @return {number}

var maxValueOfCoins = function (piles, k) {

let rootNode = new node(piles.length, k);

let maxResult = addAllChildrenForThisNode(rootNode, piles, 0);

console.log(rootNode.toObject())

return maxResult

};

function addAllChildrenForThisNode(node, piles, maxResult) {

for (let i = 0; i < node.pilesPointer.length; i++) {

if (node.pilesPointer[i] + 1 < piles[i].length) {

let y = node.pilesPointer[i] + 1;

let newNode = node.addChild(piles[i][y], i, y);

console.log(newNode.deep)

if(newNode.deep < newNode.maxSelectNum){

maxResult = addAllChildrenForThisNode(newNode, piles, maxResult)

}else{

maxResult = Math.max(newNode.currentValue, maxResult)

}

return maxResult

}

function node(pilesNum, maxSelectNum) {

this.currentValue = 0;

//樹的鏈結資料

this.deep = 0;

this.parent = undefined;

this.children = [];

//x代表在哪個piles, y代表在該piles的深度

this.indexX = undefined;

this.indexY = undefined;

//用來儲存這個node位置所有的piles的y座標

this.pilesPointer = new Array(pilesNum).fill(-1);

this.maxSelectNum = maxSelectNum;

this.addChild = function (num, indexX, indexY) {

let child = new node(this.pilesPointer.length, this.maxSelectNum);

child.deep = this.deep + 1;

child.parent = this;

child.currentValue = this.currentValue + num;

child.indexX = indexX;

child.indexY = indexY;

child.pilesPointer = this.pilesPointer.slice(0);

child.pilesPointer[child.indexX] = indexY;

this.children.push(child);

return child

}

this.toObject = function () {

let children = [];

for (let child of this.children) {

children.push(child.toObject())

}

return {deep:this.deep, value: this.currentValue , children: children}

}

console.log(maxValueOfCoins([[80,62,78,78,40,59,98,35],[79,19,100,15],[79,2,27,73,12,13,11,37,27,55,54,55,87,10,97,26,78,20,75,23,46,94,56,32,14,70,70,37,60,46,1,53]],5))

Claire's Blog

[LeetCode] Maximum Value of K Coins From Piles

發佈留言