資料科學小嫩嫩 10/19 - Day 23 Leetcode 62 unique paths

 前篇: 資料科學小嫩嫩 10/19 - Day 23 Leetcode 70. climbing stairs


資料科學小嫩嫩

維元老師

Leetcode 62 unique paths

   github : runtime 0ms, faster than 100%


   在這邊介紹一個另外的解法. 


   大腦很神奇, 事隔多年, 看到這題, 仍會想起這是高中的組合數學. 

   因為可以往下走 m - 1 步, 往右走 n - 1 步, 每個地方都可以選擇往下或往右. 

   題目可以轉換為 有 m - 1 個 白球 和 n - 1 個 紅球, 把這些球排列組合, 

   有幾種可能性

   而原本問題, 就會是寫 combination 數學函式. 

   在電腦中, 會有另一個問題是大數階乘, 很容易溢位超過, 而無法計算. 

   這有很多種做法, 有興趣可以深入繼續研究. 

   而 Leetcode 題目整數範圍有限制, 結果最大值會限制在 2 * 10^9. 

   所以在這邊簡單的用 long long, 並乘一個除一個輪流做來解決. 

   ( 連續兩個整數相乘能被 2 整除, 連續三個整數香橙能被 3 整除 ... )


Leetcode 63 unique path II

    github

   這題和前題不同的是在有阻礙物. 當遇到阻礙物時, 該路徑可能值為 0 (無法通過)

    因此可以用遞迴法 + hashmap, 這樣遇到阻礙物時, 就可以將 0 回傳計算

   



Leetcode 64 Minimum Path Sum

   github

類似前一題, 但阻礙物變成了取路徑最小值



recursive + hashmap / 動態規劃 / .. 都是不錯用的演算法. 

而用數學找到對的方法時, 速度還能再大幅提升...

或許數字貨幣在有些地方也還能再改進,




留言

熱門文章