一、題目描述
描述
原理：ip地址的每段可以看成是一個(gè)0-255的整數(shù)，把每段拆分成一個(gè)二進(jìn)制形式組合起來(lái)，然后把這個(gè)二進(jìn)制數(shù)轉(zhuǎn)變成
一個(gè)長(zhǎng)整數(shù)。
舉例：一個(gè)ip地址為10.0.3.193
每段數(shù)字 相對(duì)應(yīng)的二進(jìn)制數(shù)
10 00001010
0 00000000
3 00000011
193 11000001
組合起來(lái)即為：00001010 00000000 00000011 11000001,轉(zhuǎn)換為10進(jìn)制數(shù)就是：167773121，即該IP地址轉(zhuǎn)換后的數(shù)字就是它了。
數(shù)據(jù)范圍：保證輸入的是合法的 IP 序列
輸入描述：
輸入
1 輸入IP地址
2 輸入10進(jìn)制型的IP地址
輸出描述：
輸出
1 輸出轉(zhuǎn)換成10進(jìn)制的IP地址
2 輸出轉(zhuǎn)換后的IP地址
示例1
輸入：
10.0.3.193
167969729
輸出：
167773121
10.3.3.193
題目的主要信息：
- ip地址的每段可以看成是一個(gè)0-255的整數(shù)，把每段拆分成一個(gè)二進(jìn)制形式組合起來(lái)，然后把這個(gè)二進(jìn)制數(shù)轉(zhuǎn)變成一個(gè)長(zhǎng)整數(shù)
- 輸入需要將一個(gè)ip地址轉(zhuǎn)換為整數(shù)、將一個(gè)整數(shù)轉(zhuǎn)換為ip地址
解法1
我一開(kāi)始想到的思路是針對(duì)10.0.3.193這種點(diǎn)分十進(jìn)制的IP地址，將其轉(zhuǎn)換成字符串，然后按照字符.進(jìn)行分割，放入數(shù)組中，然后對(duì)數(shù)組中的4個(gè)數(shù)字進(jìn)行位運(yùn)算，最后進(jìn)行組合。而對(duì)于167969729這種長(zhǎng)整型的IP地址，進(jìn)行位運(yùn)算后依次得到點(diǎn)分十進(jìn)制中的每一項(xiàng)，以8位進(jìn)行右移運(yùn)算。具體的代碼如下：
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stdlib.h>
using namespace std;
vector<string> Split(const string& strInput, char split = '.')
{
vector<string> splitVec;
size_t len = strInput.size();
size_t start = 0;
size_t end = 0;
string strTemp = "";
size_t it = 0;
while ((it = strInput.find(split, start)) != string::npos && start < len) {
end = it;
strTemp = strInput.substr(start, end - start);
splitVec.push_back(strTemp);
start = end + 1;
}
splitVec.push_back(strInput.substr(start));
return splitVec;
}
long ConvertIp(const string& strIp)
{
long ip = 0;
vector<string> ipVec = Split(strIp, '.');
for (int i = 0; i < ipVec.size(); i++) {
long nTemp = atol(ipVec[i].c_str());
ip += nTemp << ((ipVec.size()-i-1) * 8); // 24 16 8
}
return ip;
}
string ConvertToIpString(long ip)
{
string strIp = "";
long nTemp = ip >> 24;
ip = ip - (nTemp << 24);
strIp += std::to_string(nTemp);
nTemp = ip >> 16;
ip = ip - (nTemp << 16);
strIp += ".";
strIp += std::to_string(nTemp);
nTemp = ip >> 8;
ip = ip - (nTemp << 8);
strIp += ".";
strIp += std::to_string(nTemp);
nTemp = ip;
strIp += ".";
strIp += std::to_string(nTemp);
return strIp;
}
int main() {
string strIp;
long ip;
while (cin >> strIp >> ip) { // 注意 while 處理多個(gè) case
cout << ConvertIp(strIp) << endl;
cout << ConvertToIpString(ip) << endl;
}
return 0;
}
解法二
借助scanf進(jìn)行接收輸入數(shù)據(jù)，然后對(duì)輸入數(shù)據(jù)進(jìn)行位運(yùn)算，如下所示：
#include <iostream>
using namespace std;
int main()
{
long long int a,b,c,d;
long long int num;
while(scanf("%lld.%lld.%lld.%lld",&a,&b,&c,&d)!=EOF){
cin>>num;
cout<<(a<<24)+(b<<16)+(c<<8)+d<<endl;
a = num>>24;
num = num-(a<<24);
b = num>>16;
num = num-(b<<16);
c = num>>8;
d = num-(c<<8);
cout<<a<<"."<<b<<"."<<c<<"."<<d<<endl;
}
}
上面的解法確實(shí)很巧妙，借助scanf函數(shù)直接接收輸入數(shù)據(jù)，這樣避免使用字符串處理輸入數(shù)據(jù)的麻煩。
解法三：逐位分割，逐位計(jì)算
具體做法：
對(duì)于兩個(gè)輸入，題目已明確表示第一個(gè)輸入是字符串型的IP地址，第二個(gè)輸入是整數(shù)，
我們就可以用一個(gè)string類(lèi)型和一個(gè)long型來(lái)接收（int會(huì)超）。
IP地址轉(zhuǎn)換整數(shù)，我們首先要將IP地址以點(diǎn)分割出來(lái)，將數(shù)組提取出來(lái)：
遍歷字符串，用變量記錄點(diǎn)出現(xiàn)的次數(shù)，剛好可以作為四個(gè)整數(shù)的下標(biāo)，
0次即第0個(gè)數(shù)組元素，1次即第1個(gè)數(shù)組元素，一一對(duì)應(yīng)，對(duì)于數(shù)字我們乘10累加記錄這個(gè)數(shù)字，
對(duì)于點(diǎn)我們統(tǒng)計(jì)次數(shù)即可。得到了四個(gè)整數(shù)，我們可以將第0個(gè)整數(shù)左移24位，使其成為32位二進(jìn)制的頭8個(gè)，
然后第1個(gè)整數(shù)左移16位，第2個(gè)整數(shù)左移8位，最后一個(gè)不變，四個(gè)數(shù)通過(guò)位或操作即可組裝在一起。
數(shù)字轉(zhuǎn)換成IP地址，我們我們也是通過(guò)位操作，即IP地址第一部分是數(shù)字右移24位后的大小，我們與后8位全1的數(shù)做位與運(yùn)算即可得到，中間添加點(diǎn)，第二部分是數(shù)字右移16位后與0xff位與，
第三部分是數(shù)字右移8位后與0xff位與，最后一部分是直接與0xff位與，每次只取相應(yīng)的8位。
具體的C++代碼如下：
#include<iostream>
#include<string>
using namespace std;
void toNum(string ip){
long num[4] = {0, 0, 0, 0};
int point = 0; //記錄點(diǎn)出現(xiàn)的次數(shù)
for(int i = 0; i < ip.length(); i++){ //遍歷ip字符串
if(ip[i] != '.'){ //通過(guò).分割
num[point] = num[point] * 10 + ip[i] - '0';
}else{
point++; //點(diǎn)數(shù)增加
}
}
long output = num[0] << 24 | num[1] << 16 | num[2] << 8 | num[3]; //位運(yùn)算組裝
cout << output << endl;
}
void toIP(long num){
string output = "";
output += to_string((num >> 24) & 0xff); //取第一個(gè)八位二進(jìn)制轉(zhuǎn)換成字符
output += ".";
output += to_string((num >> 16) & 0xff); //取第二個(gè)八位二進(jìn)制轉(zhuǎn)換成字符
output += ".";
output += to_string((num >> 8) & 0xff); //取第三個(gè)八位二進(jìn)制轉(zhuǎn)換成字符
output += ".";
output += to_string(num & 0xff); //取第四個(gè)八位二進(jìn)制轉(zhuǎn)換成字符
cout << output << endl;
}
int main(){
string ip;
long num;
while(cin >> ip >> num){ //默認(rèn)第一個(gè)是IP地址第二個(gè)是整數(shù)
toNum(ip);
toIP(num);
}
return 0;
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：O(1)，IP地址長(zhǎng)度一定，遍歷過(guò)程為常數(shù)時(shí)間，所有位運(yùn)算也是常數(shù)時(shí)間
- 空間復(fù)雜度：O(1)，輔助數(shù)組num為常數(shù)空間，其他都是必要空間
解法四：正則表達(dá)式+字符串流輸入輸出
具體做法：
我們不區(qū)分字符串還是數(shù)字，都將其看成字符串，檢查字符串中有沒(méi)有點(diǎn)，有點(diǎn)的就是ip地址，否則就是整數(shù)。
我們也不用遍歷字符串依次分割，我們可以用正則表達(dá)式直接匹配點(diǎn)將其替換成空格，然后用字符串流輸入stringstream以空格為界將其輸入到數(shù)組中成為數(shù)字，用方法三位運(yùn)算組裝成長(zhǎng)整數(shù)。
對(duì)于整數(shù)，我們也可以將其用流輸出的方式整理成字符串，然后輸出，轉(zhuǎn)換過(guò)程同方法三。
具體代碼如下：
#include<iostream>
#include<sstream>
#include<regex>
#include<string>
using namespace std;
int main(){
string s;
while(cin >> s){
if(s.find_first_of('.') != string::npos){ //查找到有.的就是IP地址
long num[4];
stringstream(regex_replace(s, regex("\\."), " ")) >> num[0] >> num[1] >> num[2] >> num[3]; //用正則表達(dá)式分割后輸入數(shù)組
long output = num[0] << 24 | num[1] << 16 | num[2] << 8 | num[3]; //位運(yùn)算組裝
cout << output << endl;
}else{ //否則是整數(shù)
long num;
stringstream(s) >> num; //流輸入轉(zhuǎn)數(shù)字
stringstream output;
output << ((num >> 24) & 0xff) << "." << ((num >> 16) & 0xff) << "." << ((num >> 8) & 0xff) << "." << (num & 0xff); //流輸出格式
cout << output.str() << endl; //轉(zhuǎn)字符串輸出
}
}
return 0;
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：O(1)，IP地址長(zhǎng)度一定，正則匹配和流輸入輸出為常數(shù)時(shí)間，所有位運(yùn)算也是常數(shù)時(shí)間
- 空間復(fù)雜度：O(1)，輔助數(shù)組num為常數(shù)空間，其他都是必要空間
