資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 中的下一個更大元素 III
假設我們有一個正的 32 位整數 n，我們需要找到一個最小的 32 位整數，該整數恰好包含整數 n 中存在的相同數字，並且其值大於 n。如果沒有這樣的正 32 位整數，則返回 -1。
所以如果數字是 213，那麼結果將是 231。
為了解決這個問題，我們將遵循以下步驟：
- s := n 作為字串，sz := s 的大小，ok := false
- 對於 i 從 sz – 2 到 0 的範圍
- 如果 s[i] < s[i + 1]，則 ok := true 並中斷迴圈
- 如果 ok 為 false，則返回 – 1
- smallest := i，curr := i + 1
- 對於 j 從 i + 1 到 sz – 1 的範圍
- 如果 s[j] > s[smallest] 且 s[j] <= s[curr]，則 curr := j
- 交換 s[smallest] 和 s[curr]
- aux := 從索引 0 到 smallest 的 s 的子字串
- 反轉 aux
- ret := 從索引 0 到 smallest + aux 的 s 的子字串
- 如果 ret > 32 位正整數範圍，則返回 -1，否則返回 ret
讓我們看看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int nextGreaterElement(int n) {
string s = to_string(n);
int sz = s.size();
int i;
bool ok = false;
for(i = sz - 2; i >= 0; i--){
if(s[i] < s[i + 1]) {
ok = true;
break;
}
}
if(!ok) return -1;
int smallest = i;
int curr = i + 1;
for(int j = i + 1; j < sz; j++){
if(s[j] > s[smallest] && s[j] <= s[curr]){
curr = j;
}
}
swap(s[smallest], s[curr]);
string aux = s.substr(smallest + 1);
reverse(aux.begin(), aux.end());
string ret = s.substr(0, smallest + 1) + aux;
return stol(ret) > INT_MAX ? -1 : stol(ret);
}
};
main(){
Solution ob;
cout << (ob.nextGreaterElement(213));
}輸入
213
輸出
231
更新於：2020年5月4日
189 次瀏覽
廣告