leetcode数据结构与算法1~4

leetcode数据结构与算法1~4从语法到算法1. LeetCode 645. 错误的集合2. LeetCode 1365. 有多少小于当前数字的数字3. LeetCode 448. 找到所有数组中消失的数字4. LeetCode 28. 找出字符串中第一个匹配项的下标优解一KMP 算法优解二Sunday 算法从语法到算法语言的尽头是算法。学完了 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(). */#includestdlib.hint*findErrorNums(int*nums,intnumsSize,int*returnSize){int*ans(int*)malloc(2*sizeof(int));*returnSize2;// 动态开辟哈希数组大小为 numsSize 1自带初始化为 0int*count(int*)calloc(numsSize1,sizeof(int));for(inti0;inumsSize;i){count[nums[i]];// 核心以值为下标进行统计}for(inti1;inumsSize;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));*returnSizenumsSize;intcount[101]{0};// 题目限制0 nums[i] 100// 1. 频次统计for(inti0;inumsSize;i){count[nums[i]];}// 2. 累加前缀和此刻 count[i] 代表 i 的元素总数for(inti1;i100;i){count[i]count[i-1];}// 3. 将答案保存到ansfor(inti0;inumsSize;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()取绝对值防止已经被打上负号的数字干扰。参考代码#includestdlib.h#includemath.hint*findDisappearedNumbers(int*nums,intnumsSize,int*returnSize){int*res(int*)malloc(numsSize*sizeof(int));intj0;// 1. 第一层遍历进行负号标记for(inti0;inumsSize;i){intindexabs(nums[i])-1;// 拿到数字对应的真实下标if(nums[index]0){nums[index]-nums[index];// 标记为负数证明 abs(nums[i]) 来过}}// 2. 第二层遍历查漏补缺for(inti0;inumsSize;i){if(nums[i]0){// 如果还是正数说明 i1 这个数字根本没出现过res[j]i1;}}*returnSizej;returnres;}4. LeetCode 28. 找出字符串中第一个匹配项的下标主要题意在长字符串主串中寻找短字符串模式串。优解一KMP 算法KMP 算法的核心主串指针绝不回退。它通过预处理模式串生成一个next数组最长公共前后缀表。当发生不匹配时它能告诉你模式串该往前滑动多少而不是像傻子一样每次只挪一位。// KMP 算法实现intstrStr_KMP(char*haystack,char*needle){intnstrlen(haystack),mstrlen(needle);if(m0)return0;int*next(int*)malloc(m*sizeof(int));next[0]0;// 1. 构建 next 数组for(inti1,j0;im;i){while(j0needle[i]!needle[j]){jnext[j-1];// 不匹配回退 j}if(needle[i]needle[j])j;next[i]j;}// 2. 正式匹配for(inti0,j0;in;i){while(j0haystack[i]!needle[j]){jnext[j-1];// 核心主串 i 不回退只回退模式串 j}if(haystack[i]needle[j])j;if(jm){free(next);returni-m1;// 匹配成功}}free(next);return-1;}优解二Sunday 算法KMP 虽强但太难记了。在实际应用中Sunday 算法跑得更快而且逻辑更简单。它的核心是看主串匹配窗口的“下一个字符”如果在模式串里根本没这个字符直接把模式串整个滑过这个字符// Sunday 算法实现intstrStr(char*haystack,char*needle){intnstrlen(haystack),mstrlen(needle);if(m0)return0;// 1. 构建偏移表记录字符最右出现位置距离尾部的距离intshift[256];for(inti0;i256;i)shift[i]m1;// 默认偏移整个模式串长度1for(inti0;im;i)shift[(unsignedchar)needle[i]]m-i;inti0;// 2. 开始匹配while(in-m){intj0;while(jmhaystack[ij]needle[j])j;// 逐个比对if(jm)returni;// 完全匹配if(imn)return-1;// 边界判断// 核心根据主串参加匹配的【下一个字符】的偏移量决定向右跳多远ishift[(unsignedchar)haystack[im]];}return-1;}建议如果要求O ( M N ) O(MN)O(MN)的复杂度 KMP否则Sunday 算法的代码量和执行效率更优。