打印第 N 个阶梯数或自传数

---

在这个问题中，我们将打印第 N 个阶梯数。

解决该问题的朴素方法是遍历自然数，检查每个数是否为阶梯数，并找到第 N 个阶梯数。另一种方法可以使用队列数据结构。

问题陈述

我们给定一个正整数 N。我们需要打印第 N 个阶梯数。如果一个数的两个相邻数字之间的差为 1，则该数称为阶梯数。

示例

输入

N = 15

输出

34

解释

阶梯数为 1、2、3、4、5、6、7、8、9、10、12、21、23、32、34。因此，第 15 个阶梯数是 34。

输入

N = 2

输出

2

解释

1 到 10 位数都是阶梯数。

方法 1

在这种方法中，我们将遍历自然数，直到找到第 N 个阶梯数。为了找到阶梯数，我们将检查每个相邻数字的差。

算法

• 步骤 1 − 将 p 初始化为 1，并使用循环进行遍历，直到 n 大于 0。

• 步骤 2 − 在循环中，通过传递 p 作为参数调用 checkForStepping() 函数，以检查 p 是否为阶梯数。

• 步骤 2.1 − 在 checkForStepping() 函数中，将 num % 10 的值存储到表示前一个数字的 p_digit 中。同时，将 num 除以 10。

• 步骤 2.2 − 当 num 大于 0 时进行遍历。

• 步骤 2.3.1 − 将数字的最后一位数字存储在 c_digit 变量中。

• 步骤 2.3.2 − 如果 c_digit 和 p_digit 之间的绝对差值不为 1，则返回 false。

• 步骤 2.3.3 − 使用 c_digit 的值更新 p_digit，并将 num 除以 10。

• 步骤 3 − 如果该数字是阶梯数，则将 n 的值减 1。

• 步骤 4 − 将 p 的值加 1。

• 步骤 5 − 返回 p – 1，因为在最后一次迭代中，p 加 1。

示例

#include <bits/stdc++.h>
using namespace std;

bool checkForStepping(int num) {
   int p_digit = num % 10;
   num /= 10;
   while (num) {
      // Get the current digit
      int c_digit = num % 10;
      // Check the difference between adjacent digits
      if (abs(p_digit - c_digit) != 1)
         return false;
      p_digit = c_digit;
      num /= 10;
   }
   return true;
}
int NthSteppingNumber(int n) {
   int p = 1;
   // Finding N stepping numbers
   while (n > 0) {
      if (checkForStepping(p)) {
         n--;
      }
      p++;
   }
   return p - 1;
}
int main() {
   int N = 15;
   cout << "The Nth Stepping or Autobiographical number is " << NthSteppingNumber(N) << "\n";
   return 0;
}

输出

The Nth Stepping or Autobiographical number is 34

• 时间复杂度 − O(P)，其中 P 是我们需要遍历的自然数总数。

• 空间复杂度 − O(1)

方法 2

在这种方法中，我们将使用队列数据结构来存储先前的阶梯数。之后，我们将通过对先前的阶梯数执行乘法、加法和模运算来找到下一个阶梯数。

算法

• 步骤 1 − 定义队列以存储先前的数字。另外，定义 temp 整数变量。

• 步骤 2 − 将 1 到 10 的数字插入队列，因为它们是阶梯数。

• 步骤 3 − 现在，使用循环进行 N 次遍历。

• 步骤 3.1 − 从队列中弹出第一个元素。

• 步骤 3.2 − 如果该数字不能被 10 整除，则将 temp * 10 + temp % 10 − 1 插入队列。它从当前数字生成一个新的阶梯数。例如，如果当前数字是 2，则它生成 21。

• 步骤 3.3 − 如果 temp % 10 不等于 9，则将 temp * 10 + temp % 10 + 1 插入队列。它从 2 生成 23。

• 步骤 4 − 返回 temp 值。

示例

#include <bits/stdc++.h>
using namespace std;

int NthSteppingNumber(int K) {
   queue<int> que;
   int temp;
   // Insert 1 to 9
   for (int p = 1; p < 10; p++)
      que.push(p);
   for (int p = 1; p <= K; p++) {
      temp = que.front();
      que.pop();
      // When the number is not divisible by 10
      if (temp % 10 != 0) {
         que.push(temp * 10 + temp % 10 - 1);
      }
      // When the number doesn't contain 9 as a last digit
      if (temp % 10 != 9) {
         que.push(temp * 10 + temp % 10 + 1);
      }
   }
   return temp;
}
int main() {
   int N = 15;
   cout << "The Nth Stepping or Autobiographical number is " << NthSteppingNumber(N) << "\n";
   return 0;
}

输出

The Nth Stepping or Autobiographical number is 34

• 时间复杂度 − O(N)

• 空间复杂度 − O(N) 用于在队列中存储数字。

结论

在第一种方法中，我们需要进行 P 次遍历，但在第二种方法中，我们进行的遍历次数等于 N。当我们需要找到一个很大的阶梯数（例如第 10000 个阶梯数）时，第一种方法可能会更耗时。