資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 中的 IP 地址還原
假設我們有一個只包含數字的字串，我們需要透過返回所有可能的有效 IP 地址組合來還原它。我們知道有效的 IP 地址由四個整數（每個整數的範圍為 0 到 255）組成，並用單個點隔開。
因此，如果輸入類似於“25525511135”，則輸出將為 ["255.255.11.135", "255.255.111.35"]
為了解決這個問題，我們將遵循以下步驟：
定義一個函式 `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) >= dotCount + 1 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)`
示例
讓我們看看下面的實現來更好地理解：
#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> restoreIpAddresses(string A) {
return genIp(A);
}};
main(){
Solution ob;
print_vector(ob.restoreIpAddresses("25525511135"));
}輸入
"25525511135"
輸出
[255.255.11.135, 255.255.111.35, ]
366 次瀏覽
