零基础 网站,简网app工场官网是不是不可以用了,如何建设网站知乎,屏蔽阿里云网站吗1 电话数字键盘问题
提供移动数字键盘。您只能按向上、向左、向右或向下至当前按钮的按钮。不允许您按最下面一行的角点按钮#xff08;即.*和##xff09;。 移动键盘
给定一个数N#xff0c;找出给定长度的可能数。
示例#xff1a;
对于N1#xff0c;可能的数字数为…
1 电话数字键盘问题
提供移动数字键盘。您只能按向上、向左、向右或向下至当前按钮的按钮。不允许您按最下面一行的角点按钮即.*和#。 移动键盘
给定一个数N找出给定长度的可能数。
示例
对于N1可能的数字数为100、1、2、3、…、9
对于N2可能的数字数为36
可能的数字00、08、11、12、14、22、21、23、25等等。
如果我们从0开始有效数字将是00、08计数2
如果我们从1开始有效数字将是11、12、14计数3
如果我们从2开始有效数字将是22、21、23、25计数4
如果我们从3开始有效数字将是33、32、36计数3
如果我们从4开始有效数字将是44,41,45,47计数4
如果我们从5开始有效数字将是55,54,52,56,58计数5
………………………………
………………………………
我们需要打印可能的数字。 推荐做法
移动数字键盘
试试看
N1是普通情况可能的数字数为100123…9
对于N1我们需要从某个按钮开始然后移动到四个方向向上、向左、向右或向下中的任何一个该方向指向有效的按钮不应转到*、#。继续这样做直到获得N个长度编号深度优先遍历。
递归解决方案
移动键盘是4X3的矩形网格4行3列
假设CountijN表示从位置ij开始的N个长度数字的计数
如果N1 ,计数ijN10
其他的 CountijN所有CountrcN-1之和其中rc是新的
长度1从当前有效移动后的位置
位置ij
下面是上述公式的三种实现代码。 2 源代码
using System;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{public static partial class Algorithm_Gallery{#region 算法1private static int MNKP_Solve_Utility(char[,] keypad, int i, int j, int n){if (keypad null || n 0){return 0;}if (n 1){return 1;}int[] row { 0, 0, -1, 0, 1 };int[] col { 0, -1, 0, 1, 0 };int totalCount 0;for (int move 0; move 5; move){int ro i row[move];int co j col[move];if (ro 0 ro 3 co 0 co 2 keypad[ro, co] ! * keypad[ro, co] ! #){totalCount MNKP_Solve_Utility(keypad, ro, co, n - 1);}}return totalCount;}public static int MNKP_Solve(char[,] keypad, int n){if (keypad null || n 0){return 0;}if (n 1){return 10;}int totalCount 0;for (int i 0; i 4; i) {for (int j 0; j 3; j) {if (keypad[i, j] ! * keypad[i, j] ! #){totalCount MNKP_Solve_Utility(keypad, i, j, n);}}}return totalCount;}#endregion#region 算法2public static int MNKP_Solve_2th(char[,] keypad, int n){if (keypad null || n 0){return 0;}if (n 1){return 10;}int[] row { 0, 0, -1, 0, 1 };int[] col { 0, -1, 0, 1, 0 };int[,] count new int[10, n 1];for (int i 0; i 10; i){count[i, 0] 0;count[i, 1] 1;}for (int k 2; k n; k){for (int i 0; i 4; i) {for (int j 0; j 3; j) {if (keypad[i, j] ! * keypad[i, j] ! #){int num keypad[i, j] - 0;count[num, k] 0;for (int move 0; move 5; move){int ro i row[move];int co j col[move];if (ro 0 ro 3 co 0 co 2 keypad[ro, co] ! * keypad[ro, co] ! #){int nextNum keypad[ro, co] - 0;count[num, k] count[nextNum, k - 1];}}}}}}int totalCount 0;for (int i 0; i 10; i){totalCount count[i, n];}return totalCount;}#endregion#region 算法3public static int MNTP_Solve_3th(char[,] keypad, int n){if (keypad null || n 0){return 0;}if (n 1){return 10;}int[] odd new int[10];int[] even new int[10];int useOdd 0;for (int i 0; i 10; i){odd[i] 1;}for (int j 2; j n; j){useOdd 1 - useOdd;if (useOdd 1){even[0] odd[0] odd[8];even[1] odd[1] odd[2] odd[4];even[2] odd[2] odd[1] odd[3] odd[5];even[3] odd[3] odd[2] odd[6];even[4] odd[4] odd[1] odd[5] odd[7];even[5] odd[5] odd[2] odd[4] odd[8] odd[6];even[6] odd[6] odd[3] odd[5] odd[9];even[7] odd[7] odd[4] odd[8];even[8] odd[8] odd[0] odd[5] odd[7] odd[9];even[9] odd[9] odd[6] odd[8];}else{odd[0] even[0] even[8];odd[1] even[1] even[2] even[4];odd[2] even[2] even[1] even[3] even[5];odd[3] even[3] even[2] even[6];odd[4] even[4] even[1] even[5] even[7];odd[5] even[5] even[2] even[4] even[8] even[6];odd[6] even[6] even[3] even[5] even[9];odd[7] even[7] even[4] even[8];odd[8] even[8] even[0] even[5] even[7] even[9];odd[9] even[9] even[6] even[8];}}int totalCount 0;for (int i 0; i 10; i){totalCount (useOdd 1) ? even[i] : odd[i];}return totalCount;}#endregion}
}3 源程序
using System; using System.Collections; using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm { public static partial class Algorithm_Gallery { #region 算法1 private static int MNKP_Solve_Utility(char[,] keypad, int i, int j, int n) { if (keypad null || n 0) { return 0; } if (n 1) { return 1; } int[] row { 0, 0, -1, 0, 1 }; int[] col { 0, -1, 0, 1, 0 }; int totalCount 0; for (int move 0; move 5; move) { int ro i row[move]; int co j col[move]; if (ro 0 ro 3 co 0 co 2 keypad[ro, co] ! * keypad[ro, co] ! #) { totalCount MNKP_Solve_Utility(keypad, ro, co, n - 1); } } return totalCount; } public static int MNKP_Solve(char[,] keypad, int n) { if (keypad null || n 0) { return 0; } if (n 1) { return 10; } int totalCount 0; for (int i 0; i 4; i) { for (int j 0; j 3; j) { if (keypad[i, j] ! * keypad[i, j] ! #) { totalCount MNKP_Solve_Utility(keypad, i, j, n); } } } return totalCount; } #endregion #region 算法2 public static int MNKP_Solve_2th(char[,] keypad, int n) { if (keypad null || n 0) { return 0; } if (n 1) { return 10; } int[] row { 0, 0, -1, 0, 1 }; int[] col { 0, -1, 0, 1, 0 }; int[,] count new int[10, n 1]; for (int i 0; i 10; i) { count[i, 0] 0; count[i, 1] 1; } for (int k 2; k n; k) { for (int i 0; i 4; i) { for (int j 0; j 3; j) { if (keypad[i, j] ! * keypad[i, j] ! #) { int num keypad[i, j] - 0; count[num, k] 0; for (int move 0; move 5; move) { int ro i row[move]; int co j col[move]; if (ro 0 ro 3 co 0 co 2 keypad[ro, co] ! * keypad[ro, co] ! #) { int nextNum keypad[ro, co] - 0; count[num, k] count[nextNum, k - 1]; } } } } } } int totalCount 0; for (int i 0; i 10; i) { totalCount count[i, n]; } return totalCount; } #endregion #region 算法3 public static int MNTP_Solve_3th(char[,] keypad, int n) { if (keypad null || n 0) { return 0; } if (n 1) { return 10; } int[] odd new int[10]; int[] even new int[10]; int useOdd 0; for (int i 0; i 10; i) { odd[i] 1; } for (int j 2; j n; j) { useOdd 1 - useOdd; if (useOdd 1) { even[0] odd[0] odd[8]; even[1] odd[1] odd[2] odd[4]; even[2] odd[2] odd[1] odd[3] odd[5]; even[3] odd[3] odd[2] odd[6]; even[4] odd[4] odd[1] odd[5] odd[7]; even[5] odd[5] odd[2] odd[4] odd[8] odd[6]; even[6] odd[6] odd[3] odd[5] odd[9]; even[7] odd[7] odd[4] odd[8]; even[8] odd[8] odd[0] odd[5] odd[7] odd[9]; even[9] odd[9] odd[6] odd[8]; } else { odd[0] even[0] even[8]; odd[1] even[1] even[2] even[4]; odd[2] even[2] even[1] even[3] even[5]; odd[3] even[3] even[2] even[6]; odd[4] even[4] even[1] even[5] even[7]; odd[5] even[5] even[2] even[4] even[8] even[6]; odd[6] even[6] even[3] even[5] even[9]; odd[7] even[7] even[4] even[8]; odd[8] even[8] even[0] even[5] even[7] even[9]; odd[9] even[9] even[6] even[8]; } } int totalCount 0; for (int i 0; i 10; i) { totalCount (useOdd 1) ? even[i] : odd[i]; } return totalCount; } #endregion } }
