C++程式：查詢恢復後所有可能的IP地址

假設我們有一個只包含數字的字串，我們需要透過形成所有可能的有效IP地址組合來恢復它。我們知道有效的IP地址由四個整數（每個整數的範圍是0到255）組成，並用單個句點符號分隔。

因此，如果輸入類似於ip = "25525511136"，則輸出將為["254.25.40.123", "254.254.0.123"]

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式convertToNum()，它將接收s、start、end作為引數。
  • num := 0
  • for i := start to end do −
    • num := (num * 10) + (s[i] - '0'的ASCII碼)
    • if num > 255 then −
      • return 10000
  • return num
  • 定義一個函式addDots()，它將接收positions作為引數。
  • res := 空字串
  • x := 0, posIndex := 0
  • for i := 0 to positions的長度-1 do −
    • num := positions[i]
    • 建立一個字串str1
    • temp := num轉換為字串
    • res := res + temp
    • if i < positions的長度-1 then −
      • res := res + "."
  • return res
  • 定義一個函式solve()，它將接收s、一個字串陣列result、一個數組positions、dotCount（初始化為3）、startIndex（初始化為0）作為引數。
  • if dotCount != 0 and ((s的長度 - 1) - startIndex + 1) >= 4 then −
    • temp := convertToNum(s, startIndex, s的長度 -1)
    • if temp >= 0 and temp <= 255 then −
      • 將temp新增到positions陣列的末尾
      • res := addDots(positions)
      • if res的長度等於s的長度 then −
        • 將res新增到result陣列的末尾
    • return
  • for i := startIndex to s的長度 -1 do −
    • temp := convertToNum(s, startIndex, i)
    • if temp >= 0 and temp <= 255 then −
      • 將temp新增到positions陣列的末尾
      • solve(s, result, positions, dotCount - 1, i + 1)
      • 從positions陣列中刪除最後一個元素
  • 定義一個函式genIp()，它將接收一個字串s作為引數
  • 定義一個數組result
  • 定義一個數組position
  • solve(s, result, position)
  • return result
  • 在主方法中呼叫genIp(A)

示例 (C++)

讓我們看看下面的實現來更好地理解：

 線上演示

#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:
   lli convertToNum(string s,int start, int end){
      lli num = 0;
      for (int i = start; i <= end; i++) {
         num = (num * 10) + (s[i] - '0');
         if (num > 255)
            return 10000;
      }
      return num;
   }
   string addDots(vector <int> positions){
      string res = "";
      int x = 0;
      int posIndex = 0;
      for (int i = 0; i < positions.size(); i++) {
         int num = positions[i];
         ostringstream str1;
         str1 << num;
         string temp = str1.str();
         res += temp;
         if (i < positions.size() - 1)
            res += ".";
         }
         return res;
      }
      void solve(string s, vector <string> &result,vector <int> positions, int dotCount = 3, int startIndex = 0){
         if (!dotCount && ((s.size() - 1) - startIndex + 1) >= 1) {
            int temp = convertToNum(s, startIndex, s.size() - 1);
            if (temp >= 0 && temp <= 255) {
               positions.push_back(temp);
               string res = addDots(positions);
               if (res.size() - 3 == s.size()) {
                  result.push_back(res);
            }
         }
         return;
      }
      for (int i = startIndex; i < s.size(); i++) {
         int temp = convertToNum(s, startIndex, i);
         if (temp >= 0 && temp <= 255) {
            positions.push_back(temp);
            solve(s, result, positions, dotCount - 1, i + 1);
            positions.pop_back();
         }
      }
   }
   vector<string> genIp(string s){
   vector<string> result;
   vector<int> position;
   solve(s, result, position);
   return result;
   }
   vector<string> get_ip(string A) {
   return genIp(A);
}};
main(){
   Solution ob;
   string ip = "25525511136";
   print_vector(ob.get_ip(ip));
}

輸入

25525511136

輸出

[255.255.11.136, 255.255.111.36, ]

更新於：2020年12月12日

285 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告