資料科學小嫩嫩 10/19 - Day 23 Leetcode 62 unique paths
前篇: 資料科學小嫩嫩 10/19 - Day 23 Leetcode 70. climbing stairs
github : runtime 0ms, faster than 100%
在這邊介紹一個另外的解法.
大腦很神奇, 事隔多年, 看到這題, 仍會想起這是高中的組合數學.
因為可以往下走 m - 1 步, 往右走 n - 1 步, 每個地方都可以選擇往下或往右.
題目可以轉換為 有 m - 1 個 白球 和 n - 1 個 紅球, 把這些球排列組合,
有幾種可能性
而原本問題, 就會是寫 combination 數學函式.
在電腦中, 會有另一個問題是大數階乘, 很容易溢位超過, 而無法計算.
這有很多種做法, 有興趣可以深入繼續研究.
而 Leetcode 題目整數範圍有限制, 結果最大值會限制在 2 * 10^9.
所以在這邊簡單的用 long long, 並乘一個除一個輪流做來解決.
( 連續兩個整數相乘能被 2 整除, 連續三個整數香橙能被 3 整除 ... )
這題和前題不同的是在有阻礙物. 當遇到阻礙物時, 該路徑可能值為 0 (無法通過)
因此可以用遞迴法 + hashmap, 這樣遇到阻礙物時, 就可以將 0 回傳計算
類似前一題, 但阻礙物變成了取路徑最小值
recursive + hashmap / 動態規劃 / .. 都是不錯用的演算法.
而用數學找到對的方法時, 速度還能再大幅提升...
或許數字貨幣在有些地方也還能再改進,
留言
張貼留言