※ 引述《ZooseWu (动物园 公告)》之铭言：
: 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差不多
等等看一下解答 姆咪