数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学N位阶梯数的个数 - 空间优化方案
在本文中，我们将学习阶梯数。我们将使用多种C++技术来查找也是阶梯数的N位数的可能个数。我们还将讨论最节省空间的解决方案。
让我们首先讨论阶梯数。这些数字的相邻数字之间的差为1。例如，321 - 每个相邻数字 (3, 2, 1) 的差都连续为1。
在这里，我们将给出N的值，然后我们必须找到所有N位阶梯数的个数。
输入输出场景
给定N，输出为N位阶梯数的个数。
Input: N = 3 Output: 32 Input: N = 4 Output: 61
对于N = 3，可能的阶梯数是32。这些数字是101、121、123、210、212、232、234、321等等。
使用迭代
我们将迭代所有N位数，并检查它们是否是阶梯数。
首先，我们创建一个名为steppingNumber的函数，用于检查一个数是否是阶梯数。这是一个布尔函数，所以它返回true或false。
在这个函数中，我们使用to_string()将数字转换为字符串。然后，我们迭代所有数字，并找到每个数字之间的差。如果差值不为1，则返回false。否则，结果为true。
接下来，我们创建函数来计算阶梯数。在这个函数中，我们从第一个N位数迭代到最后一个N位数。对于每个数字，我们应用steppingNumber函数。如果函数返回true，则变量count加1。
示例
让我们看一个例子：
#include <iostream>
#include <cmath>
using namespace std;
bool steppingNumber(int i) {
string numStr = to_string(i);
for (int j = 1; j < numStr.length(); j++) {
int diff = abs(numStr[j] - numStr[j - 1]);
if (diff != 1) {
return false;
}
}
return true;
}
int possibleNumbers(int N) {
int begin = pow(10, N - 1);
int end = pow(10, N) - 1;
int count = 0;
for (int i = begin; i <= end; i++) {
if (steppingNumber(i)) {
count++;
}
}
return count;
}
int main() {
int N = 3;
cout << "Number of " << N << " digit stepping numbers are " <<
possibleNumbers(N);
return 0;
}
输出
Number of 3 digit stepping numbers are 32
注意 - 这种方法非常简单，效率不高。它会进行冗余计算，并且耗时更长。
使用空间优化方法
在这里，我们使用这样一个概念：在阶梯数中，每个数字都比前一个数字大1或小1。
我们有两个数组，它们分别存储N位阶梯数和(N – 1)位阶梯数的个数。
我们从2循环到N。在这个循环中，我们运行两个for循环，每个循环从0到9（因为数字可以在0-9之间）。对于每个数字，我们使用currentCount数组的值更新previousCount数组的值。
如果(k > 0)，我们将previousCount[k – 1]的值添加到currentCount数组。这是因为如果第一个数字等于(k – 1)，则将1加到(N – 1)位数字的第一个数字会得到N位阶梯数。
如果(k < 9)，我们将previousCount[k + 1]的值添加到currentCount数组。这是因为如果第一个数字等于(k + 1)，则将1加到(N – 1)位数字的第一个数字会得到N位阶梯数。
接下来，我们添加currentCount数组的值之和。
示例
以下是一个例子：
#include <iostream>
using namespace std;
int possibleNumbers(int N) {
int previousCount[10] = {0};
int currentCount[10] = {1, 1, 1, 1, 1, 1, 1 ,1, 1, 1};
for (int j = 2; j <= N; ++j) {
for (int k = 0; k <= 9; ++k) {
previousCount[k] = currentCount[k];
currentCount[k] = 0;
}
for (int k = 0; k <= 9; ++k) {
if (k > 0)
currentCount[k] += previousCount[k - 1];
if (k < 9)
currentCount[k] += previousCount[k + 1];
}
}
int count = 0;
for (int k = 1; k <= 9; ++k) {
count += currentCount[k];
}
return count;
}
int main() {
int N = 5;
cout << "Number of " << N << " digit stepping numbers are " <<
possibleNumbers(N);
return 0;
}
输出
Number of 5 digit stepping numbers are 116
使用动态规划方法
我们将使用单个一维数组来存储计算结果，而不是使用两个一维数组（如前面的方法）。
示例
#include <iostream>
#include <vector>
using namespace std;
long long possibleNumbers(int N){
vector<long long> dp(10, 1);
if (N == 1)
return 10;
for (int i = 2; i <= N; i++) {
vector<long long> new_dp(10, 0);
new_dp[0] = dp[1];
new_dp[9] = dp[8];
for (int j = 1; j <= 8; j++)
new_dp[j] = dp[j - 1] + dp[j + 1];
dp = new_dp;
}
long long totalCount = 0;
for (int j = 1; j <= 9; j++)
totalCount += dp[j];
return totalCount;
}
int main(){
int N = 4;
cout << "Number of " << N << " digit stepping numbers are " <<
possibleNumbers(N);
return 0;
}
输出
Number of 4 digit stepping numbers are 61
结论
我们讨论了查找N位阶梯数个数的不同方法。第一种方法是使用迭代的简单方法。第二种方法使用两个一维数组来存储计算结果，是一种空间优化的方案。在第三种方法中，我们使用单个一维数组代替两个这样的数组，这使得代码效率更高。
浏览量：122
