leetcode数据结构与算法1~4

从语法到算法

语言的尽头是算法。学完了 C 语言的语法，只能停留在“能写出代码”的阶段，遇到稍微复杂点的数据处理就无从下手，或是只能一味的for暴力。

所以，我切换了实战模式。在接下来的数据结构篇，不讲干巴巴的理论，直接上 LeetCode 或 牛客网 原题。用代码思考。

1. LeetCode 645. 错误的集合

主要题意：在一个本该是1 11到n nn的连续序列里，有一个数重复了，导致另一个数被丢失。怎么快速把这俩揪出来？

思路：

• 1：排序再遍历，太慢了。
• 2：拿空间换时间。开辟一个额外的计数数组（哈希表），原数组里读到几，就在计数数组下标为该值的元素里加一。再循环一遍计数数组，值为 2 的就是重复项，值为 0 的就是丢失项。

踩坑批注：刚开始我直接开了一个arr[100000]在栈上。虽然能过，但如果题目给的数据量再大点，就Stack Overflow。更优雅的做法是用calloc动态开辟刚好够用的空间。

参考代码：

/** * Note: The returned array must be malloced, assume caller calls free(). */#include<stdlib.h>int*findErrorNums(int*nums,intnumsSize,int*returnSize){int*ans=(int*)malloc(2*sizeof(int));*returnSize=2;// 动态开辟哈希数组，大小为 numsSize + 1，自带初始化为 0int*count=(int*)calloc(numsSize+1,sizeof(int));for(inti=0;i<numsSize;i++){count[nums[i]]++;// 核心：以值为下标进行统计}for(inti=1;i<=numsSize;i++){// 数据从 1 开始if(count[i]==0)ans[1]=i;// 没出现过，丢失if(count[i]==2)ans[0]=i;// 出现两次，重复}free(count);// 别忘了释放内存returnans;}

2. LeetCode 1365. 有多少小于当前数字的数字

主要题意：对于数组里的每个数，找出比它小的数有多少个。

思路（频次统计 + 前缀和）：

• 1：暴力解法就是两层for循环嵌套，时间复杂度O ( N 2 ) O(N^2)O(N2)。当数据量上万时，程序就得跑半天。
• 2：注意到题目给了一个关键的条件：0 <= nums[i] <= 100。数据范围∠小，直接计数排序
• 2-1.count[i]统计每个数字出现的次数。
• 2-2. 计算前缀和。让count[i] += count[i-1]。**小于或等于i ii的数字总共有count[i]**。

算法思维：用前缀和处理数组区间问题，能把O ( N ) O(N)O(N)的区间查询操作直接降维到O ( 1 ) O(1)O(1)。

参考代码：

int*smallerNumbersThanCurrent(int*nums,intnumsSize,int*returnSize){int*ans=(int*)malloc(numsSize*sizeof(int));*returnSize=numsSize;intcount[101]={0};// 题目限制0 <= nums[i] <= 100// 1. 频次统计for(inti=0;i<numsSize;i++){count[nums[i]]++;}// 2. 累加前缀和：此刻 count[i] 代表 <= i 的元素总数for(inti=1;i<=100;i++){count[i]+=count[i-1];}// 3. 将答案保存到ansfor(inti=0;i<numsSize;i++){// 如果当前数字是 0，比它小的个数就是 0；否则查表ans[i]=(nums[i]==0?0:count[nums[i]-1]);}returnans;}

3. LeetCode 448. 找到所有数组中消失的数字

主要题意：这题和第一题极其相似，但进阶要求非常变态：不使用额外空间，且时间复杂度为O ( N ) O(N)O(N)。（返回的数组不算在内）。

思路：

• 1:直接在原数组中操作。
  因为数组里的数字都在[ 1 , N ] [1, N][1,N]范围内，而数组的下标也是[ 0 , N − 1 ] [0, N-1][0,N−1]。它们有着天然的一一对应关系（数字x xx对应下标x − 1 x-1x−1）。遍历数组，每遇到一个数x xx，把下标为x − 1 x-1x−1的数变成负数。遍历完后，谁的位置上还是正数，谁就没出现过。

借助库函数（math.h）：利用abs()取绝对值，防止已经被打上负号的数字干扰。

参考代码：

#include<stdlib.h>#include<math.h>int*findDisappearedNumbers(int*nums,intnumsSize,int*returnSize){int*res=(int*)malloc(numsSize*sizeof(int));intj=0;// 1. 第一层遍历：进行负号标记for(inti=0;i<numsSize;i++){intindex=abs(nums[i])-1;// 拿到数字对应的真实下标if(nums[index]>0){nums[index]=-nums[index];// 标记为负数，证明 abs(nums[i]) 来过}}// 2. 第二层遍历：查漏补缺for(inti=0;i<numsSize;i++){if(nums[i]>0){// 如果还是正数，说明 i+1 这个数字根本没出现过res[j++]=i+1;}}*returnSize=j;returnres;}

4. LeetCode 28. 找出字符串中第一个匹配项的下标

主要题意：在长字符串（主串）中寻找短字符串（模式串）。

优解一：KMP 算法

KMP 算法的核心：主串指针绝不回退。
它通过预处理模式串，生成一个next数组（最长公共前后缀表）。当发生不匹配时，它能告诉你模式串该往前滑动多少，而不是像傻子一样每次只挪一位。

// KMP 算法实现intstrStr_KMP(char*haystack,char*needle){intn=strlen(haystack),m=strlen(needle);if(m==0)return0;int*next=(int*)malloc(m*sizeof(int));next[0]=0;// 1. 构建 next 数组for(inti=1,j=0;i<m;i++){while(j>0&&needle[i]!=needle[j]){j=next[j-1];// 不匹配，回退 j}if(needle[i]==needle[j])j++;next[i]=j;}// 2. 正式匹配for(inti=0,j=0;i<n;i++){while(j>0&&haystack[i]!=needle[j]){j=next[j-1];// 核心：主串 i 不回退，只回退模式串 j}if(haystack[i]==needle[j])j++;if(j==m){free(next);returni-m+1;// 匹配成功}}free(next);return-1;}

优解二：Sunday 算法

KMP 虽强，但太难记了。在实际应用中，Sunday 算法跑得更快，而且逻辑更简单。
它的核心是看主串匹配窗口的“下一个字符”：
如果在模式串里根本没这个字符，直接把模式串整个滑过这个字符！

// Sunday 算法实现intstrStr(char*haystack,char*needle){intn=strlen(haystack),m=strlen(needle);if(m==0)return0;// 1. 构建偏移表：记录字符最右出现位置距离尾部的距离intshift[256];for(inti=0;i<256;i++)shift[i]=m+1;// 默认偏移整个模式串长度+1for(inti=0;i<m;i++)shift[(unsignedchar)needle[i]]=m-i;inti=0;// 2. 开始匹配while(i<=n-m){intj=0;while(j<m&&haystack[i+j]==needle[j])j++;// 逐个比对if(j==m)returni;// 完全匹配if(i+m>=n)return-1;// 边界判断// 核心：根据主串参加匹配的【下一个字符】的偏移量，决定向右跳多远i+=shift[(unsignedchar)haystack[i+m]];}return-1;}

建议：如果要求O ( M + N ) O(M+N)O(M+N)的复杂度， KMP；否则，Sunday 算法的代码量和执行效率更优。