[LeetCode] Maximum Value of K Coins From Piles

Maximum Value of K Coins From Piles

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

[LeetCode] Coin Change 2

Coin Change2

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

這是最後的結果

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

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

)。

接下來很重要的是把

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

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

我們可以先觀察在

時,
這樣的半狀態會得到:

這個的意思是,若是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]所暫存的表的

,可得知是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對照表

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

最後推得用[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。

這個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

結果如下

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

使用Charles抓取手機網路使用

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

  1. 將電腦和手機連上同一個WIFI網路
  2. 輸入ifconfig(MAC電腦)取得電腦的內網IP,如下圖可得知內網IP為192.168.1.104
  3. 設置Charles上的Proxy settings

  4. 設置手機上的WIFI的PROXY
  5. 此時即可在電腦上看到手機的網路使用狀況

好用的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

更多詳細的教學請見:官方教學

Pre-request scripts

如果我們希望每一次打出的某個變數能夠不一樣,這時可以撰寫pre-request scripts來達到這個目的,如下圖:

這時可以在傳送的參數裡用{{timestampHeader}}來存取timestampHeader這個變數

把儲存的測試API資料變成文件

在POSTMAN測試的資料可以轉換成精美的HTML API文件

更多資料請見官網

使用Postman API去自動化呼叫API測試

在下面的畫面裡按下『Get API Key』的按鈕可以取得呼叫API測試的密鑰

參考資料