C#，电话数字键盘问题（Mobile Numeric Keypad problem）的算法与源代码

1 电话数字键盘问题

提供移动数字键盘。您只能按向上、向左、向右或向下至当前按钮的按钮。不允许您按最下面一行的角点按钮（即.*和#）。


移动键盘

给定一个数N，找出给定长度的可能数。

示例：

对于N=1，可能的数字数为10（0、1、2、3、…、9）

对于N=2，可能的数字数为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）

………………………………

………………………………

我们需要打印可能的数字。

推荐做法

移动数字键盘

试试看！

N=1是普通情况，可能的数字数为10（0，1，2，3，…，9）

对于N>1，我们需要从某个按钮开始，然后移动到四个方向（向上、向左、向右或向下）中的任何一个，该方向指向有效的按钮（不应转到*、#）。继续这样做，直到获得N个长度编号（深度优先遍历）。

递归解决方案：

移动键盘是4X3的矩形网格（4行3列）

假设Count（i，j，N）表示从位置（i，j）开始的N个长度数字的计数

如果N=1 ,计数（i，j，N）=10

其他的 Count（i，j，N）=所有Count（r，c，N-1）之和，其中（r，c）是新的

长度1从当前有效移动后的位置

位置（i，j）

下面是上述公式的三种实现代码。

2 源代码

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
    }
}

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
    }
}
 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/433202.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

免费SSL证书有效期

免费SSL证书有效期

免费SSL证书有效期现状 目前市场上主流的免费SSL证书提供商大多遵循行业规范&#xff0c;将免费证书的有效期设为3个月。这意味着每隔三个月&#xff0c;网站管理员必须重新申请、验证并安装新的SSL证书&#xff0c;以维持网站的HTTPS安全连接状态。这种做法已成为行业的常态&…
阅读更多...
GEE入门篇|图像分类（一）：非监督分类

GEE入门篇|图像分类（一）：非监督分类

在非监督分类中&#xff0c;我们有与监督分类相反的过程。 首先对光谱类进行分组&#xff0c;然后将其分类为簇。因此&#xff0c;在 Earth Engine 中&#xff0c;这些分类器是 ee.Clusterer 对象。 它们是“自学”算法&#xff0c;不使用一组标记的训练数据&#xff08;即它们…
阅读更多...
C++复习笔记——泛型编程模板

C++复习笔记——泛型编程模板

01 模板 模板就是建立通用的模具&#xff0c;大大提高复用性&#xff1b; 02 函数模板 C另一种编程思想称为 泛型编程 &#xff0c;主要利用的技术就是模板 C 提供两种模板机制:函数模板和类模板 函数模板语法 函数模板作用&#xff1a; 建立一个通用函数&#xff0c;其函…
阅读更多...
centos上部署k8s

centos上部署k8s

环境准备 四台Linux服务器 主机名 IP 角色 k8s-master-94 192.168.0.94 master k8s-node1-95 192.168.0.95 node1 k8s-node2-96 192.168.0.96 node2 habor 192.168.0.77 镜像仓库 三台机器均执行以下命令&#xff1a; 查看centos版本 [rootlocalhost Work]# cat /…
阅读更多...
2024腾讯Java面试题精选，教你抓住面试的重点

2024腾讯Java面试题精选，教你抓住面试的重点

重要 大环境对于我们能力要求越来越高&#xff0c;医学专家又说今年冬天新冠肺炎将“席卷重来”。 如果疫情再次爆发&#xff0c;势必将再次影响企业的正常运作&#xff0c;一波裁员浪潮你又能否抗住&#xff1f; 不管如何&#xff0c;明年金三银四又是一波跳槽时机&#xf…
阅读更多...
数字化时代的新里程碑：Web3的革命

数字化时代的新里程碑：Web3的革命

在当今数字化时代&#xff0c;Web3正成为了一股强大的力量&#xff0c;重新定义了我们对互联网的认知。本文将深入探讨Web3的定义、特点&#xff0c;以及它对金融、供应链、社交媒体等领域的革命性影响&#xff0c;并展望Web3的未来发展。 1. Web3的定义与特点 Web3不仅是一种…
阅读更多...
力扣206反转链表

力扣206反转链表

206.反转链表 力扣题目链接(opens new window) 题意&#xff1a;反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 1&#xff0c;双指针 2&#xff0c;递归。递归参考双指针更容易写&#xff0c; 为什么不用头插…
阅读更多...
无代理方式实现VMware的迁移？详细解析

无代理方式实现VMware的迁移？详细解析

在当今数字化时代&#xff0c;数据的安全性和可用性对于企业至关重要。尤其是在VMware转变订阅策略后&#xff0c;原本永久订阅的产品转变为以年付费订阅的形式&#xff0c;导致客户不得不支付更多的费用&#xff0c;大幅增加了成本。同时&#xff0c;客户也对VMware未来发展前…
阅读更多...
计算机图形学的作用

计算机图形学的作用

计算机图形学的作用 计算机图形学的作用1.创造数字世界2.物理世界的仿真模拟2.1 三维几何2.2 物理动态2.3 人体运动2.4 虚实融合 3.仿真模拟与智能应用 笔记来源&#xff1a;GAMES001-图形学中的数学 计算机图形学的作用 1.创造数字世界 计算机图形学创造数字世界 数字世界…
阅读更多...
FEP容量瓶多应用于制药光电光伏行业

