C语言刷题日记 #6

C语言刷题日记 #72026.04.14-2026.04.21本周概览进入四月的第三周转专业申请的号角正式吹响了。4月15日至4月21日于我个人而言是异常忙碌的一周——我咬着牙改完了个人陈述的第九版提交了转专业申请表也终于确定分流志愿是高分子。尽管日程紧凑刷题这件事依然是雷打不动的。本周的刷题内容很有特色重点攻克了滑动窗口这个转专业机考的核心考点同时也穿插了哈希表、股票问题、买卖最佳时机等经典题型。从4月中旬开始我的算法练习进入了“查漏补缺针对性强化”阶段聚焦于那些在转专业机考中最高频的题型——滑动窗口和哈希表。本周练习主要涉及4月15日1. 两数之和哈希表4月16日2958. 最多 K 个重复元素的最长子数组带频次控制的滑动窗口4月17日209. 长度最小的子数组 / 713. 乘积小于 K 的子数组 / 1004. 最大连续1的个数 III / 2024. 考试的最大困扰度 / 2904. 最短且字典序最小的美丽子字符串 / 3258. 统计满足 K 约束的子字符串数量 I / 3795. 不同元素和至少为 K 的最短子数组长度滑动窗口大合集4月18日2441. 与对应负数同时存在的最大正整数哈希集4月19日121. 买卖股票的最佳时机一次扫描/动态规划4月20日2016. 增量元素之间的最大差值一次扫描4月21日624. 数组列表中的最大距离 / 1128. 等价多米诺骨牌对的数量 / 1679. K 和数对的最大数目哈希映射题目复盘1. 1. 两数之和我的代码int*twoSum(int*nums,intnumsSize,inttarget,int*returnSize){int*arr(int*)malloc(sizeof(int)*3);inti,j;*returnSize2;for(i0;inumsSize-1;i){for(ji1;jnumsSize;j){if(nums[i]nums[j]target){arr[0]i;arr[1]j;returnarr;}}}returnarr;}思路暴力双循环枚举所有数对。不足之处时间复杂度O ( n ) 2 O(n)^2O(n)2对于数组长度很大时会超时用三层数组大小申请但没有利用好内存缺少注释说明。改进方向哈希表法O ( n ) O(n)O(n)遍历数组对于每个数nums[i]判断target-nums[i]是否已在哈希表中typedefstruct{intkey;intval;}HashNode;// 复杂度更优但直接调库实现哈希表需要依赖uthashC语言调试略繁琐// 或者用数组法nums元素范围有限时int*twoSum(int*nums,intnumsSize,inttarget,int*returnSize){int*arr(int*)malloc(2*sizeof(int));*returnSize2;inthash[20001]{0};for(inti0;inumsSize;i){intcomplementtarget-nums[i];if(hash[complement10000]!0){arr[0]hash[complement10000]-1;arr[1]i;returnarr;}hash[nums[i]10000]i1;}returnarr;}2. 121. 买卖股票的最佳时机我的代码intmaxProfit(int*prices,intpricesSize){intret0,minPriceINT_MAX,right;for(right0;rightpricesSize;right){if(minPriceprices[right])retfmax(ret,prices[right]-minPrice);minPricefmin(minPrice,prices[right]);}returnret;}思路一次扫描维护历史最低价格计算当天价格与最低价的差价。不足之处判断条件if(minPriceprices[right])前后的顺序可以更清晰变量right作为循环索引但并未体现“滑动窗口”含义。改进方向交换顺序更好理解intmaxProfit(int*prices,intpricesSize){intminPriceINT_MAX,maxProfit0;for(inti0;ipricesSize;i){minPricefmin(minPrice,prices[i]);maxProfitfmax(maxProfit,prices[i]-minPrice);}returnmaxProfit;}3. 209. 长度最小的子数组我的代码intminSubArrayLen(inttarget,int*nums,intnumsSize){intleft,right,sum0,minINT_MAX;for(leftright0;rightnumsSize;){while(sumtargetrightnumsSize){sumnums[right];right;}while(sumtarget){minfmin(min,right-left);sum-nums[left];left;}}if(minINT_MAX)return0;returnmin;}思路双循环滑动窗口先右扩直到满足条件再左缩更新答案。不足之处当窗口内多个连续数满足条件时必须逐个左移指针否则可能错过更短的窗口滑动窗口对“正整数数组”有效但若允许负数本题不适用窗口长度最小化会失效。改进方向用while嵌套逻辑完整但是写成标准模板更清晰intminSubArrayLen(inttarget,int*nums,intnumsSize){intleft0,sum0,minLenINT_MAX;for(intright0;rightnumsSize;right){sumnums[right];while(sumtarget){minLenfmin(minLen,right-left1);sum-nums[left];left;}}returnminLenINT_MAX?0:minLen;}4. 713. 乘积小于 K 的子数组我的代码intnumSubarrayProductLessThanK(int*nums,intnumsSize,intk){if(k0)return0;intleft,right;longlongplus1,sum0;for(leftright0;rightnumsSize;right){plus*nums[right];while(leftrightplusk){plus/nums[left];left;}if(nums[right]k){sumright-left1;}}returnsum;}思路滑动窗口乘积小于k时计数当前窗口子数组数并累加。不足之处引入了if(nums[right]k)过滤冗余但这会跳过窗口内包含nums[right]但大于等于k的乘积计算可能导致漏计子数组处理k0的情况需要单独判断可读性需提升。改进方向统一滑动窗口每次计数子数组时相加right-left1intnumSubarrayProductLessThanK(int*nums,intnumsSize,intk){if(k1)return0;longlongproduct1;intleft0,count0;for(intright0;rightnumsSize;right){product*nums[right];while(productk)product/nums[left];countright-left1;}returncount;}5. 1004. 最大连续1的个数 III我的代码intlongestOnes(int*nums,intnumsSize,intk){intleft,right,sum00,max0;for(leftright0;rightnumsSize;right){sum0nums[right]0?1:0;maxfmax(max,right-left);while(sum0k){sum0-nums[left]0?1:0;left;}}returnfmax(max,right-left);}思路滑动窗口统计窗口内0的个数当0的个数大于k时移动左指针收缩窗口。不足之处right-left先求值再收缩可能导致长度统计偏差max在while之前更新可能记录过长窗口最终返回值需要和前一个计算合并。改进方向统一在右指针遍历过程中维护窗口内0的个数保证窗口内0的个数始终≤kintlongestOnes(int*nums,intnumsSize,intk){intleft0,maxLen0,zeroCount0;for(intright0;rightnumsSize;right){if(nums[right]0)zeroCount;while(zeroCountk){if(nums[left]0)zeroCount--;left;}maxLenfmax(maxLen,right-left1);}returnmaxLen;}6. 2024. 考试的最大困扰度我的代码intmaxConsecutiveAnswers(char*answerKey,intk){intsumF0,sumT0,max0,left,right;for(left0,right0;rightstrlen(answerKey);right){if(answerKey[right]T)sumT;elsesumF;maxfmax(max,right-left);while(sumTk){if(answerKey[left]T)sumT--;elsesumF--;left;}}maxfmax(max,right-left);sumFsumT0;for(left0,right0;rightstrlen(answerKey);right){if(answerKey[right]T)sumT;elsesumF;maxfmax(max,right-left);while(sumFk){if(answerKey[left]T)sumT--;elsesumF--;left;}}returnfmax(max,right-left);}思路两次滑动窗口分别统计T和F允许最多翻转k个。不足之处代码重复两次滑动窗口逻辑几乎一样可重构为函数多次调用strlen(answerKey)效率低max更新逻辑不统一。改进方向抽取maxConsecutiveChar函数处理单个字符intmaxConsecutiveChar(char*s,charch,intk){intleft0,maxLen0,count0,nstrlen(s);for(intright0;rightn;right){if(s[right]!ch)count;while(countk){if(s[left]!ch)count--;left;}maxLenfmax(maxLen,right-left1);}returnmaxLen;}intmaxConsecutiveAnswers(char*answerKey,intk){returnfmax(maxConsecutiveChar(answerKey,T,k),maxConsecutiveChar(answerKey,F,k));}7. 2958. 最多 K 个重复元素的最长子数组我的代码intmaxSubarrayLength(int*nums,intnumsSize,intk){inti,left,right,maxLength0,maxINT_MIN,minINT_MAX;int*hush(int*)malloc(1000000001*sizeof(int));memset(hush,0,1000000001*sizeof(int));for(left0,right0;rightnumsSize;right){hush[nums[right]];if(hush[nums[right]]k){maxLengthfmax(right-left,maxLength);--hush[nums[left]];left;for(;hush[nums[left-1]]k;left){--hush[nums[left]];}}}free(hush);returnfmax(right-left,maxLength);}思路哈希表记录每个元素的出现次数超过k时向左移动指针收缩窗口。不足之处哈希表大小100000000110亿1过大内存可能不足移动指针的复杂循环逻辑容易出错全局变量min/max未使用。改进方向使用动态哈希数组根据nums实际值范围分配或用哈希表映射元素值与频次简单通过while (hush[nums[right]] k)收缩窗口intmaxSubarrayLength(int*nums,intnumsSize,intk){int*freq(int*)calloc(100001,sizeof(int));intleft0,maxLen0;for(intright0;rightnumsSize;right){freq[nums[right]];while(freq[nums[right]]k){freq[nums[left]]--;left;}maxLenfmax(maxLen,right-left1);}free(freq);returnmaxLen;}8. 2016. 增量元素之间的最大差值我的代码intmaximumDifference(int*nums,intnumsSize){intret-1,minPriceINT_MAX,right;for(right0;rightnumsSize;right){if(minPricenums[right])retfmax(ret,nums[right]-minPrice);minPricefmin(minPrice,nums[right]);}returnret;}思路一次扫描维护最小值求max(nums[i]-minPrice)。不足之处几乎和股票问题121重复但是条件要求ji要求差值至少为1而不是利润可为0。代码逻辑没问题但可以更聚焦于题目设定。改进方向改if(minPricenums[right])为if(minPrice nums[right])更符合严格递增需求但题目不禁止相同值的交换intmaximumDifference(int*nums,intnumsSize){intminPriceINT_MAX,maxDiff-1;for(inti0;inumsSize;i){if(nums[i]minPrice){maxDifffmax(maxDiff,nums[i]-minPrice);}minPricefmin(minPrice,nums[i]);}returnmaxDiff;}9. 2904. 最短且字典序最小的美丽子字符串我的代码篇幅较长略思路滑动窗口统计1的个数当1的个数k时比较当前子串与已记录的最优子串维护长度最短且字典序最小的字符串。不足之处代码较长使用多次malloc、strcmp和strcpy动态处理字符串时的边界条件复杂容易发生内存泄漏lenINT_MAX的初始化取值可疑。改进方向抽象出子串生成操作用变量存储最短子串起始、结束位置避免反复复制字符串char*shortestBeautifulSubstring(char*s,intk){intnstrlen(s);intbestStart-1,bestLenINT_MAX;intleft0,ones0;for(intright0;rightn;right){oness[right]-0;while(onesk){intlenright-left1;if(lenbestLen){bestStartleft;bestLenlen;}elseif(lenbestLenstrncmp(sleft,sbestStart,len)0){bestStartleft;}ones-s[left]-0;left;}}if(bestStart-1)return;char*res(char*)malloc((bestLen1)*sizeof(char));strncpy(res,sbestStart,bestLen);res[bestLen]\0;returnres;}本周总结这一周我真正感受到滑动窗口这一算法并不是一个神秘的“黑盒子”当熟记背后的逻辑后就变成了一种稳定的工具。滑动窗口的核心思想其实很简单用两个指针维护一个窗口通过条件来动态调整窗口的大小和位置计算窗口内的性质并更新答案。今天能够用它的变体解决题目大多是“找满足条件的最长/最短连续数组”我甚至开始对这类题目的模式有了肌肉记忆。这一周提升的点主要有从“只会暴力枚举”过渡到“先想滑动窗口”理解了滑动窗口的优势——时间复杂度从O ( n ) 2 O(n)^2O(n)2降到O ( n ) O(n)O(n)空间复杂度一般O ( 1 ) O(1)O(1)开始用while和if组合处理窗口内计数和边界收缩比之前复杂的嵌套结构简洁了更多开始仔细考虑内存分配和变量作用域确保C语言实现没有内存泄漏。当然改进的空间还有很多尤其是字符串字典序处理和哈希表代替数组的写法这些是我下个阶段要重点刷的题。但能一步步看着自己从写很复杂难懂的绕弯子代码到今天对每个滑动窗口都能在脑海里快速搭建结构终究是在往前走的。这一周也完成了两件大事——成功提交了转专业申请表也完成了分流志愿的填报。无论最后结果如何我都为自己这半年多来的坚持感到骄傲。计算机学院的大门还在前方闪闪发光我会一以贯之地顺着这个向往的方向走下去。附本周所有代码已上传至我的GitHub仓库LeetCode-C-Practice/2026-04-第三周