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
}