IPv6压缩地址还原：标记数组与滑动窗口两种字符串处理方案解析

IPv6压缩地址还原：标记数组与滑动窗口两种字符串处理方案解析

发布时间：2026/10/10 15:30:59
IPv6压缩地址还原：标记数组与滑动窗口两种字符串处理方案解析 1. 先把这个题目的本质看清楚考的不是IPv6协议是字符串组块处理做这个题之前我先把题目本身从头到尾吃透了。P2815这道题题面套了个IPv6地址压缩的壳但做过之后你会发现它真正在考的东西其实很直白给你一串已经压缩过的IPv6地址要求你按照规范把它展开成完整的8组十六进制形式。核心考点是两件事——字符串的分割与合并以及连续全零组的定位与处理。很多同学看到IPv6三个字就容易发怵下意识觉得要懂网络协议、要懂RFC文档。实际上这道题不需要你有任何网络基础你只需要把题面里给的几条规则当成纯粹的字符串变换规则来理解就行原始地址由8组十六进制数构成组与组之间以冒号分隔比如0000:0000:0000:0000:0000:0000:0000:0001每组内部的前导零可以省略所以0001可以写成1连续出现的全零组可以合并成一个::比如连续四组全零可以写成::如果原输入里已经出现了::就说明这个位置代表若干组全零题目保证输入是已经合法压缩过的地址你不需要考虑还原成多种可能的情况。也就是说这道题的输入可能是0:0:0:0:0:0:0:1可能是::1可能是1::也可能是2001:db8:0:0:0:0:2:1这种半压缩形态。你要做的就是把这个字符串还原成8组完整的、每组4位十六进制不足4位补前导0的标准形式。这里有一个隐藏的关键点给出的字符串里可能已经存在::也可能没有。如果没有::那说明这个字符串本身就是8组直接逐组补零输出即可如果有::说明从这里开始缺失了8 - 当前组数个全零组需要在输出时把缺失的部分补回来。题目保证压缩是合法的所以不需要做多余的判断。这道题在洛谷上的定位是普及/提高说实话算法本身不复杂但细节极多稍不留神就会在格式和边界处理上出错。接下来我先讲我做这个题时的整体设计思路再给出具体的实现代码和踩坑记录。2. 标记数组方案把压缩段还原转换成一次线性扫描与区间标记2.1 核心思路先找到::把它替换成 N 个零组我的第一版方案逻辑很朴素既然::代表着若干个全零组那我只需要找到::的位置计算出它到底代表几个零组然后把它展开成对应个数的0组就能把输入变成一个标准的、不含::的8组地址接下来逐组格式化输出就行了。具体步骤拆开来看读入字符串s检查s中是否存在::子串如果存在以::为分界点把s拆成左右两段left和right分别统计left和right中冒号分组的个数注意空串的边界情况计算出中间需要补的零组数量zeroGroups 8 - leftCount - rightCount按left 中间补的零组 right的顺序构造出完整的8组列表对每一组做前导零补齐补齐到4位然后用冒号连接输出。听着是不是很简单第一版我也觉得简单但一旦动手写代码问题马上就开始冒出来了。最烦人的边界情况有这么几种输入的地址就是::代表8组全是0即0:0:0:0:0:0:0:0输入的地址是::1此时left为空字符串leftCount是0right是1组输入的地址是1::此时right为空rightCount是0输入的地址是1::1此时左1右1中间补6组零输入的地址是1:2:3:4:5:6:7:8没有::直接就是8组。这些情况如果不逐一处理很容易在某个点RE或者WA。我第一版代码就是在::这种输入上翻车的因为我试图find(::)之后直接按位置截取结果左边和右边都是空串分割逻辑直接炸了。2.2 无::时的直通处理先讲简单的情况。如果整个字符串里根本找不到::那说明这个地址已经是以标准8组形式给出的只是每组内部可能有前导零省略我们的任务就只剩两件事按冒号把字符串切成8段每段不足4位的左侧补0补到4位用冒号连接后输出。这一步基本没什么坑唯一要注意的是C里按冒号分割的办法。我强烈建议不要用getline配合:分隔符来读因为如果字符串里存在::用getline读的时候空串会被跳过或产生奇怪的行为会让后续逻辑变得不可控。正确做法是手写一个简单的解析循环遍历字符串遇到冒号就切一刀把冒号之间的子串收集到vectorstring里。不过这里有一个细节如果字符串中间存在::你按冒号切分时会多出一个空串。比如1::2按冒号切分会得到[1, , 2]。这个空串其实就是::中间位置缺失的那一部分你无法只靠切分结果唯一确定它代表几个零组所以切分之前必须提前把::作为整体识别出来然后再做区间标记。这也是为什么我说标记数组因为你确实需要遍历整个字符串把哪些位置是压缩标记::这一点明确记录下来而不能只按字符流简单处理。2.3 有::时的定位与补零计算处理带::的输入时我的做法分这么几步第一步找到::的位置pos。用s.find(::)可以拿到起始下标注意这是::第一个冒号的位置不是第二个。第二步把左段和右段分别截出来string left s.substr(0, pos); string right s.substr(pos 2);第三步分别统计左右两段的组数。这里要小心如果left或right是空串说明这一侧根本没有组组数记为0否则按冒号切分后统计元素个数。int leftCount 0; if (!left.empty()) { leftCount countGroups(left); } int rightCount 0; if (!right.empty()) { rightCount countGroups(right); } int zeroCount 8 - leftCount - rightCount;这里countGroups就是把字符串按冒号切开后统计数量的函数。比如1:2:3返回31返回1。到了这一步你其实已经完成了标记的核心工作——你已经确定了压缩点::代表多少组零。接下来要做的就是把左段、中间补的零组、右段按顺序拼接成一个完整的8组列表。2.4 完整代码与格式化细节我给出的第一版完整代码如下C#include bits/stdc.h using namespace std; vectorstring split(const string str, char delim) { vectorstring res; string cur; for (char c : str) { if (c delim) { res.push_back(cur); cur.clear(); } else { cur.push_back(c); } } res.push_back(cur); return res; } string pad4(const string s) { if (s.size() 4) return s; return string(4 - s.size(), 0) s; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; cin s; vectorstring groups; size_t pos s.find(::); if (pos string::npos) { // 没有压缩标记直接切分成8组 groups split(s, :); } else { string left s.substr(0, pos); string right s.substr(pos 2); vectorstring leftGroups, rightGroups; if (!left.empty()) leftGroups split(left, :); if (!right.empty()) rightGroups split(right, :); int zeroCount 8 - (int)leftGroups.size() - (int)rightGroups.size(); for (auto g : leftGroups) groups.push_back(g); for (int i 0; i zeroCount; i) groups.push_back(0); for (auto g : rightGroups) groups.push_back(g); } bool first true; for (auto g : groups) { if (!first) cout :; cout pad4(g); first false; } cout endl; return 0; }说一下几个特别容易出问题的地方第一find(::)返回的是第一个冒号的位置不是第二个冒号的位置。所以substr(0, pos)截出来的是::左侧的内容substr(pos 2)截出来的是右侧内容。这里的2就是跳过两个冒号没错但也容易写成1——一旦写错右侧开头就会多出一个冒号后面的所有解析全部错位。第二空串的组数统计必须单独判断。如果直接对空串执行 split 逻辑按我的split实现会把空串本身当成一个元素导致组数多算。所以在写代码时我刻意加了if (!left.empty())的判断。第三zeroCount的取值范围。题目保证输入合法所以理论上zeroCount一定在0到8之间。但这里有个隐患如果输入里根本没有::但也不是完整的8组理论上不会出现但如果你没有提前判断::代码会走到split分支然后未必能凑出8组。所以我用的是if (pos string::npos)先行判断再走到对应分支避免两种逻辑互相干扰。2.5 标记数组方案的优缺点我用标记数组来称呼这个方案核心原因是你先把原始字符串中需要特殊处理的::标记出来再根据这个标记去构造输出结构。它不是严格意义上的数组标记状态但它体现的思想是显式记录特殊位置而不是在处理过程中临时判断。这个方案的优点是思路直白代码量少适合作为初版方案快速过样例不需要复杂的状态机也不容易在读入阶段踩坑逻辑分支清晰容易调试。缺点是你需要先把::单独找出来再走substr分割对什么时候左边为空、什么时候右边为空的边界情况要心里有数如果left或right内部还有需要解析的组你还得再写一层分割函数整个流程是先找点、再切开、再拼接对于追求一步到位的人来说会显得有点绕。我也是做完这个方案之后才去想滑动窗口方案的——不是为了炫技而是想看看有没有更简洁的处理方式。毕竟洛谷上有不少题目同样的逻辑换个实现角度踩坑点完全不同。3. 滑动窗口方案从找冒号到找组的思维切换3.1 为什么想到滑动窗口标记数组方案写完之后我拿着代码去跑了一遍样例AC了。但我心里其实不太满意每次都要substr、split、判断空串总觉得有点啰嗦。尤其是一想到如果题目换个形态比如要求同时输出多种可能的压缩方式那这版代码基本就废了。于是我开始想第二个方案能不能不显式找::而是通过一次扫描把8组字符串全部提取出来然后根据提取结果在输出时决定要不要补零这就引出了滑动窗口的思路。如果你把整个IPv6地址当成一个字符串流你会发现它天然就是一个用冒号分隔的组序列。如果我们忽略压缩标记::的特殊性单纯从左到右扫描遇到非冒号字符就累积到当前窗口遇到冒号就关闭当前窗口把窗口内容作为一个组存储遇到::时连续两个冒号当前窗口为空且后一个冒号又紧接着再来一次。但是这里有一个问题::里有两个连续的冒号你按遇到冒号就关闭窗口的逻辑处理时会得到左右两个空窗口。这两个空窗口本质上就对应着压缩点。你没法直接区分这个空窗口是合法还是非法——因为普通的::压缩地址里左右两侧的空窗口都有可能代表真实存在的零组位置。所以滑动窗口方案不能只处理关闭窗口这一种事件还需要维护一个连续冒号计数器来判断是否遇到了::。3.2 滑动窗口的状态设计我最终设计的滑动窗口逻辑是这样的我用两个指针i和j作为窗口的左右边界j从i开始向后移动直到遇到冒号或字符串末尾为止。同时维护一个布尔变量hasDoubleColon一旦发现连续两个冒号就置为真并且记录压缩点出现的位置。伪代码如下i 0 groups [] hasDoubleColon false while i s.length: j i while j s.length and s[j] ! :: j // 窗口内容为 [i, j) if j - i 0: groups.push_back(s.substr(i, j - i)) // 此时 s[j] 是冒号若 j length if j s.length: // 判断是否是 :: if j 1 s.length and s[j 1] :: hasDoubleColon true // 跳过两个冒号 i j 2 else: i j 1 else: break这里的关键设计是窗口内容[i, j)永远是一个组的字符串而hasDoubleColon这个状态位在一轮扫描中被全局记录。如果后面需要知道::到底在哪个位置、需要补多少个零组可以在输出阶段处理。到了输出阶段如果hasDoubleColon为真我就知道当前的groups数量一定小于8需要在适当的位置插入零组。但是——这里有个微妙的问题——你只凭groups的数量能否确定::应该插在哪个位置答案是不能。举个例子输入1::2和::1:2扫描之后groups都是[1, 2]数量都是2。但前者压缩点在中间输出应该是1:0:0:0:0:0:0:2后者压缩点在开头输出应该是0:0:0:0:0:0:1:2。如果只靠groups数量这两者会得到完全相同的输出——大错特错。所以滑动窗口方案必须额外记录压缩点的位置信息。我是这样做的在扫描到::的那一刻记录下当前已经收集的组数compressPos groups.size()。这样等到输出时我就知道在groups中的第compressPos个元素之前需要插入零组。3.3 滑动窗口方案的完整实现基于上面的设计完整代码写成这样#include bits/stdc.h using namespace std; string pad4(const string s) { if (s.size() 4) return s; return string(4 - s.size(), 0) s; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string s; cin s; vectorstring groups; int compressPos -1; // 压缩点前已有的组数-1表示未遇到 int n s.size(); int i 0; while (i n) { int j i; while (j n s[j] ! :) { j; } // 收集 [i, j) 这一组 if (j i) { groups.push_back(s.substr(i, j - i)); } if (j n) break; // 检测是否为 :: if (j 1 n s[j 1] :) { // 第一次遇到时记录压缩位置 if (compressPos -1) { compressPos (int)groups.size(); } i j 2; } else { i j 1; } } // 在 compressPos 处插入缺失的零组 if (compressPos ! -1) { int zeroCount 8 - (int)groups.size(); vectorstring result; for (int k 0; k compressPos; k) { result.push_back(groups[k]); } for (int k 0; k zeroCount; k) { result.push_back(0); } for (int k compressPos; k (int)groups.size(); k) { result.push_back(groups[k]); } groups result; } for (int k 0; k (int)groups.size(); k) { if (k 0) cout :; cout pad4(groups[k]); } cout endl; return 0; }我实测下来这个方案对于::、::1、1::、1::2、2001:db8::1这类输入都能正确输出。而且整段代码里不再有find(::)和substr的成对处理状态全部藏在一次线性扫描里。3.4 滑动窗口方案的踩坑点滑动窗口方案看起来优雅但我调试的时候踩了三个坑一个个说坑一压缩点位置的记录时机。我最初是在检测到::时记录compressPos groups.size()这个逻辑在::1压缩点在开头时是对的因为此时groups里一个组都没有groups.size()是0压缩点就在第0个元素之前。但在1::2这种场景里扫描完1之后才遇到::此时groups.size()是1压缩点就被记录为1——这意味着在groups[1]之前插入零组也就是在1和2之间插正确。但有一个特殊情况如果字符串里的压缩点不止一次出现怎么办题目保证输入合法所以最多出现一次::。但我写的if (compressPos -1)这个判断是为了防止重复记录如果输入意外出现两个::我的代码只会把第一个当成有效压缩点后面那个会被吞掉——但这不是本题该考虑的问题只是做防御性编程时要注意。坑二空组的收集问题。我的代码里写的是if (j i)才把窗口内容推进groups。如果j i说明窗口是空的可能是遇到了::的第二个冒号位置也可能是地址尾部的一个空组。由于题目保证合法这种空窗口不会在正常输入中作为有效组出现所以直接跳过是正确的。但如果输入形如1:2:3:4:5:6:7:尾部多一个冒号我的代码就会把这个空尾巴跳过导致组数不足8压缩点判断出错。好在题目不会给这种非法输入。坑三输出阶段的插入位置。我这里的做法是先把已有的groups拆成前半段和后半段在中间插入零组再重新拼成result。如果你直接往groups里insert要注意insert位置随着插入不断变化的问题。我建议干脆开一个新的result容器来装逻辑最清晰。做完这一版之后我发现两个方案本质上做的事情是一样的——都是先定位压缩点再计算缺失组数再补零输出。区别只在于定位压缩点的方式一个用find加substr一个用单次遍历加窗口维护。一个直觉上是先切开再处理一个是边扫边记。如果你问哪个更好我建议新手用第一版标记数组因为思路直接、不容易把状态搞丢如果你希望代码更接近流式处理、更便于扩展到其他题目第二版更顺手。4. 重建压缩地址时的易错细节补齐位数与冒号连接的顺序问题题目真正要求的是把压缩地址展开成完整地址所以输出格式在整个题目里占的分数比算法本身还高——很多人WA不是因为思路错而是因为格式错空格问题、位数问题、冒号数量问题。我在这里把格式化输出的细节单独拎出来因为这是最容易被忽略、但也最致命的部分。4.1 为什么要补齐到4位IPv6的标准表示中每组是4位十六进制数对应16位二进制。比如2001:0db8:0000:0000:0000:0000:0000:0001。题目要求我们输出完整形式所以每一组都必须占满4位不足4位就在左侧补0。这一步看起来简单但有一个天然陷阱原始输入里如果某组本身就是4位比如db8补成0db8那就不能动它如果原始输入里某组超过4位比如12345题目保证不会出现这种情况。所以正常情况下你只需要判断size() 4就补不需要考虑截断问题。补充一句组内字符一定是小写十六进制数字或a-f小写字母题目在格式上做了保证所以不需要处理大小写转换。4.2 拼接顺序先补零组再逐组输出很多同学在输出阶段犯的错误是先把groups补齐到8组然后拼接输出时忘了在组之间加冒号或者在开头/结尾多加了一个冒号。比如::1输入正确输出是0000:0000:0000:0000:0000:0000:0000:0001如果代码在循环里无脑在每个组后面加冒号最后就会多出一个尾部冒号——WA。我的处理方式统一为先构造完整的8组groups输出时用bool first控制分隔符使用:\n之类的写法时特别注意。bool first true; for (auto g : groups) { if (!first) cout :; cout pad4(g); first false; } cout \n;这个方法在输出任意数量元素时都不会多出分隔符是最稳的写法。不建议用for循环每次输出group :再在最后删掉尾部冒号——看着简单实际上很容易在处理空数组或特殊值时越界。4.3 中间补零组的数量计算细节补零组的数量是8 - 已提取组数但这里有一个很容易被忽略的边界——如果原输入没有::但你错误地认为它缺失若干组就会多补零组。所以代码里必须先判断是否真的遇到了::再决定要不要补零。在我的两版代码里这个判断分别体现在标记数组版pos ! string::npos决定走哪条分支滑动窗口版compressPos ! -1决定是否插入零组。一旦这个条件写错常见的后果是把完整地址再压缩一遍输出里混入多余的全零组。比如输入0001:0002:...:00088个非零组如果错误地走补零分支就会输出0001:0002:...:0008并且在某处插入0000直接错。4.4 二进制与十六进制组位数的关系给基础薄弱的同学我自己在初学这个问题时其实有一点是懵的为什么一组是4位十六进制这要从IPv6地址本身说起。IPv6地址总共128位分成8组每组16位。16位二进制数正好对应4位十六进制数因为4位二进制对应1位十六进制。所以每组标准化后必须是4位十六进制。这个8组 x 4位十六进制的结构是整个地址格式的根基理解了它很多边界条件都不用死记。比如为什么补零要补到8组因为128位固定长度压缩只是表示方式的省略展开时必须还原成完整的8组。我在做题时还专门验证了一下如果把0000写成单0加冒号也就是0:和:0能看懂吗能但这不是标准的完整形式答案里输出的必须是4位。这也是为什么输出阶段必须调用pad4不能偷懒直接原样输出。5. 对拍实测两组方案的边界用例对比与结果分析写完两版代码之后我没有急着提交而是先手动构造了一批边界用例逐个跑了一遍。这里把测试结果整理成表格方便大家自查时对照。输入标记数组版输出滑动窗口版输出判定::0000:0000:0000:0000:0000:0000:0000:0000同上通过::10000:0000:0000:0000:0000:0000:0000:0001同上通过1::0001:0000:0000:0000:0000:0000:0000:0000同上通过1::20001:0000:0000:0000:0000:0000:0000:0002同上通过1:2:3:4:5:6:7:80001:0002:0003:0004:0005:0006:0007:0008同上通过2001:db8::12001:0db8:0000:0000:0000:0000:0000:0001同上通过a:b:c:d::e000a:000b:000c:000d:0000:0000:0000:000e同上通过我特别验证了一下a:b:c:d::e这个输入因为它展示了普通组和压缩点共存的情况。::前有4组a、b、c、d后有1组e中间应该补3组零。两版代码都拿到了000a:000b:000c:000d:0000:0000:0000:000e符合预期。然后又测了几个容易出错的输入1:2:3:4:5:6::左6组右0组中间补2组零输出为0001:0002:0003:0004:0005:0006:0000:0000::1:2:3:4:5:6:7左0组右7组中间补1组零输出为0000:0001:0002:0003:0004:0005:0006:00071:2::3:4:5:6左2右4中间补2输出0001:0002:0000:0000:0003:0004:0005:0006。这几组用例的主要意义是确保压缩点前后组数之和不超过8并且补零位置正确。题目保证输入合法所以左右组数之和必然小于8否则::就没有存在的必要了但你在自己的实现里还是要做好这个假设的前提判断——万一以后题目变种不再保证合法性代码就需要加入非法输入检测。最后我还跑了一下洛谷自带样例AC。这个题时间上没有任何压力两种方案都是线性复杂度内存占用也极小哪怕输入字符串很长虽然IPv6标准最长是45字符左右也不会出问题。6. 标记数组 vs 滑动窗口两种方案的设计取舍总结写到这里我把两种方案放在一起做个对比方便你根据自身情况选型维度标记数组方案滑动窗口方案核心逻辑先find(::)再用substr拆左右段单次扫描提取组记录压缩点位置代码量略短略长但状态集中对初学者友好度高容易理解中等需要适应双指针思维扩展性差改动逻辑时要动好几处好可直接迁移到其他字符串组块问题踩坑点空串判断、substr 位置计算压缩点记录时机、空窗口跳过个人建议是如果你是第一次接触这种压缩标记还原类题目先用标记数组方案把正确逻辑跑通如果你已经比较熟练可以挑战滑动窗口方案顺便积累一套扫描提取状态标记的模板以后处理类似字符串题目会快很多。说个题外话我当初做这道题时最早的思路其实是想用stringstream按冒号读取把::当普通分隔符处理。结果测试::1时直接裂开——stringstream根本不保留空字段你压根不知道中间丢了几个冒号。后来才意识到这种题目必须自己显式地处理分隔符绝对不能依赖现成的按字符分割工具因为它们不会替你保留空窗口的信息。这个教训我后来在别的字符串题目里也反复遇到算是提前给大家排个雷。另外还想提醒一句不要在输出阶段玩花活。有人可能会想用printf(%04x, ...)之类的十六进制格式化输出但前提是你得先把字符串转换成整数而题目给的组有可能是a、b、c这样的十六进制字母转来转去反而容易出错。直接字符串补零是最稳的也最符合题目对输出格式的要求。最后再说一点关于判题体验这个题看起来只是个字符串处理题但它实际上是在训练你把规则精确翻译成代码的能力。IPv6压缩规则本身不难难的是每条规则之间互相影响——前导零省略影响组内长度压缩标记影响组间数量你要在还原时同时兼顾这两个维度。我做完这道题之后的最大体会是凡是涉及格式还原的题目先把标准形式长什么样在纸上画出来再写代码会比自己凭空想省力很多。如果你在照着我的代码理解的过程中发现哪里卡住了建议把输入2001:db8::1手动在纸上走一遍滑动窗口的流程把i、j、groups、compressPos四个量的变化记录下来走完一遍基本就通了。这道题没有算法上的高门槛真正的门槛全在动手调试的耐心上。希望这篇复盘对你有帮助。