LeetCode---Hot100-字符串部分

前提

这部分遇到了好多之前没用到的或者很少见过的知识，比如三级指针、指针数组相关的内容，记录一下方便复习。所选内容都是出自leetcodehot100。
本内容不考虑什么复杂度问题，只是给个思路方便以后不会了在刷一刷

1.两数之和

题目地址

思路:直接采用暴力解法(双层for循环)，其中一个指针(叫1指针吧，从最开始遍历到倒数第二个元素，另一个指针(叫2指针)从1指针的下一个元素一直遍历到最后一个元素，在内层循环中让对应元素相加来判断是否满足条件。
注意题目要求:输入只会对应一种答案，就是说返回的数组个数是确定的为2，这样就好做多了，同时要考虑输入为空的情况，最后的代码如下。

//int* nums表示传入的数组 int numsSize表示传入数组的元素个数//int* returnSize 最终返回的元素个数int* twoSum(int* nums, int numsSize, int target, int* returnSize) { if(numsSize == 0) { *returnSize = 0;//returnSize变量表示最后返回的数组元素的个数 return NULL; } int *arr = (int *)malloc(sizeof(int)*2); for(int i = 0; i < numsSize -1;i++) { for(int j = i+1; j <numsSize;j++) { if(nums[i]+nums[j] == target) { arr[0] = i; arr[1] = j; } } } *returnSize = 2; return arr;}

2.找到字符串中所有的字母异位词

题目地址
题目描述如下:

题目思路:这个题首先要考虑到s串字符数大于p串字符数时才成立，第二点就是该如何遍历，这里还是采用暴力算法，从头开始遍历，每次遍历的长度是p字符串的长度，也就是说按照顺序每次从s串中取与p字符串长度相等的字符串进行比较，如果确定是字母异位词，则记录一下s串中抽取的字符串的首个字母的索引值就行。最后关键的一步是，如何判断两个等长的字符串是字母移位词(即字符串中含有不同类别但对应相同数量的字母，说白了就是一个字符串和其多种排列组合方式就叫做字母异位词，比如abc,acb和bac)。这个思路来源于这个老哥的博客字母异位词，我感觉写的很清楚，同时接下来的字母异位词分组也是按照这个老哥的思路写的。
对于两个字母异位词，比如\"abc\" 和\"acb\"
核心就是定义一个int a[26]的数组，这个数组全部初始化为0，之后对于char *str1 =\"abc\"和char *str2 =\"bca\"字符串，它们长度为3，a[str1[0]-‘a’]++;以及
a[str2[2]-‘a’]–;这两个经过加和减后结果还是0，这个就是字母异位词对应的性质。

char *s1 = \"abc\";char *s2 = \"cba\";int len1 = strlen(s1);int len2 = strlen(s2);int array[26]={0};//假设字母异位词中的字母全部位小写字母for(int i = 0;i < len1;i++){array[s1[i]-\'a\']++;array[s2[i]-\'a\']--;}for(int j = 0;j < 26;j++){ if(array[i] != 0) return array[i];}return 0;//根据是否为0来判断是不是字母异位词

根据上述思路，可以写代码了，如下图所示:

int if_true(char* s1,char* s2,int len);int* findAnagrams(char* s, char* p, int* returnSize) {//因为要返回数组，所以需要给定返回的数组元素的个数，由于返回元素个数不确定，可能会被修改，所以这里传入一个整形指针returnSize进行改变原始变量的值 int len1 = strlen(s); int len2 = strlen(p); int* array = (int*)malloc(sizeof(int)*30000); int flag = 0; int index = 0; if(len1 < len2) { *returnSize = 0; return NULL; } for(int i = 0; i < len1-len2+1;i++)//遍历全部长度为len2的字符串和p字符串比较 { flag = if_true(s+i,p,len2); if(flag == 0)//说明以第i个位置为起始长度为len2的字符串与p字符串为字母异位词 { array[index++] = i; } } *returnSize = index; return array;}int if_true(char* s1,char* s2,int len)//判断对应的程序是否出现异位词{ int cnt[26] ={0}; for(int i = 0; i < len;i++) { cnt[s1[i]-\'a\']++; cnt[s2[i]-\'a\']--; } for(int i =0; i < 26;i++) { if(cnt[i] != 0) return cnt[i]; } return 0;}

3.字母异位词分组

题目地址
来看一个进阶的，这个题如果使用哈希表的话还是比较简单的，或者C++也能很快的实现，但用C语言的话可以使用哈希数组，但由于哈希函数可能不太好构造或者说到时候笔试或面试啥的不会了，这个就比较麻烦，所以还是采用上面那一道题的思路。在加上返回的是三级指针相关的内容，因此这个题能复习很多的知识点(尤其是关于指针和根据指针分配内存的知识点，所以把它单独拿了出来，这道题值得一做)，先看几个前置的知识。
(1).关于字符串数组的知识
char *p = “abcd” 和 char p[] = \"abcd\"的区别?
由于\"abcd\"是一个字符串常量，存储在常量区，即是只读的，因此对于第一个使用一个指针，指向了一个常量区，则内容只可以读，不可以修改。而第二个是可以读写的,\"abcd\"存储在栈区。

char str1[] = \"abcd\"; // 静态存储区（可修改）char *str2 = \"abcd\"; // 静态存储区（指向只读内存）str1[0] = \'x\'; // ✅ 合法str2[0] = \'x\'; // ❌ 崩溃（未定义行为）

(2).关于指针数组和如何定义一个具有多个字符串的指针数组
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出[[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
我们如何用数组来构造一个题目所示的输入strs和一个输出呢?

 其中test1_arr1为指针数组，在传入函数参数时作为一个二级指针传入(因为数组的数组名对应变量类型就是数组存储元素的首地址即如果一个数组类型为int 则数组名对应类型为int*，如果一个数组存储元素类型为int*，则数组名类型为int**,指针数组和二维数组还不太一样，对于二维数组，int a[3][3]和指针数组int* a[3],第一个int a[3][3]元素类型可以理解为int[3]即，它是一个一维数组，该数组存储的数据类型为一个数组,因此将二维数组传入函数的时候应该传的是数组指针的方式，而int* a[3]传入时采用的是二级指针的方式(int ** ）。直接看例子吧目的:知道二维数组多种构造以及传入方式构造一个二维数组，之后我们通过不同的传入方式输出这个二维数组1.直接输出二维数组2.通过数组指针 输出二维数组3.通过二级指针分配数组先看第1个1.定义一个二维数组后,传入一个二维数组之后打印数组int a[3][3] = {{1,2,3},{4,5,6},{7,8,9}};void printf_arr_array(int a[][3], int size){ printf(\"---直接传入一个数组进行输出---\\n\"); for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { printf(\"%d \", a[i][j]); } } printf(\"\\n\");}2.通过数组指针 输出二维数组int a[3][3] = {{1,2,3},{4,5,6},{7,8,9}};对于a,它是一个数组名，表示它的类型是a[0]这个数据类型的指针,a[3][3]可以看做是一个长度为3的一维数组，每个数组元素存储的数据类型为int [3],则a表示为一个长度为3,存储类型为int的数组指针int (*p)[3]void printf_arr_pointer_array(int (*arr)[3],int size){ printf(\"---传入一个数组指针进行输出---\\n\"); for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { printf(\"%d \",(*(arr+i))[j]); } } printf(\"\\n\");}3.二维数组的动态分配动态分配这个一般是常用到的，尤其是让我们返回一个分配好的二维数组，在返回一个二级指针后，一般还会返回这个数组的长度(通常是一个整形指针 int* returnsize），和一个整形数组(记录每行元素的个数,int** return_arr)。涉及到指针问题的时候，一定要明确指针必须指向一个明确的对象空间，否则就是野指针，会使得程序卡死。对于动态分配二维数组而言，二级指针执行一个指针数组，因此要为这个指针数组分配实际的内存空间，同时每个指针数组指向一个整形数组，因此每个指针数组中的每个元素也要进行空间的分配。好，下面看一下程序。int** printf_arr_double_pointer(int **arr, int size){ int **result = (int**)malloc(sizeof(int*)*size);//申请一个指针数组，使得result指向一个实例化的对象 for (int i = 0; i < size; i++)//这个for循环的size对应的是有几个这样的一维数组，可以类别二维数组中的行 { result[i] = (int*)malloc(sizeof(int)*size);//每个指针数组的每个元素都是一个指针，都指向一个整形数组，因此也要分配空间 for (int j = 0; j < size; j++)//这个size对应的是每行对应的元素个数 { result[i][j] = 3*i+j+1; } } return result;//返回对应的二维数组}好二维数组的传入总结的差不多了，现在如何构造一个数组，数组中的每个元素是二维数组呢?答案如下 char *test1_arr[] = {\"bat\"}; char *test2_arr[] = {\"nat\",\"tan\"}; char *test3_arr[] = {\"ate\",\"eat\",\"tea\"}; char** array_two[] = {test1_arr,test2_arr,test3_arr};

经过上面的一些复习，现在来看一下这道题，这道题如果用哈希表的话很简单，但是不用的话，就是考察对应的指针相关的知识。这道题的思路如下:先构造一个比较函数，将原始的字符串排个序即可。之后的话，开始分配内存，由于是三级指针，因此它其实指向的是一个二级指针数组。里面存放的是一个char类型的指针，它其实又指向的也是一个指针数组，里面存放的是char*的指针，它指向的就是一个一维char类型的数组。好，明白上述的关系后，我们开始进行内存分配。为三级指针分配一个类型为数据类型char，长度为strSize(输入的指针数组中数据的个数，因为最后该三级指针指向的数组长度肯定小于strSize，但不一定全部用完，这也是为什么在动态分配二级指针或者三级指针往上的数据类型时，要返回数组的个数以及每行对应的元素个数，这样才能准确输出对应的内容，因为你分配的内存不一定全部要使用)。之后的话就是遍历，遍历每一个输入的指针数组中每个项的内容，进行字母异位词判断，直到出现不是字母异位词的情况，这个时候将前面的字母异位词添加到对应的分配的内存中去即可。代码如下:

int compare(const void* a, const void* b);char*** groupAnagrams(char** strs, int strsSize, int* returnSize, int** returnColumnSizes) { if(strsSize == 0) { *returnSize = 0; *returnColumnSizes = NULL; return NULL; } qsort(strs,strsSize,sizeof(strs[0]),compare);//进行顺序排列 char*** result = (char***)malloc(sizeof(char**)*strsSize);//进行内存分配 *returnColumnSizes = (int*)malloc(sizeof(int)*strsSize); int i,j,index; index = i = 0; int temp = 0; while(i < strsSize) { j = i+1; while(j < strsSize &&(compare(strs+i,strs+j)==0)) { j++;//退出循环后指向的是下一组字母异位词的地址 } result[index] = (char**)malloc(sizeof(char*)*(j-i)); for(int k = i;k < j;k++) { result[index][k-i] = strs[k]; } (*returnColumnSizes)[temp++] = j-i; i=j; index++; } *returnSize = index; return result;}//基于qsort封装的比较函数，采用的升序排序int compare(const void* a, const void* b){ char* str1 = *(char**)a;//这里要进行一个转化，因为传入的是二级指针 char* str2 = *(char**)b; int len1 = strlen(str1); int len2 = strlen(str2); if(len1 != len2) return len1-len2; int cnt[26] = {0}; if(len1 == len2) { for(int i = 0; i < len1;i++) { cnt[str1[i] - \'a\']++; cnt[str2[i] - \'a\']--; } for(int j =0;j<26;j++) { if(cnt[j] != 0) return cnt[j]; } } return 0;}

4.无重复字符的最长子串

题目链接

这道题采用的滑动窗口的做法，先看一个示例吧，关于滑动窗口的，已知一个字符串(这里用的是伪代码)
ABCDEFG，现在问其中包含BD字符串的最小长度，采用的就是滑动窗口思想。
采用左右指针思想([代表左指针，而]代表右指针)
不符合题意的话右指针向右加加符合题意的话左指针加加。

[]ABCDEFG [A]BCDEFG[AB]CDEFG[ABC]DEFG [ABCD]EFG //符合题意此时记录当前字符串的长度为4A[BCD]EFG //符合题意此时记录当前字符串的长度为3 同时左指针加加AB[CD]EFG AB[CDE]FGAB[CDEF]GAB[CDEFG] //遍历完，右指针达到最大此时退出循环

上面就是滑动窗口的思想，代码如下:

int lengthOfLongestSubstring(char* s) { int left,right =0; int len = strlen(s); if(!len)//为0条件时该如何处理 return 0; left = right = 0; int max_count = 1;//记录符合题目要求的字符长度 while(right < len)//退出条件右指针遍历完毕 { for(int i = left;i < right;i++)//查找字符是否出现重复 { if(s[i] == s[right])//出现重复此时左指针指向重复位置的下一个 { left = i+1; break;  } } max_count = (max_count < right-left+1)?right-left+1:max_count; right++; } return max_count;//返回对应的值}

5.最长连续序列

题目描述
题目要求如下:

这道题的思路比较简单，其实就是使用C语言自带的快排函数进行升序排序，之后的话，采用前后相减的方式判断是否为1，是否相等和其他这三种情况。
是否为1表示这两项是连续序列，其中这个是否相等按1个算，举个例子
0 11 2，这个11可以当成是一个1 ，也就是0 1 2，如果是 0 1 1 1 2，也当成0 1 2。同时采用一个变量去记录对应大小并且实时的去更新它。下面为该题的代码。

int compare(const void* a, const void* b);int longestConsecutive(int* nums, int numsSize) { qsort(nums,numsSize,sizeof(int),compare);//整体做一个顺序排序 int m,n; if(numsSize == 0) return 0; m = n =1; for(int i = 0;i < numsSize-1;i++)//由于涉及到前后两项,因此只遍历到numsSize-1 { if(nums[i+1] - nums[i] == 1) { n++; } else if(nums[i] == nums[i+1]) { n = n; } else { m = (m > n)?m:n;//实时更新满足题意要求的长度 n = 1; } } m = (m > n)?m:n;//实时更新，这里更新是因为如果输入全部是连续序列，那么上 //面的else不会执行，最终输出结果会为1,但这个是不对的所以这里要加上这个。 return m;}int compare(const void* a, const void* b){ return *(int*)a - *(int*)b;}

6.动态二维数组分配的题目

这道题是关于动态分配二维数组的题，所以感觉还是挺有意思的，拿出来看一下。题目描述如下:
题目链接

思路如下:
首先对传入的数组进行一个升序的排序。这里需要使用qsort函数进行快排，需要用户自己传入一个比较函数。第二步就是进行内存的分配。由于返回的是二级指针，因此采用动态分配内存的方式进行。二级指针指向的是一个一维指针数组，每个数组元素同时又指向一个一维数组，也就是说我们要进行两次分配，第一次分配为指针数组分配固定size的空间，第二次分配是为每个数组元素分配固定长度的(长度为3)一维数组。同时由于返回的是二维数组，还要返回数组对应的长度(一个整形变量)以及每行对应的元素个数(一个一维数组),由于这两个是不确定的，同时形参不改变实参，因此这两个需要传入对应的指针，整形变量传入一个整形指针即可，一维数组传入一个二级指针即可(同时还需要为该数组分配内存空间)为什么是二级指针?因为一维数组比如int a[3],a是int*形的，想改变a对应的值需要再取一个地址也就是int **。这样才可以。最后就是双指针思想，左指针在前右指针往后，同时从0开始遍历，由于数组已经做了升序排序，所以遍历到某个元素大于0，往后就不需要遍历了，因为不可能出现符合题意的了，同时当出现前一个和后一个值相等的时候要跳过，因为前一个包含后一个后面的所有结果，后一个不一定包含前一个后面的所有结果。根据符合题意要求的进行内存分配即可。

int compare(const void* a, const void* b);int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) { int left_pointer,right_pointer; int t_base = numsSize; int sum =0; *returnSize = 0; if(numsSize < 3)//元素小于3不符合题意，直接跳过 { *returnColumnSizes = NULL; return NULL; } int **res = (int**)malloc(sizeof(int*)*t_base); *returnColumnSizes = (int*)malloc(sizeof(int)*t_base); qsort(nums,numsSize,sizeof(int),compare); for(int i = 0; i < numsSize;i++) { if(nums[i] > 0)  break; if((i > 0) && (nums[i-1] == nums[i]))//重复值舍掉后一个结果  continue; left_pointer = i+1; right_pointer = numsSize-1; while(left_pointer < right_pointer) { sum = nums[i] + nums[left_pointer] + nums[right_pointer]; if(sum == 0) { res[*returnSize] = (int*)malloc(sizeof(int)*3); res[*returnSize][0] = nums[i];  res[*returnSize][1] = nums[left_pointer]; res[*returnSize][2] = nums[right_pointer]; (*returnColumnSizes)[*returnSize] = 3; (*returnSize)++; if(t_base == *returnSize)//防止申请的内存不够，重新进行分配 { t_base = 2*t_base; res = (int**)realloc(res,sizeof(int*)*t_base); *returnColumnSizes = (int*)realloc(*returnColumnSizes,sizeof(int)*t_base); } while((left_pointer<right_pointer)&&(nums[left_pointer] == nums[++left_pointer]));//跳过重复的值(题目要求) while((left_pointer<right_pointer)&&(nums[right_pointer] == nums[--right_pointer])); } if(sum >0)//总体值大于0，说明值要往小的地方移动即左指针减减。 { right_pointer--; } if(sum < 0)//总体值大于0,，说明值要往大的地方移动即右指针加加。 { left_pointer++; } } } return res;}int compare(const void* a, const void* b){ return *(int*)a - *(int*)b;}

以上就是字符串中的相关题目，涉及到指针、指针数组、多级指针等方面的内容，多多复习，加深对C语言的理解。