資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告