数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++中的阶梯数
假设我们有两个整数 low 和 high，我们需要找到并显示范围 [low, high]（包括 low 和 high）内所有阶梯数的排序列表。阶梯数是指其所有相邻数字的绝对差都正好为 1 的整数。例如，321 是一个阶梯数，但 421 不是。因此，如果输入类似于 low := 0 和 high := 21，则结果将为 [0,1,2,3,4,5,6,7,8,9,10,12,21]
为了解决这个问题，我们将遵循以下步骤：
- 创建一个数组 temp
- 创建一个名为 solve() 的方法，它将接收 high、seed 和 len 作为参数。len 最初为 0。
- 如果 seed > high，则返回。
- 将 seed 插入到 temp 数组中。
- 如果 seed 为 0，则
- 对于 i 的范围从 1 到 9，执行 solve(high, i, 1)
- 否则
- lastDigit := seed mod 10
- 如果 lastDigit >= 1 且 len + 1 <= 10，则 solve(high, (seed*10) + lastDigit – 1, len + 1)
- 如果 lastDigit <= 8 且 len + 1 <= 10，则 solve(high, (seed*10) + lastDigit + 1, len + 1)
- 主方法将如下所示：
- solve(high, 0, 0)
- 对 temp 数组进行排序。
- 创建一个数组 ans。
- 对于 i 的范围从 0 到 temp 大小 – 1
- 如果 temp[i] >= low，则将 temp[i] 插入到 ans 中。
- 返回 ans。
让我们看看以下实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
typedef long long int lli;
class Solution {
public:
vector <lli> temp;
void solve(int high,lli seed=0, int len =0){
if(seed>high){
return;
}
temp.push_back(seed);
if(!seed){
for(int i =1;i<=9;i++){
solve(high,i,1);
}
} else {
int lastDigit = seed%10;
if(lastDigit>=1 && len+1<=10)
solve(high, (seed*10) + lastDigit-1,len+1);
if(lastDigit<=8 && len+1<=10)
solve(high, (seed*10) + lastDigit+1,len+1);
}
}
vector<int> countSteppingNumbers(int low, int high) {
solve(high);
sort(temp.begin(),temp.end());
vector <int> ans;
for(int i =0;i<temp.size();i++){
if(temp[i]>=low)ans.push_back(temp[i]);
}
return ans;
}
};
main(){
Solution ob;
print_vector(ob.countSteppingNumbers(0,40));
}输入
0 40
输出
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 21, 23, 32, 34, ]
更新于：2020年4月30日
284 次浏览
广告