当前位置：首页 > news >正文

C语言刷题日记 #6

news 2026/4/26 1:53:50

C语言刷题日记 #7（2026.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;*returnSize=2;for(i=0;i<numsSize-1;i++){for(j=i+1;j<numsSize;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;// 复杂度更优，但直接调库实现哈希表需要依赖uthash，C语言调试略繁琐// 或者用数组法（nums元素范围有限时）int*twoSum(int*nums,intnumsSize,inttarget,int*returnSize){int*arr=(int*)malloc(2*sizeof(int));*returnSize=2;inthash[20001]={0};for(inti=0;i<numsSize;i++){intcomplement=target-nums[i];if(hash[complement+10000]!=0){arr[0]=hash[complement+10000]-1;arr[1]=i;returnarr;}hash[nums[i]+10000]=i+1;}returnarr;}

2. 121. 买卖股票的最佳时机

我的代码：

intmaxProfit(int*prices,intpricesSize){intret=0,minPrice=INT_MAX,right;for(right=0;right<pricesSize;right++){if(minPrice<prices[right])ret=fmax(ret,prices[right]-minPrice);minPrice=fmin(minPrice,prices[right]);}returnret;}

思路：一次扫描，维护历史最低价格，计算当天价格与最低价的差价。
不足之处：判断条件if(minPrice<prices[right])前后的顺序可以更清晰；变量right作为循环索引但并未体现“滑动窗口”含义。
改进方向：交换顺序更好理解：

intmaxProfit(int*prices,intpricesSize){intminPrice=INT_MAX,maxProfit=0;for(inti=0;i<pricesSize;i++){minPrice=fmin(minPrice,prices[i]);maxProfit=fmax(maxProfit,prices[i]-minPrice);}returnmaxProfit;}

3. 209. 长度最小的子数组

我的代码：

intminSubArrayLen(inttarget,int*nums,intnumsSize){intleft,right,sum=0,min=INT_MAX;for(left=right=0;right<numsSize;){while(sum<target&&right<numsSize){sum+=nums[right];right++;}while(sum>=target){min=fmin(min,right-left);sum-=nums[left];left++;}}if(min==INT_MAX)return0;returnmin;}

思路：双循环滑动窗口，先右扩直到满足条件，再左缩更新答案。
不足之处：当窗口内多个连续数满足条件时，必须逐个左移指针，否则可能错过更短的窗口；滑动窗口对“正整数数组”有效，但若允许负数（本题不适用），窗口长度最小化会失效。
改进方向：用while嵌套逻辑完整，但是写成标准模板更清晰：

intminSubArrayLen(inttarget,int*nums,intnumsSize){intleft=0,sum=0,minLen=INT_MAX;for(intright=0;right<numsSize;right++){sum+=nums[right];while(sum>=target){minLen=fmin(minLen,right-left+1);sum-=nums[left];left++;}}returnminLen==INT_MAX?0:minLen;}

4. 713. 乘积小于 K 的子数组

我的代码：

intnumSubarrayProductLessThanK(int*nums,intnumsSize,intk){if(k==0)return0;intleft,right;longlongplus=1,sum=0;for(left=right=0;right<numsSize;right++){plus*=nums[right];while(left<right&&plus>=k){plus/=nums[left];left++;}if(nums[right]<k){sum+=right-left+1;}}returnsum;}

思路：滑动窗口，乘积小于k时计数当前窗口子数组数并累加。
不足之处：引入了if(nums[right]<k)过滤冗余，但这会跳过窗口内包含nums[right]但大于等于k的乘积计算，可能导致漏计子数组；处理k==0的情况需要单独判断，可读性需提升。
改进方向：统一滑动窗口，每次计数子数组时相加right-left+1：

intnumSubarrayProductLessThanK(int*nums,intnumsSize,intk){if(k<=1)return0;longlongproduct=1;intleft=0,count=0;for(intright=0;right<numsSize;right++){product*=nums[right];while(product>=k)product/=nums[left++];count+=right-left+1;}returncount;}

5. 1004. 最大连续1的个数 III

我的代码：

intlongestOnes(int*nums,intnumsSize,intk){intleft,right,sum0=0,max=0;for(left=right=0;right<numsSize;right++){sum0+=nums[right]==0?1:0;max=fmax(max,right-left);while(sum0>k){sum0-=nums[left]==0?1:0;left++;}}returnfmax(max,right-left);}

思路：滑动窗口，统计窗口内0的个数，当0的个数大于k时移动左指针收缩窗口。
不足之处：right-left先求值再收缩可能导致长度统计偏差；max在while之前更新可能记录过长窗口；最终返回值需要和前一个计算合并。
改进方向：统一在右指针遍历过程中维护窗口内0的个数，保证窗口内0的个数始终≤k：

intlongestOnes(int*nums,intnumsSize,intk){intleft=0,maxLen=0,zeroCount=0;for(intright=0;right<numsSize;right++){if(nums[right]==0)zeroCount++;while(zeroCount>k){if(nums[left]==0)zeroCount--;left++;}maxLen=fmax(maxLen,right-left+1);}returnmaxLen;}

