工作雜記隨筆 – Claire's Blog

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

[LeetCode] Coin Change 2

Coin Change2

這也是一題動態規劃的題目，但是比起上一題，上一題每一個暫時儲存的東西是有意義的，我們可以了解說每一個的暫時狀態是某個數字用所給的硬幣列表裡，能用最少數量達成答案的數目，但是這一題的中間狀態所儲存的真的就是『中間的狀態』，我是看著別人的答案去回推理論的，真的很難想像在遇到這樣的問題時，該用什麼角度去把複雜的問題拆分，並找尋出重複步驟並找到可暫存狀態來計算出最終結果。

這是最後的結果

var change = function(amount, coins) {
    let dp = new Array(amount+1).fill(0);
    dp[0]=1;
    for(let coin of coins){
        for(let i=coin;i<=amount;i++){
            dp[i]+=dp[i-coin];
        }
    }
    return dp[amount]
};

var change = function(amount, coins) {

let dp = new Array(amount+1).fill(0);

dp[0]=1;

for(let coin of coins){

for(let i=coin;i<=amount;i++){

dp[i]+=dp[i-coin];

}

return dp[amount]

};

大概解釋一下解題的思緒，首先就是最重要的，先設定一個暫存動態編程的序列

dp

，這裡面的值只是儲存一個暫時的狀態，讓我們在計算下一個值時可以拿前一個運算到一半的值來繼續運算，長度為amount+1（這樣才存的到

dp[amount]

1	dp[amount]

）。

接下來很重要的是把

dp[0]=1

dp[0]=1

, 這是所有計算的起點, 代表說在一個分解狀態下，若自己可以被自己整除，那就可以有一種解法

若題目是coins=[2,5,8], amount=16時：

我們可以先觀察在

coins:[2], amount:16

1	coins:[2], amount:16

時，
這樣的半狀態會得到：

dp = [1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]

1	dp = [1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1]

這個的意思是，若是coins只有2時，可以用2組成0, 2, 4, 6, 8, 10, 12, 14, 16，皆只有一種組法。

接下來我們再把5加進去，但是因為以coins=[2,5]來說，我們可以把任務拆細，若是要組成16，我們要避免掉重覆的狀態，也就是說
我們可以思考，因為5,5,2,2,2和2,2,5,5,2其實是相同的答案，以2,2,2,5,5來說，其實是單純用2coin*3個＝6和單純用5coin*2個＝10,
那麼就可以開始計算，用5和2共同組成的狀況下，五的分佈是如何呢？

amount為16，則5有可能有分成：1個5(這時會需要單純用2組成11)和2個5(這時會需要用2組成6)和3個5(這時會需要用2組成1)三種可能性，這時參照上面coins=[2]的dp，會知道用2組成11的狀況和用2組成1狀況是0個，代表只會增加2個5的狀況。

但是動態編程當然沒這麼容易思考（真哭），因為這邊的dp存的是一個暫時半狀態的對照表，會需要算出從5~16所有可用[2,5]組成的，需要較完整的對照表。

首先很重要的，為什麼要從五開始，因為一定要大於五才有可能可以用五組成結果，並且如同dp[0]一樣，dp[5]因為coins有5，一定會多一種5的組合法。
從上面的推論我們可以觀查到要知道有沒有機會使用5這個coins來組成結果，主要要觀察『要組成總數』減掉現有coin的面額的數字，能不能用2組成。

所以若要知道6能不能用[5,2]組成，就要查coins:[2]所暫存的表的

dp[6(要組數字）-5(現有硬幣)]＝dp[1]（能不能用2組成1） = 0

1	dp[6(要組數字）-5(現有硬幣)]＝dp[1]（能不能用2組成1） = 0

，可得知是0種可能，以此類推。
這邊非常重要的是一定要從小到大，因為才可以讓狀態累加，我們先得知5可以組成5，把dp[5]＝1(本來只有coins:2時是0)，而在算10時，才能得到dp[10-5]=1(得知可以使用5來組成10)，外加單純用2組成10的可能性（當coins=[2]時dp[10]為1），可知10這個數字可單純用5組成也可用[2,5]組成，所以共有2種可能性，然後把dp[10]更新為2

接著在算dp[15]時才能夠利用dp[15-5]=dp[10]=2，再加上當coins=[2]時的dp[15]＝0，得知dp[15]為2

以下為coins=[2,5]時的dp對照表

dp= [ 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 2]

1	dp= [ 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 2]

接下來就是再相同的步驟再把coin 8加進coins列表裡。以同樣的步驟和概念，就可以得到

dp=[1, 0, 1, 0, 1, 1, 1, 1, 2, 1, 3, 1, 3, 2, 3, 3, 4]

1	dp=[1, 0, 1, 0, 1, 1, 1, 1, 2, 1, 3, 1, 3, 2, 3, 3, 4]

最後推得用[2,5,8要組成16有四種可能性]

[LeetCode] Coin Change

https://leetcode.com/problems/coin-change

最近開始刷leetcode覺得思考這些邏輯問題還滿好玩的
第一個刷的是這個,他是一個動態規劃的題目

一般我們在思考的時候會去思考以錢幣為基準,例如1,3,5的錢幣要怎麼湊成11元,我們會拿1,3,5去隨機湊硬幣,但是當數值大了以後,要計算最小的錢幣組合就會變成很困難.

像這種極限求值就會需要將思考轉換過來, 我們可以一步步的拆解, 先了解1,3,5,若要組成1是用幾個(1個1),那組成2要用幾個(2個1),若要組成3要用幾個,到3時我們就會發現,3可以用”3個1″或”1個3″組成, 這時候就可以來比較誰用的硬幣比較少,然後把最小可組成的數字”1″存到可組成結果為3的陣列。
接下來在思考4的時候,我們就可以思考4減掉硬幣1,也就是3,的最小使用硬幣數量,那就代表我們使用3,再加上硬幣1,可以組成4。接下來算要組成6要幾個硬幣,6減掉硬幣3,可以拿到硬幣3要用幾個硬幣,所以就是硬幣3使用的硬幣數量+1。

var coinChange = function (coins, amount) {
    if (amount == 0) return 0;
    let amountRecord = []
    amountRecord[0] = 0
    lastExistResult = 0
    minCoin = Math.min(...coins);
    //紀錄這些硬幣能夠組合成的數值所使用的硬幣數, 並用這些數值來推算目標所需的硬幣
    for (var currentAmount = 1; currentAmount <= amount; currentAmount++) {
        amountRecord[currentAmount] = Infinity
        if (currentAmount + minCoin >= lastExistResult) {
            for (var coin of coins) {
                if (coin <= currentAmount) {
                    //尋找這一個數字可不可以用之前可組成的硬幣加上其中一個新的硬幣來滿足(以確認是最小的硬幣數目)
                    amountRecord[currentAmount] = Math.min(amountRecord[currentAmount], amountRecord[currentAmount - coin] + 1);
                }
            }
        }
        if (amountRecord[currentAmount] != Infinity) {
            lastExistResult = amountRecord[currentAmount];
        }
    }
    console.log(amountRecord)
    return amountRecord[amount] == Infinity ? -1 : amountRecord[amount]
};

var coinChange = function (coins, amount) {

if (amount == 0) return 0;

let amountRecord = []

amountRecord[0] = 0

lastExistResult = 0

minCoin = Math.min(...coins);

//紀錄這些硬幣能夠組合成的數值所使用的硬幣數, 並用這些數值來推算目標所需的硬幣

for (var currentAmount = 1; currentAmount <= amount; currentAmount++) {

amountRecord[currentAmount] = Infinity

if (currentAmount + minCoin >= lastExistResult) {

for (var coin of coins) {

if (coin <= currentAmount) {

//尋找這一個數字可不可以用之前可組成的硬幣加上其中一個新的硬幣來滿足(以確認是最小的硬幣數目)

amountRecord[currentAmount] = Math.min(amountRecord[currentAmount], amountRecord[currentAmount - coin] + 1);

}

if (amountRecord[currentAmount] != Infinity) {

lastExistResult = amountRecord[currentAmount];

}

console.log(amountRecord)

return amountRecord[amount] == Infinity ? -1 : amountRecord[amount]

};

這個JS的效能只贏了32.59%的人

覺得不太開心(?)
所以我把console.log拿掉,再把let amountRecord = []; amountRecord[0] = 0;改成一行let amountRecord = [0](是有沒有這麼無聊)

接著我突發奇想,想說若是這個數字可用硬幣湊齊, 下個數字如果小於最小的coins數字的話,可以省略(如硬幣是10,15,18, 但是要組成11,很明顯就不可能會有結果,因為11-10小於10)

PS: 但是測試後其實拿掉console.log影響最大XD

var coinChange = function (coins, amount) {
    if (amount == 0) return 0;
    let amountRecord = [0]
    lastExistResult = 0
    minCoin = Math.min(...coins);
    //紀錄這些硬幣能夠組合成的數值所使用的硬幣數, 並用這些數值來推算目標所需的硬幣
    for (var currentAmount = 1; currentAmount <= amount; currentAmount++) {
        amountRecord[currentAmount] = Infinity
        if (currentAmount + minCoin >= lastExistResult) {
            for (var coin of coins) {
                if (coin <= currentAmount) {
                    //尋找這一個數字可不可以用之前可組成的硬幣加上其中一個新的硬幣來滿足(以確認是最小的硬幣數目)
                    amountRecord[currentAmount] = Math.min(amountRecord[currentAmount], amountRecord[currentAmount - coin] + 1);
                }
            }
            if (amountRecord[currentAmount] != Infinity) {
                lastExistResult = amountRecord[currentAmount];
            }
        }
    }
    return amountRecord[amount] == Infinity ? -1 : amountRecord[amount]
};

var coinChange = function (coins, amount) {

if (amount == 0) return 0;

let amountRecord = [0]

lastExistResult = 0

minCoin = Math.min(...coins);

//紀錄這些硬幣能夠組合成的數值所使用的硬幣數, 並用這些數值來推算目標所需的硬幣

for (var currentAmount = 1; currentAmount <= amount; currentAmount++) {

amountRecord[currentAmount] = Infinity

if (currentAmount + minCoin >= lastExistResult) {

for (var coin of coins) {

if (coin <= currentAmount) {

//尋找這一個數字可不可以用之前可組成的硬幣加上其中一個新的硬幣來滿足(以確認是最小的硬幣數目)

amountRecord[currentAmount] = Math.min(amountRecord[currentAmount], amountRecord[currentAmount - coin] + 1);

}

if (amountRecord[currentAmount] != Infinity) {

lastExistResult = amountRecord[currentAmount];

}

return amountRecord[amount] == Infinity ? -1 : amountRecord[amount]

};

結果如下

好啦至少擊敗了72.28%的人,累了…先這樣吧XDD

使用Charles抓取手機網路使用

使用Charles抓取手機網路使用資訊

將電腦和手機連上同一個WIFI網路
輸入ifconfig（MAC電腦）取得電腦的內網IP，如下圖可得知內網IP為192.168.1.104
設置Charles上的Proxy settings
設置手機上的WIFI的PROXY
此時即可在電腦上看到手機的網路使用狀況

好用的API測試工具 – POSTMAN

軟體介紹

官方下載點 : https://www.getpostman.com/
Chrome 擴充功能版 : 下載連結

Postman 是一個可以模擬 HTTP Request 的工具，其中包含常見的 HTTP 的請求方式，例如： GET 、POST、PUT、DELETE，而它的主要功能就是能夠快速的測試你的 API 是否能夠正常的請求資料，並得到正確的請求結果。

使用帳號

使用帳號去同步設定，可以選擇新創一個帳號或者使用google帳號去同步在不同電腦裡的POSTMAN設定

這樣在不同電腦裡面，使用紀錄或者儲存的Collection等都可以被同步。

發送Request教學

在登入帳號後，按下左上方的＋New按鈕，會可以看到一個創建Request的畫面

有些API的網址會有變數，這時可以使用https://api.library.com/:entity/並且藉由下面這樣的設定來取代變數entity

在發送Request時，正確的header資訊非常重要，可在下面這個頁籤做設定

也可以選擇發送的模式是要使用POST或GET