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 < 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))