※ 引述《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差不多
等等看一下解答 姆咪