leetcode每日一题（20241210）
leetcode每日一题（20241210）本日依旧是棋盘类型的题目，但是本日的只是表面相关，看题：935.骑士拨号器 题目形貌：
象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个 L 的形状)。
象棋骑士可能的移动方式如下图所示:
我们有一个象棋骑士和一个电话垫，如下所示，骑士只能站在一个数字单元格上(即蓝色单元格)。
给定一个整数 n，返回我们可以拨多少个长度为 n 的不同电话号码。
你可以将骑士放置在任何数字单元格上，然后你应该执行 n - 1 次移动来获得长度为 n 的号码。所有的跳跃应该是有效的骑士跳跃。
因为答案可能很大，所以输出答案模 109 + 7.
https://i-blog.csdnimg.cn/direct/de8e45f646874ca9ae80f8ce76cf079f.png
这个题其实和题目没关系，把题目提炼一下就是，有一组数方向如下：
0--->{4,6} 4--->{3,9,0}
1--->{6,8} 5---->{}
2--->{7,9} 6--->{1,7,0}
3--->{4,8} 7--->{2,6}
8--->{1,3} 9--->{2,4}
给定长度，可以任意选起始元素，求有多少大概，看代码：
class Solution {
List<int[]> list=new ArrayList<>();
int n;
int mod=1000000007;
int[][] cache;
public int knightDialer(int n) {
this.n=n;
cache=new int;
initList();
int count=0;
for(int i=0;i<=9;i++){
count=(count+dfs(1,i))%mod;
}
return count;
}
public int dfs(int step,int num){
if(step==n){
return 1;
}
if(cache!=0){
return cache;
}
int count=0;
for(int next:list.get(num)){
count=(count+dfs(step+1,next))%mod;
}
return cache=count;
}
public void initList(){
list.add(new int[]{4,6});
list.add(new int[]{6,8});
list.add(new int[]{7,9});
list.add(new int[]{4,8});
list.add(new int[]{3,9,0});
list.add(new int[]{});
list.add(new int[]{1,7,0});
list.add(new int[]{2,6});
list.add(new int[]{1,3});
list.add(new int[]{2,4});
}
}
加油！！！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]