leetcode每日一题（20241210）

leetcode每日一题（20241210）本日依旧是棋盘类型的题目，但是本日的只是表面相关，看题：
935.骑士拨号器 题目形貌：

1. 象棋骑士有一个独特的移动方式，它可以垂直移动两个方格，水平移动一个方格，或者水平移动两个方格，垂直移动一个方格(两者都形成一个 L 的形状)。
2. 象棋骑士可能的移动方式如下图所示:
3. 我们有一个象棋骑士和一个电话垫，如下所示，骑士只能站在一个数字单元格上(即蓝色单元格)。
4. 给定一个整数 n，返回我们可以拨多少个长度为 n 的不同电话号码。
5. 你可以将骑士放置在任何数字单元格上，然后你应该执行 n - 1 次移动来获得长度为 n 的号码。所有的跳跃应该是有效的骑士跳跃。
6. 因为答案可能很大，所以输出答案模 109 + 7.

复制代码

这个题其实和题目没关系，把题目提炼一下就是，有一组数方向如下：

1. 0--->{4,6}               4--->{3,9,0}  
2. 1--->{6,8}               5---->{}   
3. 2--->{7,9}               6--->{1,7,0}
4. 3--->{4,8}               7--->{2,6}
5. 8--->{1,3}               9--->{2,4}

复制代码

给定长度，可以任意选起始元素，求有多少大概，看代码：

1. class Solution {
2.     List<int[]> list=new ArrayList<>();
3.     int n;
4.     int mod=1000000007;
5.     int[][] cache;
6.     public int knightDialer(int n) {
7.         this.n=n;
8.         cache=new int[n+1][10];
9.         initList();
10.         int count=0;
11.         for(int i=0;i<=9;i++){
12.             count=(count+dfs(1,i))%mod;
13.         }
14.         return count;
15.     }
16.     public int dfs(int step,int num){
17.         if(step==n){
18.             return 1;
19.         }
20.         if(cache[step][num]!=0){
21.             return cache[step][num];
22.         }
23.         int count=0;
24.         for(int next:list.get(num)){
25.             count=(count+dfs(step+1,next))%mod;
26.         }
27.         return cache[step][num]=count;
28.     }
31.     public void initList(){
32.         list.add(new int[]{4,6});
33.         list.add(new int[]{6,8});
34.         list.add(new int[]{7,9});
35.         list.add(new int[]{4,8});
36.         list.add(new int[]{3,9,0});
37.         list.add(new int[]{});
38.         list.add(new int[]{1,7,0});
39.         list.add(new int[]{2,6});
40.         list.add(new int[]{1,3});
41.         list.add(new int[]{2,4});
42.     }
43. }

复制代码

加油！！！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。