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

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

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

问题描述

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

示例示例

输入

N = 15

输出

34

解释

Stepping numbers是1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21, 23, 32, 34。所以，第15个Stepping number是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)

第二种方法

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

算法

• 步骤1： − 定义队列来存储先前的数字。同时，定义一个临时整数变量。

• 步骤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个步进数时，第一种方法可能更耗时。