Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

ถัดไป Greater Element III ใน C++


สมมติว่าเรามีจำนวนเต็ม 32 บิตเป็นบวก เราต้องหาจำนวนเต็มที่น้อยที่สุดแบบ 32 บิตซึ่งมีตัวเลขเหมือนกันทุกประการในจำนวนเต็ม n และมีค่ามากกว่า n หากเราไม่มีจำนวนเต็มบวก 32 บิต ให้คืนค่า -1

ดังนั้นหากตัวเลขคือ 213 ผลลัพธ์จะเป็น 231

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

  • s :=n เป็นสตริง sz :=ขนาดของ s ตกลง :=false
  • สำหรับฉันอยู่ในช่วง sz – 2 ถึง 0
    • ถ้า s[i]
  • ถ้า of เป็นเท็จ ให้คืนค่า – 1
  • เล็กที่สุด :=i, curr :=i + 1
  • สำหรับ j ในช่วง i + 1 ถึง sz – 1
    • id s[j]> s[smallest] และ s[j] <=s[curr] จากนั้น curr :=j
  • แลกเปลี่ยน s[เล็กที่สุด] กับ s[curr]
  • aux :=สตริงย่อยของ s จากดัชนี 0 ถึงเล็กที่สุด
  • ย้อนกลับ aux
  • ret :=สตริงย่อยของ s จากดัชนี 0 ถึงเล็กที่สุด + aux
  • คืนค่า -1 ถ้า ret เป็น> 32-บิต +ve ช่วงจำนวนเต็ม มิฉะนั้น 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