Day15刷题复盘：字符串压缩、链表反转与快排的代码细节-北京尧图网络

今天是连续打卡的第十五天。说实话到Day10那会儿已经有点疲惫了但真正进入Day15之后反而找到了一个比较稳定的节奏不再追求一天刷很多题而是把代码题、英语翻译和单词打卡放进了同一个固定流程里每天稳步推进。今天做了三道代码题编号43到45另外按计划完成了两段英文翻译和20个新单词的打卡。这篇文章不是单纯贴题目和答案而是把今天的完整执行过程做个复盘。三道题分别对应字符串处理、链表操作和排序算法刚好覆盖了笔试面试中最基础也最容易被抠细节的三类考点。英语翻译我选了技术文摘里的长难句拆解过程也一并记录下来单词部分记录了我用的记忆法和今日清单。无论你是在刷题阶段还是想找一套可复用的每日学习流程这篇文章都可以直接参考。1. 今日学习内容总览与整体规划1.1 为什么代码题、翻译和单词要放在同一天完成多数人学习时有一个误区觉得一天应该只攻一个方向。我以前也试过一整天全泡在代码题里结果到下午脑子转不动效率断崖式下跌。后来调整为“代码题英语翻译单词打卡”的三件套效果反而好了很多。核心原因是大脑对不同类型任务的消耗路径不一样代码训练需要高强度的逻辑推理而英语翻译和单词记忆更多依赖语言的输入输出转换。两类任务交替进行实际上是一种主动休息。另一个原因是这类打卡本身就带有习惯养成属性。如果一天只做代码题遇到难题卡住时很容易产生挫败感导致当天直接断更。但把任务拆成三块之后哪怕代码题没能在预期时间内写出最优解翻译和单词部分依然能带来“今天完成了既定任务”的反馈。这种正反馈对长期坚持非常重要。今天的实际表现也验证了这一点三道题里第44题链表反转我在递归和迭代两种写法之间犹豫了很久但翻译部分意外的顺利整体心态一直很稳。1.2 Day15的执行排期我是怎么把三件事塞进一天的我目前的作息是早上头脑最清醒所以把最费脑子的代码题放在上午午休之后做英语翻译晚上睡觉前用半小时收尾单词打卡。今天的具体时间安排是这样的09:30 - 11:00三道代码题先独立思考再动手写最后对照参考实现复盘14:00 - 15:00英语翻译一段技术博客摘要和一个长难句精翻22:00 - 22:30单词打卡20个新词昨天的20个旧词快速回顾执行过程中我要求自己每道题都先手写思路不直接打开搜索引擎找答案。哪怕是见过很多次的快速排序我也要求自己先把边界条件写清楚再动手敲代码。这个习惯帮我避开了“看题觉得会写代码就废”的尴尬。另外每完成一个小任务我会在笔记软件里打一个勾这种可视化的进度反馈是我坚持到Day15的一个重要原因。2. 三道代码题的难点拆解与思路推导2.1 第43题字符串压缩边界条件比算法本身更考验人这道题的描述很简短给定一个字符串把连续出现的字符压缩成“字符出现次数”的形式。比如把aaabbcccc压缩成a3b2c4如果压缩后的字符串不比原字符串短就返回原字符串。乍看就是一次遍历的问题但实际写起来边界条件非常磨人。首先需要处理空字符串和单字符字符串这两种情况直接返回原串即可。其次是“压缩后长度不小于原串”的判断这里的比较要放在整个压缩完成之后再做不能边遍历边判断否则容易出现半截结果。在具体实现上我采用的是双指针方案一个指针负责遍历另一个指针记录写入位置这样可以避免额外开一块新的存储空间空间复杂度控制在O(1)。这道题真正的考察点在于“原地操作”和“边界判断”之间的平衡。如果你用Java或C的字符串拼接很容易写出新字符串再返回虽然能通过测试但在面试场景里会被追问空间复杂度。我建议养成“能原地就原地”的习惯尤其在字符串和数组类的题目里。2.2 第44题链表反转为什么我推荐先会递归再学迭代链表反转是一道经典题大部分人在初学阶段都背过迭代写法维护prev、curr、next三个指针一遍循环把每个节点的next指向前驱节点。但今天我想聊的是递归写法。递归解决链表反转的思路非常简洁假设当前节点后面的链表已经反转完成那么只需要让head.next.next head再把head.next置空即可。很多人在递归这里卡住是因为大脑试图去模拟每一层递归的调用过程。实际上递归版链表反转不需要你手动跟踪每一层的细节只需要相信“更短的子问题已经被正确处理”。这种思维方式的迁移价值很高后续处理二叉树、回溯算法时都能用上。我对这道题的建议是两种写法都要能默写。迭代版考察的是指针操作的熟练度递归版考察的是分治思维的理解深度。面试时如果只写出一种面试官大概率会让你补另一种。所以准备阶段不要偷懒。2.3 第45题快速排序换个写法性能差别巨大快速排序是排序算法里的常客几乎是所有算法课程必讲的排序。可正因为常见很多人反而只会背模板一旦要手写就漏洞百出。今天我在实现快排时重点关注的是partition过程。最简单的partition写法是选最左边元素作为哨兵然后从左往右扫描把小于哨兵的元素放到左边最后把哨兵交换到正确位置。这种写法实现容易但在输入近乎有序的情况下会退化到O(n²)。我今天实现时用了“三数取中”来选哨兵取区间左端、中间、右端三个元素的中位数作为pivot这样能在很大程度上避免最坏情况。快排的核心复杂度分析也值得多说两句。平均情况下时间复杂度是O(n log n)空间复杂度O(log n)但这个空间复杂度来自递归栈。非递归实现需要显式地维护一个栈来模拟递归过程实际工程中反而少见。多数使用场景下递归版加上随机化pivot已经足够应对。3. 完整题解与可运行代码含测试用例3.1 第43题完整代码双指针加原地写入我选用C来实现这一版核心逻辑简单直接#include iostream #include string using namespace std; string compressString(string S) { int n S.size(); if (n 2) return S; string res; int i 0; while (i n) { int j i; while (j n S[j] S[i]) j; res.push_back(S[i]); res to_string(j - i); i j; } return res.size() S.size() ? res : S; } int main() { string cases[] {aaabbcccc, abc, a, , aabbbbbbbbbbbbbbbbbbbbbbbbbbb}; for (auto s : cases) { cout s - compressString(s) endl; } return 0; }测试输出aaabbcccc - a3b2c4 abc - abc a - a - aabbbbbbbbbbbbbbbbbbbbbbbbbbb - a2b25这里两个容易踩的坑写在注释里第一是res.size() S.size()时要返回S不能返回res否则当压缩字符串更长时会输出错误结果第二是写to_string(j - i)时j - i是整数不能直接拼接到字符串里必须先转换类型。3.2 第44题完整代码两种解法对照我用Python来实现链表反转刚好可以更直观地对比两种写法。先看定义和迭代版class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def reverseList_iterative(head: ListNode) - ListNode: prev None curr head while curr: nxt curr.next curr.next prev prev curr curr nxt return prev递归版虽然代码量更少但理解门槛略高def reverseList_recursive(head: ListNode) - ListNode: if head is None or head.next is None: return head new_head reverseList_recursive(head.next) head.next.next head head.next None return new_head用一条1 - 2 - 3 - None的链表来测试两种写法返回的头节点都是原链表的尾节点打印结果一致。需要注意递归版在链表长度非常大时可能出现递归深度过大Python默认递归深度约1000层所以生产环境优先用迭代版。3.3 第45题完整代码随机化快排及验证由于今天选的是C路线第三题我也用C写了随机化快排。partition部分用最经典的挖坑法配合随机下标交换避免有序数组退化#include iostream #include vector #include cstdlib #include ctime using namespace std; int partition(vectorint arr, int low, int high) { int pivot arr[low]; while (low high) { while (low high arr[high] pivot) high--; arr[low] arr[high]; while (low high arr[low] pivot) low; arr[high] arr[low]; } arr[low] pivot; return low; } void quickSort(vectorint arr, int low, int high) { if (low high) return; int idx low rand() % (high - low 1); swap(arr[low], arr[idx]); int p partition(arr, low, high); quickSort(arr, low, p - 1); quickSort(arr, p 1, high); } int main() { srand(time(0)); vectorint arr {5, 3, 8, 6, 2, 7, 1, 4}; quickSort(arr, 0, arr.size() - 1); for (int x : arr) cout x ; cout endl; return 0; }输出为1 2 3 4 5 6 7 8。这里的rand() % (high - low 1)用来生成low到high范围内的随机下标保证pivot的选取不依赖输入顺序。我第一次写的时候漏了把随机选中的元素交换到low位置结果partition里取arr[low]时拿到的还是原值随机化完全失效。这个细节建议关注一下。4. 英语翻译实操一个长难句的拆解全过程4.1 今日例句与我的三步拆解法今天翻译的句子来自一篇讲算法评估的技术博客原句如下While the algorithm guarantees an optimal solution under idealized assumptions, its practical performance often depends on the choice of hyperparameters and the quality of the input data, which makes empirical evaluation an indispensable part of the development pipeline.面对这种长难句我习惯用三步拆解法第一步抓主干找到主谓宾第二步划分从句和修饰成分第三步调整语序让译文符合中文表达习惯。这个句子的主干是its practical performance often depends on the choice of hyperparameters and the quality of the input data。前面While the algorithm guarantees an optimal solution under idealized assumptions是让步状语从句后面which makes empirical evaluation an indispensable part of the development pipeline是非限制性定语从句修饰前面整个主句。理清结构之后翻译就比较顺畅了我的译文是尽管该算法在理想化假设下能够保证得到最优解但它的实际性能往往取决于超参数的选择和输入数据的质量因此经验性评估成为开发流程中不可或缺的一环。这里while翻译成“尽管”比生硬地翻译成“当……的时候”更符合语境。最后一个which从句如果不拆开处理中文会显得特别冗长所以改成“因此”来承接因果关系。4.2 翻译中比较容易失分的三个细节第一个细节是专业术语的准确性。hyperparameters必须翻译成“超参数”不能随意翻译成“高级参数”或“超级参数”。empirical evaluation在计算机领域的标准译法是“经验性评估”或“实证评估”翻译时尽量不要使用自创的说法。第二个细节是对under idealized assumptions的定位。很多初学者容易把它翻译成“在理想化的假设下运行”但其实它修饰的是整个前提不是算法本身。这类介词短语的位置在翻译时经常需要根据语义做调整。第三个细节是makes ... an indispensable part的翻译。这里不要把每个词都直译成“使……成为不可缺少的部分”适当换成“成为……中不可或缺的一环”更自然。翻译的最终目标是准确且通顺直译和意译之间的权衡需要靠积累。5. 单词打卡今日20词与记忆方案5.1 我一直在用的词根联想和间隔重复组合单词打卡如果只是机械地抄写效率非常低。我目前使用的方法是“词根联想”加“间隔重复”的组合。词根联想解决的是初记问题比如看到allocate先拆出al-这个前缀表示方向再结合loc表示地点整体就是“分配到某个地方”比死记“分配”要牢固得多。间隔重复解决的是遗忘问题。我每天早上新词的背诵周期是“第1天、第2天、第4天、第7天、第15天”各复习一遍。今天正好是Day15所以我的复习任务里包含了第一天学过的词这种“到期提醒”式的复习比我以前那种“考前一锅端”有效得多。5.2 今日单词清单及记忆锚点今天打卡的20个词都是编程和算法相关的高频词列在这里并附上助记线索方便我后续回顾单词中文义记忆锚点allocate分配al loc ate定位到某处ambiguous有歧义的ambi两边 guous两边都能解释approximate近似的ap proxim接近asymptotic渐进的指时间复杂度里的渐进符号cache缓存联想“藏着”compile编译把源码“塞”到一起变成机器码concurrency并发con共同 curr跑constant常数常数时间内记住了O(1)duplicate重复dupli双 cateempirical实证的靠经验而非纯理论iterate迭代iter再次 ateliteral字面量字面上的意思negative负的负数里的negativeoverflow溢出over超过 flow流pointer指针指出地址的东西recursion递归re反复 curr跑statement语句程序中的一个完整句stack栈后进先出的数据架子syntactically语法上syntax语法threshold阈值超过这个门限就触发这些词我在每天复习时都会给自己造句比如The recursion depth exceeds the threshold一句话既练了recursion也练了threshold远比孤立抄写单词高效。6. 常见问题与排查技巧实录6.1 三道题执行中踩过的bug与定位方法第43题我踩的第一个bug是忘记判断空字符串导致访问S[0]时越界。C里string的size()返回size_t类型当n 0时进入不了循环但如果先取S[0]就会出事。这类问题建议在所有字符串操作前加一个极短输入测试。第44题递归版链表反转比较容易出的问题是忘记head.next None导致链表成环。调试时可以通过打印每次递归返回后的链表长度来定位或者直接在关键节点输出val看访问顺序是否符合预期。我习惯在返回前打印一下head.val用肉眼确认它是否单调。第45题快排的随机化写法中我第一次忘记把随机选中的pivot交换到最左侧导致随机化没有生效。排查方法是在输入一个已经有序的数组时观察运行时间如果随机化失效有序数组的排序时间会显著变长。更直接的办法是打印每次选中的pivot值对比它是否为当前区间的边界元素。6.2 翻译和记单词的防忘技巧翻译练习最容易犯的错误是太着急写出译文结果把句子结构理解错。我现在给自己的规定是动笔之前必须先用笔划出主干和从句哪怕不写在纸上也要在心里默念一遍。这个习惯在今天的例句翻译里明显减少了回头修改的次数。单词记忆的防遗忘技巧除了间隔重复之外还有一个细节容易被忽略把单词放到语境里记。一个单词如果没有跟任何句子绑定它在你大脑中就是孤立的复习时很容易想不起来。我现在每个新词都会强制造一个跟技术有关的短句哪怕句子很粗糙也比没有强。比如cache我会记成The CPU cache speeds up memory access下次看到cache时大脑会自动调出这个画面。今天一整天的任务完成下来我能明显感觉到套路化刷题的疲惫感在降低取而代之的是一种“我知道自己在为什么而练”的清晰感。代码题考的是能否在有限时间内把思路变成无缺陷的实现翻译考的是能否快速理清复杂结构并准确转述单词考的是能否建立长期记忆。这三者表面上没什么关系实际上都是在训练同一个能力在给定约束下准确完成一件具体的事。这一天的打卡内容就整理到这里如果你也在用类似的学习节奏希望今天记录的三道题代码和翻译拆解过程能给你提供一点参考。

Day15刷题复盘：字符串压缩、链表反转与快排的代码细节

相关推荐

PyTorch AT_DISPATCH_V2 宏迁移实战：从 AT_DISPATCH_* 旧宏到新 Dispatch v2 API 的完整转换指南

物联网温湿度异常预警系统实战：MQTT+机器学习从0到1

MODBUS RTU从站调试实战：帧格式、寄存器映射与物理层排查指南

更多资讯

ChainUQ论文阅读总结

Ladders of Thought论文阅读总结

Mitigating LLM Over‑Refusal via Dynamic Semantic Routing Calibration 论文笔记

法考历年真题及答案解析合集pdf版（2002-2025年）

Folia 歌词动画播放器安装指南：Windows、macOS、Linux 三平台从取包到启动

用Python画二手玫瑰

今日更新

PLFM_RADAR：从被动告警到主动感知的微服务健康监控系统

SPI隔离设计实战：MAX14431BAEE+与STM32F407工业级应用

数字隔离器如何根治SPI通信地环路干扰：MAX14431与TM4C129实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？