c++ - 生成直到给定数字 N 的步进数字

Question

如果数字中所有相邻数字的绝对差都为 1，则该数字称为步进数字。

步进数字示例:- 0,1,2,3,4,5,6,7,8,9,10,12,21,23,...

我必须生成直到给定数字 N 的步进数字。生成的数字应该按顺序排列。

我使用简单的方法将所有数字移动到 N 并检查它是否为步进数字。我的老师告诉我这是蛮力，需要更多时间。现在，我必须优化我的方法。

任何建议。

Answer 1

可以使用类似广度优先搜索的方法生成步进数。

示例查找从 0 到 N 的所有步进数

-> 0 是一个步进数字，它在范围内 所以显示它。 -> 1 是步进数，找到 1 的邻居，即 将10和12插入队列

如何得到10和12？

这里U为1 最后一位也是1

V = 10 + 0 = 10(添加 lastDigit - 1)

V = 10 + 2 = 12(加上 lastDigit + 1)

然后对 10 和 12 执行相同的操作，这将导致 101、123、121，但这些数字超出范围。 现在任何从 10 和 12 转换而来的数字都会产生 变成大于 21 的数字，所以无需探索 他们的邻居。

-> 2 是步进数，找到 2 的邻居，即 21、23。 -> 生成直到 N 的步进数。

其他步数为 3、4、5、6、7、8、9。

用于在给定范围内生成步进数字的 C++ 代码:

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

// Prints all stepping numbers reachable from num 
// and in range [n, m] 
void bfs(int n, int m) 
{ 
    // Queue will contain all the stepping Numbers 
    queue<int> q; 

    for (int i = 0 ; i <= 9 ; i++) 
        q.push(i);

    while (!q.empty()) 
    { 
        // Get the front element and pop from the queue 
        int stepNum = q.front(); 
        q.pop(); 

        // If the Stepping Number is in the range 
        // [n, m] then display 
        if (stepNum <= m && stepNum >= n) 
            cout << stepNum << " "; 

        // If Stepping Number is 0 or greater than m, 
        // need to explore the neighbors 
        if (stepNum == 0 || stepNum > m) 
            continue; 

        // Get the last digit of the currently visited 
        // Stepping Number 
        int lastDigit = stepNum % 10; 

        // There can be 2 cases either digit to be 
        // appended is lastDigit + 1 or lastDigit - 1 
        int stepNumA = stepNum * 10 + (lastDigit- 1); 
        int stepNumB = stepNum * 10 + (lastDigit + 1); 

        // If lastDigit is 0 then only possible digit 
        // after 0 can be 1 for a Stepping Number 
        if (lastDigit == 0) 
            q.push(stepNumB); 

        //If lastDigit is 9 then only possible 
        //digit after 9 can be 8 for a Stepping 
        //Number 
        else if (lastDigit == 9) 
            q.push(stepNumA); 

        else
        { 
            q.push(stepNumA); 
            q.push(stepNumB); 
        } 
    } 
}  

//Driver program to test above function 
int main() 
{ 
    int n = 0, m = 99; 

    // Display Stepping Numbers in the 
    // range [n,m] 
    bfs(n,m); 
    return 0; 
} 

访问此 link . 提到的链接同时具有 BFS 和 DFS 方法。 它将针对上述问题为您提供不同语言的解释和代码。