Re: [閒聊] 每日LeetCode

: 935. Knight Dialer : 西洋棋的騎士只能往前兩步後往左或右走一步 : 有一個撥號板如下圖 : https://assets.leetcode.com/uploads/2020/08/18/phone.jpg : 騎士只能站在數字上(藍色按鈕) : 回傳騎士在撥號板上能走的所有可能的數量mod 10^9+7 : Input: n = 1 Output: 10 : 每一格都可以踩 共十種 : Input: n = 2 Output: 20 : 所有可以走的路徑是 : [04, 06, 16, 18, 27, 29, 34, 38, 40, 43, : 49, 60, 61, 67, 72, 76, 81, 83, 92, 94] : Intuition: : : 之前好像也有遇到一題類似的題目 : 思路是把能走的路徑反轉思考成這格能從哪邊來 : 紀錄可能走到這一格的可能數並不斷重複計算就好 : Approach: : : 先定義所有可能走到此格的陣列 stepRefs : 例如 stepRefs[0] = [4, 6] : 代表號碼4跟號碼6可以走到號碼0 : 所以我們把號碼4的數量跟號碼6的數量加起來 : 就是號碼0下一步可能的所有數量 : 這一次我開始用FP去實現演算法 : 雖然速度稍微變慢了一點 : 但是可讀性up up : 不過還有可以改進的地方 : 現在會把資料傳進去 : 要想辦法改成只關注方法 : 另外之後還得自己實作compose跟curry : 下面兩種版本都放上去 : TS Code with FP: : const mod = 1000000007 : const stepRefs = [ : [4, 6], [6, 8], [7, 9], [4, 8], [3, 9, 0], : [], [1, 7, 0], [2, 6], [1, 3], [2, 4], : ] : function calculateNextStepElement (refIndexes: number[], prevArray: : number[]): number { : return refIndexes.reduce((result, index) => result + prevArray[index], 0) : } : function calculateNextStepArray (prevArray: number[]): number[] { : return stepRefs.map(stepRef => calculateNextStepElement(stepRef, prevArray) : % mod) : } : function calculate (n: number, arr: number[]): number[] { : return n === 1 ? arr : calculate(n - 1, calculateNextStepArray(arr)) : } : function knightDialer (n: number): number { : return calculate(n, new Array(10).fill(1)) : .reduce((result, currValue) => result + currValue) % mod : } : TS Code: : const mod = 1000000007 : const stepRefs = [ : [4, 6], [6, 8], [7, 9], [4, 8], [3, 9, 0], : [], [1, 7, 0], [2, 6], [1, 3], [2, 4], : ] : function knightDialer (n: number): number { : let currentStepArray = new Array(10).fill(1) : const calculateNextStepElement = (refIndexes: number[]): number => { : let nextStep = 0 : for (let i = 0; i < refIndexes.length; i++) { : nextStep += currentStepArray[refIndexes[i]] : } : return nextStep : } : for (let i = 1; i < n; i++) { : const newArray: number[] = new Array(10) : for (let i = 0; i < currentStepArray.length; i++) { : newArray[i] = calculateNextStepElement(stepRefs[i]) % mod : } : currentStepArray = newArray : } : let result = 0 : for (let i = 0; i < currentStepArray.length; i++) { : result += currentStepArray[i] : } : return result % mod : } Python Code: class Solution: def knightDialer(self, n: int) -> int: mod = 1000000007 #list = [[4,6],[6,8],[7,9],[4,8],[0,3,9],[],[0,1,7],[2,6],[1,3],[2,4]] list = [1,1,1,1,1,1,1,1,1,1] for i in range(1,n): prev_0 = list[4]+list[6] prev_1 = list[6]+list[8] prev_2 = list[7]+list[9] prev_3 = list[4]+list[8] prev_4 = list[0]+list[3]+list[9] prev_5 = 0 prev_6 = list[0]+list[1]+list[7] prev_7 = list[2]+list[6] prev_8 = list[1]+list[3] prev_9 = list[2]+list[4] list[0],list[1],list[2],list[3],list[4]=prev_0,prev_1,prev_2,prev_3,prev_4 list[6],list[7],list[8],list[9]=prev_6,prev_7,prev_8,prev_9 list[5] = prev_5 return sum(list) % mod 寫得滿醜的 思路跟1220差不多 等等看一下解答 姆咪 --
※ 批踢踢實業坊(ptt.cc), 來自: 114.43.157.170 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1701138742.A.78C.html

推 oin1104: 大師 11/28 10:39