C++ 中 N 位数阶梯数

在本文中，我们将讨论如何在 C++ 中查找 n 位跳跃数的数量。在进入程序之前，我们必须了解跳跃数。

什么是跳跃数？

跳跃数是指相邻数字之间只有一位差的数字。例如，在567中，相邻数字(5, 6, 7)之间存在连续的 1 差。

在这种情况下，我们将给定数字 N，我们的任务是计算所有 N 位跳跃数。

示例 1

输入

3

输出

32

说明

210, 123, 321, 456, 234, 345, 432, 454, 543, 567, 657, 678, 765, 789, 876, 987, 989.

示例 2

输入

4

输出

61

说明

3210, 1234, 2345, 3456, 4567, 5678, 6789, 7654, 8765, 9876.

我们将使用几种 C++ 方法来确定是跳跃数的 n 位数字的最大数量。我们还将讨论在空间优化方面的最佳解决方案。

方法 1：迭代法

• 为了确定一个数字是否是跳跃数，我们首先开发一个名为 steppingNumber 的函数。由于它是一个布尔函数，结果要么是 true，要么是 false。
• 在这种方法中，我们使用 to_string() 函数将数字转换为字符串。之后，通过遍历所有数字来确定每个数字之间的差。如果差不是 1，则为 false。如果不是，则结果为 true。
• 创建计算跳跃数的函数。在此函数中，我们从第一个 N 位数字迭代到最后一个 N 位数字。我们对每个数字使用 steppingNumber 函数。如果函数返回 true，则计数器值增加 1。

示例

让我们举一个例子来说明 C++ 中的跳跃数。

输出

方法 2：空间优化搜索

1. N 位跳跃数和 (N - 1) 位跳跃数的计数存储在两个数组中。
2. 循环从 2 迭代到 N。由于数字可以介于 0 到 9 之间，我们在此循环中执行两个循环，每个循环从 0 迭代到 9。我们使用 currentCount 数组中的数据来更新 previousCount 数组中每个数字的值。
3. 如果 (x > 0)，则将 previousCount[x- 1] 的值添加到 currentCount 数组。这是因为如果 (N - 1) 位数字的第一位等于 (ex- 1)，将其加一会得到 N 位跳跃数。
4. 如果 (x < 9)，则将 previousCount[x + 1] 的值添加到 currentCount 数组。这是因为如果第一位等于 (x + 1)，将 (N - 1) 位数字的第一位加一会得到 N 位跳跃数。
5. 然后将数组 currentCount 的值相加。

示例

让我们举一个例子来说明在 C++ 中使用空间优化搜索的跳跃数。

输出

方法 3：使用动态方法

示例

让我们举一个例子来说明在 C++ 中使用动态方法的跳跃数。

输出