6. 2024. 考试的最大困扰度

我的代码：

intmaxConsecutiveAnswers(char*answerKey,intk){intsumF=0,sumT=0,max=0,left,right;for(left=0,right=0;right<strlen(answerKey);right++){if(answerKey[right]=='T')sumT++;elsesumF++;max=fmax(max,right-left);while(sumT>k){if(answerKey[left]=='T')sumT--;elsesumF--;left++;}}max=fmax(max,right-left);sumF=sumT=0;for(left=0,right=0;right<strlen(answerKey);right++){if(answerKey[right]=='T')sumT++;elsesumF++;max=fmax(max,right-left);while(sumF>k){if(answerKey[left]=='T')sumT--;elsesumF--;left++;}}returnfmax(max,right-left);}

思路：两次滑动窗口，分别统计T和F，允许最多翻转k个。
不足之处：代码重复（两次滑动窗口逻辑几乎一样），可重构为函数；多次调用strlen(answerKey)效率低；max更新逻辑不统一。
改进方向：抽取maxConsecutiveChar函数处理单个字符：

intmaxConsecutiveChar(char*s,charch,intk){intleft=0,maxLen=0,count=0,n=strlen(s);for(intright=0;right<n;right++){if(s[right]!=ch)count++;while(count>k){if(s[left]!=ch)count--;left++;}maxLen=fmax(maxLen,right-left+1);}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,maxLength=0,max=INT_MIN,min=INT_MAX;int*hush=(int*)malloc(1000000001*sizeof(int));memset(hush,0,1000000001*sizeof(int));for(left=0,right=0;right<numsSize;++right){++hush[nums[right]];if(hush[nums[right]]>k){maxLength=fmax(right-left,maxLength);--hush[nums[left]];++left;for(;hush[nums[left-1]]<k;++left){--hush[nums[left]];}}}free(hush);returnfmax(right-left,maxLength);}

思路：哈希表记录每个元素的出现次数，超过k时向左移动指针收缩窗口。
不足之处：哈希表大小1000000001（10亿+1）过大，内存可能不足；移动指针的复杂循环逻辑容易出错；全局变量min/max未使用。
改进方向：使用动态哈希数组（根据nums实际值范围分配），或用哈希表映射元素值与频次，简单通过while (hush[nums[right]] > k)收缩窗口：

intmaxSubarrayLength(int*nums,intnumsSize,intk){int*freq=(int*)calloc(100001,sizeof(int));intleft=0,maxLen=0;for(intright=0;right<numsSize;right++){freq[nums[right]]++;while(freq[nums[right]]>k){freq[nums[left]]--;left++;}maxLen=fmax(maxLen,right-left+1);}free(freq);returnmaxLen;}

8. 2016. 增量元素之间的最大差值

我的代码：

intmaximumDifference(int*nums,intnumsSize){intret=-1,minPrice=INT_MAX,right;for(right=0;right<numsSize;right++){if(minPrice<nums[right])ret=fmax(ret,nums[right]-minPrice);minPrice=fmin(minPrice,nums[right]);}returnret;}

思路：一次扫描，维护最小值，求max(nums[i]-minPrice)。
不足之处：几乎和股票问题121重复，但是条件要求j>i，要求差值至少为1而不是利润可为0。代码逻辑没问题但可以更聚焦于题目设定。
改进方向：改if(minPrice<nums[right])为if(minPrice <= nums[right])更符合严格递增需求，但题目不禁止相同值的交换：

intmaximumDifference(int*nums,intnumsSize){intminPrice=INT_MAX,maxDiff=-1;for(inti=0;i<numsSize;i++){if(nums[i]>minPrice){maxDiff=fmax(maxDiff,nums[i]-minPrice);}minPrice=fmin(minPrice,nums[i]);}returnmaxDiff;}

9. 2904. 最短且字典序最小的美丽子字符串

我的代码：（篇幅较长，略）

思路：滑动窗口统计1的个数，当1的个数==k时，比较当前子串与已记录的最优子串，维护长度最短且字典序最小的字符串。
不足之处：代码较长，使用多次malloc、strcmp和strcpy；动态处理字符串时的边界条件复杂，容易发生内存泄漏；len=INT_MAX的初始化取值可疑。
改进方向：抽象出子串生成操作，用变量存储最短子串起始、结束位置，避免反复复制字符串：

char*shortestBeautifulSubstring(char*s,intk){intn=strlen(s);intbestStart=-1,bestLen=INT_MAX;intleft=0,ones=0;for(intright=0;right<n;right++){ones+=s[right]-'0';while(ones==k){intlen=right-left+1;if(len<bestLen){bestStart=left;bestLen=len;}elseif(len==bestLen&&strncmp(s+left,s+bestStart,len)<0){bestStart=left;}ones-=s[left]-'0';left++;}}if(bestStart==-1)return"";char*res=(char*)malloc((bestLen+1)*sizeof(char));strncpy(res,s+bestStart,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语言实现没有内存泄漏。