首页 > 代码库 > [LeetCode]Restore IP Addresses
[LeetCode]Restore IP Addresses
审题很重要啊，对某些测试用例能否通过不清楚的时候还是先在RunCode里试一试得好。
我开始的时候没考虑0的情况，后来去考虑多个零的时候，我主观的认为零在前面的时候是要把它去掉变成合法的IP。
例如：“1000111”->“100.01.1.1”->“100.1.1.1”也是合法的IP，但其实题目认为不能去掉零，所以它是非法的情况。
我的思路大概是：
首先，将IP分为{第一个地址}.{第二个地址}.{第三个地址}.{第四个地址}
然后考虑点的位置来划分情况，第一个点从第一个字符的后面向后移动；
第二个点从第一个点的后一个位置开始向后移动，每次移动到最后时，第一个点在往后前进一步，第二个重新开始。
第三个点从后往前移动，当它到字符串尾的长度超过3(最大是255)时，算法结束了。
我在里面做了小小的优化，当第三个地址的长度大于3时，第一个点需要向前进一步，但是第二个点不用回到第一个点的后一位置，因为那样第三个地址一定非法。
1 class Solution {
2 public:
3 vector<string> restoreIpAddresses(string &str) {
4 int length = str.length();
5 vector<string> strs;
6 vector<int> dotPos(3);
7 vector<int>::iterator firstDot = dotPos.begin();//第一个点的位置
8 vector<int>::iterator lastDot = dotPos.begin();//第三个点的位置
9 vector<int>::iterator middleDot = dotPos.begin();//第二个点的位置
10 int dis_first_middle = 0, dis_middle_last = 0;
11 middleDot++;
12 advance(lastDot, 2);
13 *firstDot = 1;
14 *middleDot = 1;
15 *lastDot = length - 1;
16 do{
17 (*middleDot)++;
18 if (*middleDot - *firstDot > 3){//第二个地址的长度不能大于3
19 (*firstDot)++;
20 if (*firstDot > 3){
21 *firstDot = 1;
22 *middleDot = (*firstDot) + 3;
23 (*lastDot)--;
24 }
25 if (dis_middle_last <= 3)//当第三个地址的长度小于等于3时，第二个点才回到第一个点的后一位置
26 *middleDot = (*firstDot) + 1;
27 }
28 dis_first_middle = *middleDot - *firstDot;
29 dis_middle_last = *lastDot - *middleDot;
30 if (dis_first_middle < 4 && dis_middle_last < 4 && dis_first_middle > 0 && dis_middle_last > 0){
31 string s1 = str.substr(0, *firstDot);
32 int num = stringToInteger(s1);
33 if (s1.size() > 1 && s1.at(0) == 48) continue;//去掉前面是零的情况
34 if (*firstDot == 3){
35 if (num > 255) continue;
36 }
37 string s2 = str.substr(*firstDot, dis_first_middle);
38 num = stringToInteger(s2);
39 if (s2.at(0) == 48 && s2.size() > 1) continue;
40 if (dis_first_middle == 3){
41 if (num > 255) continue;
42 }
43 string s3 = str.substr(*middleDot, dis_middle_last);
44 num = stringToInteger(s3);
45 if (s3.size() > 1 && s3.at(0) == 48) continue;
46 if (dis_middle_last == 3){
47 if (num > 255) continue;
48 }
49 string s4 = str.substr(*lastDot, length - (*lastDot));
50 num = stringToInteger(s4);
51 if (s4.size() > 1 && s4.at(0) == 48) continue;
52 if (*lastDot + 3 <= length){
53 if (num > 255) continue;
54 }
55 string temp(s1 + "." + s2 + "." + s3 + "." + s4);
56 strs.push_back(temp);
57 }
58 } while (*lastDot + 3 >= length);
59 return strs;
60 }
61 private:
62 int stringToInteger(string s){//字符串转化为数字
63 istringstream istream(s);
64 int num;
65 istream >> num;
66 return num;
67 }
68 };
[LeetCode]Restore IP Addresses
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。