目录
零、写在前面
一、主要知识点
1.字符拷贝
2.字符串比较
3.字符串是否为子串(补充知识点)
二、课后习题
剑指 Offer 05. 替换空格
面试题 10.05. 稀疏数组搜索
290. 单词规律
1309. 解码字母到整数映射
1967. 作为子字符串出现在单词中的字符串数目
写在最后
零、写在前面
这是打卡的第二十二天，今天难度不高，主要知识点在
《算法零基础100讲》(第22讲) 字符串算法(二) - 字符串比较https://blog.csdn.net/WhereIsHeroFrom/article/details/120875787
https://blog.csdn.net/WhereIsHeroFrom/article/details/120875787
一、主要知识点
1.字符拷贝
系统函数strcpy(const char *,const char *);
char src[10] = "Hello"; char tar[10]; strcpy(tar, src);
2.字符串比较
系统函数 int strcmp(const char *,const char *)，这个函数有返回值，返回值是两个字符串第一个不同的字母的字典序差值。当完全相同时返回0，并且有大小写的区分。
char src[10] = "Hello"; char tar[10] = "hello"; int x = strcmp(tar, src); int y = strcmp(tar, "hello");
3.字符串是否为子串(补充知识点)
系统函数char * strcmp(const char *,const char *)，判断第二个字符串是否为第一个字符串的字串，是的话返回匹配的首地址，否则返回0；
for(int i = 0; i < patternsSize; i++) { if (strstr(word, patterns[i])) {//如果是子串 cnt++; //统计 } }
二、课后习题
剑指 Offer 05. 替换空格
剑指 Offer 05. 替换空格
https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/
思路
如果一开始就直接扫描需要往后挪动元素，时间复杂度过高。
可以一开始扫描一遍字符串 统计空格个数，然后从后往前替换空格，时间复杂度会低很多。
char* replaceSpace(char* s){ int count = 0,size = 0;//记录大小和空格多少 for(int i = 0;s[i];i++){ if(s[i] == ' ') count++;//记录空格 size++; } int p1 = size,p2 = size + 2*count; //双指针，第一个指向当前元素，后面指向要替换位置 char *ans = malloc(sizeof(char)*(p2 + 1 ));//必须申请，因为新串比旧串长很多 while(p1 >= 0){ if(s[p1] != ' ') ans[p2--] = s[p1--];//移动 else{ //插入字符 ans[p2--] = '0'; ans[p2--] = '2'; ans[p2--] = '%'; p1--; } } return ans; }
结果分析
还行吧？
面试题 10.05. 稀疏数组搜索
面试题 10.05. 稀疏数组搜索
https://leetcode-cn.com/problems/sparse-array-search-lcci/
思路
直接扫描判断，如果两个字符串的比较结果是0就返回，如果到最后都没找到，就返回-1
int findString(char** words, int wordsSize, char* s){ for(int i = 0;i < wordsSize;i++){ if(!strcmp(words[i],s)) return i;//找到了返回i } return -1;//没找到 }
结果分析
凑合？
290. 单词规律
290. 单词规律
https://leetcode-cn.com/problems/word-pattern/
思路
将所有的空格替换成结束符，利用hash表记录str中每一个字母对应的字符串的首地址。
特别注意两个长度如果不同就要返回false;
bool wordPattern(char * pattern, char * s){ char * temp[256]; //hash表 char ans[256],size1 =0; //利用数组记录字母个数 int size = 0,i; //用于记录s和pattern长度 memset(temp,0,sizeof(temp));//初始化hash表 其实不初始化也没啥问题 //替换空格并且判断是否相同 for(i = 0;pattern[i] && s[size];i++){ if(temp[pattern[i]]){ char *p = &s[size]; while(!(s[++size] == ' ' ||s[size] == 0)); if(s[size] == ' ') s[size++] = 0; if(strcmp(p,temp[pattern[i]])) return false;//不同返回0 } else{ ans[size1++] =pattern[i]; temp[pattern[i]] = &s[size]; while(!(s[++size] == ' ' ||s[size] == 0)); if(s[size] == ' ') s[size++] = 0; } } if(pattern[i] || s[size]) return false;//长度不同 for(i = 0;i < size1;i++) //判断hash表内元素是否相同 for(int j = i + 1;j < size1;j++) if(!strcmp(temp[ans[i]],temp[ans[j]])) return false; //有相同的串 返回错 return true; }
结果分析
官方题解全是c++,c++的map确实好用，但是。。我喜欢c，怎样啊！
1309. 解码字母到整数映射
1309. 解码字母到整数映射
https://leetcode-cn.com/problems/decrypt-string-from-alphabet-to-integer-mapping/
思路
其实很简单的，利用字符串做记录，现在的思路是从后往前扫描，如果扫到1或者2就判断i+2是否是#，如果是就进入j-z的处理。
突然想到，直接先扫描一遍到最后，从后往前扫描会省事很多，欢迎你们试试。
char * freqAlphabets(char * s){ char * ans = malloc(sizeof(char)*1000); int count = 0; for(int i = 0;s[i];i++){ //j-z的判定 防止越界 判断i+1是否是结束符 利用与的短路特性 if((s[i] == '1' || s[i] == '2')&& s[i + 1] &&s[i + 2] == '#'){ int temp = 0; temp = (s[i] -'1') * 10 + s[i+1] - '0'; i+= 2; ans[count++] = temp +'j'; } //a-i的判定 else ans[count++] = s[i] - '1' + 'a'; } ans[count] = 0;//增加结束符 防止越界 return ans; }
结果分析
可以了。
1967. 作为子字符串出现在单词中的字符串数目
1967. 作为子字符串出现在单词中的字符串数目
https://leetcode-cn.com/problems/number-of-strings-that-appear-as-substrings-in-word/
思路
利用补充知识点，直接判断就好了。
int numOfStrings(char ** patterns, int patternsSize, char * word){ int cnt = 0; for(int i = 0; i < patternsSize; i++) { if (strstr(word, patterns[i])) {//是字串 统计 cnt++; } } return cnt; }
结果分析
挺好？
写在最后
还是得卷，不卷就堕落了。。。加油！