FEP容量瓶多应用于制药光电光伏行业

常用规格&#xff1a;25ml、50ml、100ml、250mlFEP容量瓶也叫特氟龙容量瓶&#xff0c;容量瓶是为配制一定物质的量浓度的溶液用的精确定容器皿&#xff0c;常和移液管配合使用。广泛用于ICP-MS、ICP-OES等痕量分析以及同位素分析等高端实验。地质、电子化学品、半导体分析测试…
阅读更多...
鸿蒙Harmony应用开发—ArkTS声明式开发（基础手势：TapGesture）

鸿蒙Harmony应用开发—ArkTS声明式开发（基础手势：TapGesture）

支持单击、双击和多次点击事件的识别。 说明&#xff1a; 从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 接口 TapGesture(value?: { count?: number, fingers?: number }) 参数&#xff1a; 参数名称参数类型必填参…
阅读更多...
【Android Studio】的矢量绘图【pathData】详解

【Android Studio】的矢量绘图【pathData】详解

目录&#xff1a; 例子老师&#xff1a;一、基础知识&#xff1a;1、命令和常数&#xff1a;2、绝对坐标和相对坐标&#xff1a; 一、落笔命令命令Mx&#xff0c;y和mx&#xff0c;y&#xff08;大小写绝对和相对&#xff09; 二、画直线命令Lx&#xff0c;y和lx&#xff0c;y&…
阅读更多...
Linux系统——LVS-DR群集部署及拓展

Linux系统——LVS-DR群集部署及拓展

目录 引言 1.LVS的工作模式及其工作过程 2.列举出LVS调度算法 3.LVS调度常见算法&#xff08;均衡策略&#xff09; 3.1固定调度算法:rr&#xff0c;wrr&#xff0c;dh&#xff0c;sh 3.2动态调度算法:wlc&#xff0c;lc&#xff0c;lblc 4.LVS三种工作模式区别 一、I…
阅读更多...
逆向实战33——某东登录参数与流程分析（包含滑块）

逆向实战33——某东登录参数与流程分析（包含滑块）

声明 本文章中所有内容仅供学习交流，抓包内容、敏感网址、数据接口均已做脱敏处理，严禁用于商业用途和非法用途，否则由此产生的一切后果均与作者无关，若有侵权，请联系我立即删除！ 目标网站 aHR0cHM6Ly9wYXNzcG9ydC5qZC5jb20vbmV3L2xvZ2luLmFzcHg/UmV0dXJuVXJsPWh0dHBzJ…
阅读更多...
CSS极速入门

CSS极速入门

CSS介绍 什么是CSS? CSS(Cascading Style Sheet),层叠样式表,用于控制页面的样式. CSS能够对网页中元素位置的排版进行像素级的精确控制,实现美化页面的效果.能够做到页面的样式和结构分离. CSS可以理解为"东方四大邪术"的化妆术. 对页面展示进行化妆. 基本语法规…
阅读更多...
PCM会重塑汽车OTA格局吗(2)

PCM会重塑汽车OTA格局吗(2)

目录 1.概述 2. PCM技术视角下的OTA 3.小结 1.概述 上一篇文章&#xff0c;我们着重讲解了OTA的概述内容&#xff0c;和意法半导体推出的跨域融合MCU的四大特征&#xff0c;其中就包含了OTA技术。 他们针对OTA做了比较创新的设计&#xff0c;在总的可用memory容量不变情况…
阅读更多...
Ansys Zemax | 如何在OpticStudio中建模DMD（MEMS）

Ansys Zemax | 如何在OpticStudio中建模DMD（MEMS）

附件下载 联系工作人员获取附件 什么是DMD/ MEMS 下图显示了一个DMD设备&#xff0c;它单独倾斜的微镜组成。镜子通常被称为像素。 如何在OpticStudio中建模DMD 这些设备可以在序列或非序列模式下建模。 如何计算单个像素/镜子的旋转 本节将说明如何设置单个像素的旋转。像…
阅读更多...
FEP样品瓶透明聚四氟乙烯取样瓶

FEP样品瓶透明聚四氟乙烯取样瓶

一、产品介绍 FEP试剂瓶&#xff0c;也叫FEP取样瓶、特氟龙样品瓶等&#xff0c;主要用于痕量分析、同位素检测&#xff0c;ICP-MS/OES/AAS分析等高端实验。本底值低&#xff0c;金属元素铅、铀含量小于0.01ppb,无溶出与析出。 常用尺寸&#xff08;ml&#xff09;&#xff1…
阅读更多...
2024大厂Java面试最火问题，1200页文档笔记

2024大厂Java面试最火问题，1200页文档笔记

前言 ⽂章有点⻓&#xff0c;请耐⼼看完&#xff0c;绝对有收获&#xff01;不想听我BB直接进⼊⾯试分享&#xff1a; 准备过程蚂蚁⾦服⾯试分享拼多多⾯试分享字节跳动⾯试分享最后总结个人所得&#xff08;供大家参考学习&#xff09; 当时我⾃⼰也准备出去看看机会&#…
阅读更多...
七、链表问题（上）

七、链表问题（上）

160、相交链表&#xff08;简单&#xff09; 题目描述 给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交&#xff1a; 题目数据 保证 整个…
阅读更多...
最新文章

Copyright @ 2022~2023