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
}