字符串算法(一)"/>
[解题报告](第21讲) 字符串算法(一)
目录
零、写在前面
一、主要知识点
1.字符串遍历
2.大小写转换。
二、课后习题
1812. 判断国际象棋棋盘中一个格子的颜色
LCP 17. 速算机器人
2011. 执行操作后的变量值
1876. 长度为三且各字符不同的子字符串
520. 检测大写字母
709. 转换成小写字母
1704. 判断字符串的两半是否相似
1844. 将所有数字用字符替换
1805. 字符串中不同整数的数目
写在最后
零、写在前面
这是打卡的第二十天,今天难度不高,其中有些是之前的题目我放了链接。主要知识点在《算法零基础100讲》(第21讲) 字符串算法(一) - 字符串遍历://blog.csdn/WhereIsHeroFrom/article/details/120875895
一、主要知识点
1.字符串遍历
由于'\0'结束符的ASCII码为0,所以可以用下面的方式进行遍历。
for(int i = 0;s[i];++i){//blabla
}
2.大小写转换。
其实小写的ASCII码比大写的大' '个(你说你看不见?你仔细瞅瞅?)。好吧其实就是差一个空格的ASCII码值。可以取查表看看
if(s[i] >= 'A' && s[i] <= 'Z'){s[i] += ' ';
}
二、课后习题
1812. 判断国际象棋棋盘中一个格子的颜色
1812. 判断国际象棋棋盘中一个格子的颜色/
思路
如果把它看成一个矩阵的话,就是下标和为偶数的是黑色,奇数为白色。
所以一行代码完事了呗?
bool squareIsWhite(char * coordinates){//求下表和并返回奇偶判定return (coordinates[0] - 'a' + coordinates[1] - '1') & 1;
}
结果分析
可还行?
LCP 17. 速算机器人
LCP 17. 速算机器人/
主要思路
不难,让干啥干啥就完事了。。
int calculate(char* s){int x = 1,y = 0;//初始化for(int i = 0;s[i];++i) //遍历字符串计算值if(s[i] == 'A') x = 2 * x + y;else y = 2 * y + x;return x + y;
}
结果分析
可以把?
2011. 执行操作后的变量值
2011. 执行操作后的变量值/
思路
差不多也算是暴力了,但是只要判断前两位就好了。
int finalValueAfterOperations(char ** operations, int operationsSize){int x = 0;for(int i = 0;i < operationsSize;++i)//遍历判断if(operations[i][0] == '+') x++; //是++xelse if(operations[i][0] == '-') x--;//是--xelse if(operations[i][1] == '+') x++;//是x++else if(operations[i][1] == '-') x--;//是x--return x;
}
结果分析
凑合玩吧
1876. 长度为三且各字符不同的子字符串
1876. 长度为三且各字符不同的子字符串/
思路
从第3个元素开始往后扫描,看看前三个字母一样不 然后做统计就好了。
int countGoodSubstrings(char * s){if(!s[0]||!s[1]||!s[2]) return 0;//长度小于3直接返回int ans = 0;for(int i = 2;s[i];i++) //遍历统计if(s[i] != s[i - 1]&&s[i] != s[i-2] && s[i - 1] != s[i - 2]) ans++;return ans;
}
结果分析
满意!
520. 检测大写字母
520. 检测大写字母/思路
我一直以为我写过这个题解,,看来没有,,好吧 这是昨天c的题
扫描所有的大写个数,并分三种情况
1.大写个数为0 就返回true
2.大写个数等于字符串长度 返回true
3.大写个数为0,且第一个为大写 则返回true
其它都是false
bool detectCapitalUse(char * word){int upnum = 0,i = 0;for(i = 0;word[i];++i){if(word[i] <= 'Z') upnum++;//判断大写数量,因为小写比大写大 所以可以这么写}if(!upnum) return true;else if(upnum == 1 &&word[0] <='Z') return true;//判断第一位是不是大写else if(upnum == i) return true;return false;
}
结果分析
满意?
709. 转换成小写字母
709. 转换成小写字母/
思路
没难度,从前到后扫描。扫描到大写就加上' '就好了,为啥看知识点。。。
char * toLowerCase(char * s){for(int i = 0;s[i];i++)if(s[i]>='A'&&s[i]<='Z') s[i]+= ' ';//扫描到大写,转换return s;
}
结果分析
行了
1704. 判断字符串的两半是否相似
1704. 判断字符串的两半是否相似/
思路
扫描一遍字符串记录长度,再次扫描前半段和后半段,统计其中的元音数量,返回两者判等的结果。
注:我创建了hash表加快了判定速度,也可以不用用循环写。
bool halvesAreAlike(char * s){int count = 0,ans1 = 0, ans2 = 0;bool f[26]; //创建元音数组memset(f,0,sizeof(f));f[0] = 1;f[4] = 1;f[8] = 1;f[14] = 1;f[20] = 1; //对应aeiouwhile(s[count]) count++; //计算数组长度for(int i = 0;i < count/2;++i) //统计前半段元音数量if(s[i] >= 'a' && f[s[i] - 'a']) ans1 ++;else if(s[i] <= 'Z'&&f[s[i] - 'A']) ans1++;for(int i = (count+1) / 2;i < count;i++) //判断后半段元音数量if(s[i] >= 'a'&&f[s[i] - 'a']) ans2++;else if(s[i] <= 'Z'&&f[s[i] - 'A']) ans2++;return ans1 == ans2;
}
结果分析
做人嘛。要开心
1844. 将所有数字用字符替换
1844. 将所有数字用字符替换/
思路
直接按照要求进行转换就好了嘛。
char * replaceDigits(char * s){for(int i = 0;s[i];++i)//遍历修改if(s[i] >='0'&&s[i] <='9') //找到修改s[i] = s[i - 1] + (s[i] -'0');return s; }
结果分析
有趣
1805. 字符串中不同整数的数目
1805. 字符串中不同整数的数目/
思路
其实按照题目要求来就好了
1.拆分字符串
2.去除头部0
3.去除重复元素的统计
int numDifferentIntegers(char * word){bool flag = false;int counti = 0,countj = 0;char spit[500][1001];//记录拆分后的字符串for(int i = 0;i == 0||word[i - 1];++i) //拆分字符串if(word[i] >= '0' && word[i] <= '9'){flag = true;spit[counti][countj++] = word[i];}else{if(flag){spit[counti++][countj] = 0;countj = 0;flag = false;}}for(int i = 0;i < counti;i++){ //删除头部的0int first = 0;while(spit[i][first] == '0') first++;if(first != 0)for(int j = first;spit[i][j - 1];++j)spit[i][j-first] = spit[i][j];}//将重复元素做标记for(int i = 0;i < counti;i++)for(int j = i + 1;j<counti;j++)if(!strcmp(spit[i],spit[j])) spit[j][0] = '#';//减去重复元素int ans = counti;for(int i = 0;i < counti;i++)if(spit[i][0] == '#') ans--;return ans;
}
结果分析
还行
写在最后
有点卷不动了,好多考试都来了,不知道大家最近过的怎么样呀,有没有被考试烦恼,再怎样也要加油呀!
更多推荐
[解题报告](第21讲) 字符串算法(一)
发布评论