資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究C++ 中的單調遞增數字
如果我們有一個非負整數 N，我們必須找到小於或等於 N 的最大數字，並且數字呈單調遞增。我們知道一個整數具有單調遞增的數字，當且僅當每一對相鄰的數字 x 和 y 滿足 x <= y。）因此，如果輸入類似於 332，則結果將為 299。
為解決這個問題，我們將遵循以下步驟 −
- s := N 作為字串、i := 1、n := s 的大小
- while i < n 且 s[i] >= s[i – 1]
- 增加 i 1 個
- 如果 i < n
- while i > 0 且 s[i – 1] > s[i]，那麼
- 減少 i 1 個
- 減少 s[i] 1 個
- while i > 0 且 s[i – 1] > s[i]，那麼
- 對於範圍 i + 1 到 n 的 j
- s[j] := ‘9’
- 返回 s 作為數字
讓我們看看以下實施以獲得更好的理解 −
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int monotoneIncreasingDigits(int N) {
string s = to_string(N);
int i = 1;
int n = s.size();
while(i < n && s[i] >= s[i - 1]) i++;
if( i < n)
while(i > 0 && s[i - 1] > s[i]){
i--;
s[i]--;
}
for(int j = i + 1; j < n; j++)s[j] = '9';
return stoi(s);
}
};
main(){
Solution ob;
cout << (ob.monotoneIncreasingDigits(332));
}輸入
332
輸出
299
更新時間： 2020-05-04
414 次瀏覽
廣告