在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ A chess knight can move as indicated in the chess diagram below: .
This time, we place our chess knight on any numbered key of a phone pad (indicated above), and the knight makes Each time it lands on a key (including the initial placement of the knight), it presses the number of that key, pressing How many distinct numbers can you dial in this manner? Since the answer may be large, output the answer modulo Example 1: Input: 1
Output: 10
Example 2: Input: 2
Output: 20
Example 3: Input: 3
Output: 46
Note:
国际象棋中的骑士可以按下图所示进行移动: .
每当它落在一个键上(包括骑士的初始位置),都会拨出键所对应的数字,总共按下 你能用这种方式拨出多少个不同的号码? 因为答案可能很大,所以输出答案模 示例 1: 输入:1 输出:10 示例 2: 输入:2 输出:20 示例 3: 输入:3 输出:46 提示:
284ms 1 class Solution { 2 func knightDialer(_ N: Int) -> Int { 3 var N = N 4 var mod:Int64 = 1000000007 5 N -= 1 6 var dp:[Int64] = [Int64](repeating: 1,count: 10) 7 for i in 0..<N 8 { 9 var ndp:[Int64] = [Int64](repeating: 0,count: 10) 10 ndp[0] = dp[4] + dp[6] 11 ndp[1] = dp[6] + dp[8] 12 ndp[2] = dp[7] + dp[9] 13 ndp[3] = dp[4] + dp[8] 14 ndp[4] = dp[3] + dp[9] + dp[0] 15 ndp[6] = dp[1] + dp[7] + dp[0] 16 ndp[8] = dp[1] + dp[3] 17 ndp[7] = dp[2] + dp[6] 18 ndp[9] = dp[2] + dp[4] 19 for j in 0..<10 20 { 21 ndp[j] %= mod 22 } 23 dp = ndp 24 } 25 var ret:Int64 = 0 26 for i in 0..<10 27 { 28 ret += dp[i] 29 } 30 return Int(ret % mod) 31 } 32 } 1296ms 1 class Solution { 2 func knightDialer(_ N: Int) -> Int { 3 let navigationMap: [Int: [Int]] = [0: [4, 6], 4 1: [6,8], 5 2: [7,9], 6 3: [4,8], 7 4: [3,9,0], 8 5: [], 9 6: [1,7,0], 10 7: [2,6], 11 8: [1,3], 12 9: [2,4]] 13 14 var currentPathsStats = [1,1,1,1,1,1,1,1,1,1] 15 for i in 1..<N { 16 var newStats = [Int](repeating: 0, count: 10) 17 for currentDigit in 0...9 { 18 let numberOfPathsToCurrentDigit = currentPathsStats[currentDigit] 19 for nextDigit in navigationMap[currentDigit]! { 20 newStats[nextDigit] = newStats[nextDigit] + numberOfPathsToCurrentDigit 21 if newStats[nextDigit] >= 1000000007 { 22 23 newStats[nextDigit] = newStats[nextDigit] - 1000000007 24 } 25 } 26 } 27 currentPathsStats = newStats 28 } 29 30 var result = 0 31 for i in 0...9 { 32 result = result + currentPathsStats[i] 33 if result >= 1000000007 { 34 35 result = result - 1000000007 36 } 37 } 38 39 // if N == 1 { 40 // result = result + 1 41 // } 42 43 return result 44 } 45 } 1532ms 1 class Solution { 2 func knightDialer(_ N: Int) -> Int { 3 var d = [[4, 6], [6, 8], [7, 9], [4, 8], [0, 3, 9], [], [0, 1, 7], [2, 6], [1, 3], [2, 4]] 4 let mod = 1000000007 5 var dp = [[Int]](repeating: [Int](repeating: 0, count: 10), count: N) 6 dp[0] = [Int](repeating: 1, count: 10) 7 guard N > 1 else { 8 return dp[0].reduce(0, +) 9 } 10 11 for i in 1 ..< N { 12 for j in 0 ... 9 { 13 let prev = d[j] 14 for k in prev { 15 dp[i][j] = (dp[i][j] + dp[i-1][k]) % mod 16 } 17 } 18 } 19 var sum = 0 20 for i in 0 ... 9 { 21 sum = (sum + dp[N-1][i]) % mod 22 } 23 return sum 24 } 25 } 2196ms 1 class Solution { 2 let modulo:Int = 1000000007 3 let availableNumbers: [Int:Set<Int>] = [ 4 0 : [4, 6], 5 1 : [6, 8], 6 2 : [7, 9], 7 3 : [4, 8], 8 4 : [0, 3, 9], 9 5 : [], 10 6 : [0, 1, 7], 11 7 : [2, 6], 12 8 : [1, 3], 13 9 : [2, 4] 14 ] 15 16 var moves:[Int:[Int:Int]] = [ 17 0:[0:1, 1:1, 2:1, 3:1, 4:1, 5:1, 6:1, 7:1, 8:1, 9:1], 18 1:[0:2, 1:2, 2:2, 3:2, 4:3, 5:0, 6:3, 7:2, 8:2, 9:2], 19 2:[0:6, 1:5, 2:4, 3:5, 4:6, 5:0, 6:6, 7:5, 8:4, 9:5] 20 ] 21 func knightDialer(_ N: Int) -> Int { 22 let dict = subDictFor(N-1) 23 var result = 0 24 for (_, value) in dict { 25 result += value 26 result %= modulo 27 } 28 return result 29 } 30 31 func subDictFor(_ movesCount: Int) -> [Int: Int] { 32 if let result = moves[movesCount] { 33 return result 34 } 35 36 let prevMoves = subDictFor(movesCount - 1) 37 var curMoves:[Int:Int] = [:] 38 for i in 0...9 { 39 var sum = 0 40 let nextSteps = availableNumbers[i]! 41 for nextStep in nextSteps { 42 sum += prevMoves[nextStep]! 43 } 44 sum %= modulo 45 curMoves[i] = sum 46 } 47 moves[movesCount] = curMoves 48 return curMoves 49 } 50 } 2476ms 1 class Solution { 2 func knightDialer(_ N: Int) -> Int { 3 var map: [Int64: Int64] = [0:1,1:1,2:1,3:1,4:1,6:1,7:1,8:1,9:1] 4 var sum: Int = 10 5 for n in (1..<N) { 6 let t = countLayer(map) 7 sum = t.0 8 map = t.1 9 //print(t) 10 } 11 12 return sum 13 } 14 15 func countLayer(_ map: [Int64: Int64]) -> (Int, [Int64: Int64]) { 16 var sum: Int64 = 0 17 var nextMap: [Int64: Int64] = [:] 18 for (key, value) in map { 19 var value = value % 1000000007 20 switch key { 21 case 0: sum += (Int64)(2 * value); 22 nextMap[6] = (nextMap[6] ?? 0) + value; 23 nextMap[4] = (nextMap[4] ?? 0) + value; 24 break; 25 case 1: sum += (Int64)(2 * value); 26 nextMap[6] = (nextMap[6] ?? 0) + value 27 nextMap[8] = (nextMap[8] ?? 0) + value; break; 28 case 2: sum += (Int64)(2 * value); 29 nextMap[7] = (nextMap[7] ?? 0) + value; 30 nextMap[9] = (nextMap[9] ?? 0) + value; break; 31 case 3: sum += (Int64)(2 * value); 32 nextMap[4] = (nextMap[4] ?? 0) + value; 33 nextMap[8] = (nextMap[8] ?? 0) + value; break; 34 case 4: sum += (Int64)(3 * value); 35 nextMap[0] = (nextMap[0] ?? 0) + value; 36 nextMap[3] = (nextMap[3] ?? 0) + value; 37 nextMap[9] = (nextMap[9] ?? 0) + value; break; 38 case 6: sum += (Int64)(3 * value); 39 nextMap[1] = (nextMap[1] ?? 0) + value; 40 nextMap[7] = (nextMap[7] ?? 0) + value; 41 nextMap[0] = (nextMap[0] ?? 0) + value; break; 42 case 7: sum += (Int64)(2 * value); 43 nextMap[2] = (nextMap[2] ?? 0) + value; 44 nextMap[6] = (nextMap[6] ?? 0) + value; break; 45 case 8: sum += (Int64)(2 * value); 46 nextMap[1] = (nextMap[1] ?? 0) + value; 47 nextMap[3] = (nextMap[3] ?? 0) + value; break; 48 case 9: sum += (Int64)(2 * value); 49 nextMap[4] = (nextMap[4] ?? 0) + value; 50 nextMap[2] = (nextMap[2] ?? 0) + value; break; 51 default: break 52 } 53 sum = sum % 1000000007 54 } 55 return (Int(sum % 1000000007), nextMap) 56 } 57 }
|
请发表评论