零、写在前面
这是打卡的第二十五天,今天题目好多好多啊,考虑到现在用的是深色皮肤,如果还是像之前一样放结果的话效果太差了,并且最近题量太大,篇幅太长了,所以取消之前炫富一样的结果分析,主要放思路和代码,也能更专注一些。主要知识点在
《算法零基础100讲》(第25讲) 字符串算法(五) - 字符串反转
https://blog.csdn.net/WhereIsHeroFrom/article/details/121309985
一、主要知识点
1.字符串反转
通过两个类似于指针,一个往前扫描一个往后扫描,遇到符合要求的就进行交换操作,当两个类指针相遇完成所有的操作。
char * reverseVowels(char * s){ int i = 0, j = strlen(s)-1; //创建两个类指针,并初始化 while(i < j) { while(s[i] && !isVowel(s[i])) ++i; // 寻找前面的满足条件的元素 while(j >= 0 && !isVowel(s[j])) --j; // 寻找后面的满足条件元素 if(i >= j) break; // 相遇就退出 swap( &s[i], &s[j] ); // 交换 ++i, --j; // 寻找下一个元素 } return s; }
二、课后习题
344. 反转字符串
344. 反转字符串
https://leetcode-cn.com/problems/reverse-string/
题目描述
编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
思路
从前扫描到长度的一半进行元素的交换就好了啊0.0
void reverseString(char* s, int sSize){ for(int i = 0; i < sSize/2; ++i){ //扫描到1/2 s[i] = s[i] ^ s[sSize - i -1]; //交换元素 s[sSize - i -1] = s[i] ^s[sSize - i -1]; s[i] = s[i] ^s[sSize - i -1]; } }
2000. 反转单词前缀
2000. 反转单词前缀
https://leetcode-cn.com/problems/reverse-prefix-of-word/
题目描述
给你一个下标从 0 开始的字符串 word 和一个字符 ch 。找出 ch 第一次出现的下标 i ,反转 word 中从下标 0 开始、直到下标 i 结束(含下标 i )的那段字符。如果 word 中不存在字符 ch ,则无需进行任何操作。
思路
分两步,先找到ch所在位置,然后反转ch前的元素就好了。
char * reversePrefix(char * word, char ch){ int chnum = 0; for(;word[chnum]&&word[chnum]!=ch;chnum++);//查找ch位置 if(!word[chnum]) return word; //找不到 直接返回 chnum += 1; //因为要包含ch在内全反转 所以+1 for(int i = 0;i < chnum / 2;i++){ //反转 word[i] = word[i]^word[chnum - i - 1]; word[chnum - i - 1] = word[i]^word[chnum - i - 1]; word[i] = word[i]^word[chnum - i - 1]; } return word; }
345. 反转字符串中的元音字母
345. 反转字符串中的元音字母
https://leetcode-cn.com/problems/reverse-vowels-of-a-string/
题目描述
给你一个字符串 s ,仅反转字符串中的所有元音字母,并返回结果字符串。
元音字母包括 'a'、'e'、'i'、'o'、'u',且可能以大小写两种形式出现。
思路
先根据元素值设置hash表,查表得到是否是满足条件的元素加快速度。保存所有满足条件的元素位置,然后根据位置反转字符串。
char * reverseVowels(char * s){ bool hash[256]; char target[11] = "aeiouAEIOU"; memset(hash,0,sizeof(hash)); for(int i = 0;i<10;i++) hash[target[i]] = 1; //设置target表 int changewei[300000],change = 0; //设置待交换字符位置表 for(int i = 0;s[i];i++) if(hash[s[i]]) changewei[change++] = i; //记录需要交换的位置 for(int i = 0;i < change / 2;i++){ //交换元素 s[changewei[i]] = s[changewei[i]] ^ s[changewei[change - 1 - i]]; s[changewei[change - 1 - i]] = s[changewei[i]] ^ s[changewei[change - 1 - i]]; s[changewei[i]] = s[changewei[i]] ^ s[changewei[change - 1 - i]]; } return s; }
剑指 Offer 58 - I. 翻转单词顺序
剑指 Offer 58 - I. 翻转单词顺序
https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/
题目描述
输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。为简单起见,标点符号和普通字母一样处理。例如输入字符串"I am a student. ",则输出"student. a am I"。
思路
新建一个字符串,从后往前,读到一个单词就写入一个单词。最后写入0结束符。
char* reverseWords(char* s){ char *ans = malloc(sizeof(char)*100000);//结果字符串 int ansnum = 0; //结果字符串长度 for(int i = strlen(s) - 1;i>= 0;){ while(i>=0 && s[i] == ' ') i--; //寻找非空格 int j = i; //j记录最后一个元素 while(i >= 0 && s[i]!=' ') i--;//寻找空格或者头部 for(int k = i + 1;k < j + 1;k++) //写入单词 ans[ansnum++] = s[k]; ans[ansnum ++] = ' ';//插入空格 } if(ansnum >= 2 && ans[ansnum - 2] == ' ') ans[ansnum - 2] =0;//多种情况的结束符写的位置不同 else if(ansnum >0)ans[ansnum - 1] = 0; else ans[ansnum] = 0; return ans; }
151. 翻转字符串里的单词
151. 翻转字符串里的单词
https://leetcode-cn.com/problems/reverse-words-in-a-string/
题目描述
给你一个字符串 s ,逐个翻转字符串中的所有 单词 。
单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。
请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。
思路
。。。。看上一道题去。。。一毛一样
557. 反转字符串中的单词 III
557. 反转字符串中的单词 III
https://leetcode-cn.com/problems/reverse-words-in-a-string-iii/
题目描述
给定一个字符串,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。
思路
和前面的思路差不多,找到一个单词,进行反转就好了。
char * reverseWords(char * s){ int i = 0; for(i = 0;s[i];){ while(s[i] && s[i] == ' ') i++; //找到第一个非空格 int j = i; //记录位置 while(s[i] && s[i] != ' ') i++; //找到空格作为结束 for(int k = j;k < (i + j)/2;k++){ //反转 s[k] = s[k]^s[i + j - k - 1]; s[i +j - k - 1] = s[k]^s[i + j - k - 1]; s[k] = s[k]^s[i + j - k - 1]; } } return s; }
541. 反转字符串 II
541. 反转字符串 II
https://leetcode-cn.com/problems/reverse-string-ii/
题目描述
给定一个字符串 s 和一个整数 k,从字符串开头算起,每计数至 2k 个字符,就反转这 2k 字符中的前 k 个字符。
思路
先将能凑齐2k的所有元素进行反转,剩余的元素如果够k就直接反转,不够就把k调整为剩余元素个数。
void swap(char *a,char *b){ //交换 *a = *a^*b; *b = *a^*b; *a = *a^*b; } char * reverseStr(char * s, int k){ int size = strlen(s), i = 0; for(i = 0;i < size/(2*k);i++){ //先把能反转的反转掉 for(int j = 0;j < k/2;j++) swap(&s[i*2*k+j],&s[ k - j - 1+ i*2*k]); } i = i*2*k; //记录i值 if(size%(2*k) < k) //如果不足k就把k改成剩余个数 k = size%(2*k); for(int j = 0;j<k/2;j++) swap(&s[i+j],&s[k-1-j+i]); //反转剩余元素 return s; }
917. 仅仅反转字母
917. 仅仅反转字母
https://leetcode-cn.com/problems/reverse-only-letters/
题目描述
给定一个字符串 s 和一个整数 k,从字符串开头算起,每计数至 2k 个字符,就反转这 2k 字符中的前 k 个字符。
思路
使用hash表记录所有位置,然后根据hash表反转元素。
注:感觉用大哥的双指针会好很多。但是没看就写了,,,下次得看看。
void swap(char *a,char *b){//交换元素 *a = *a^*b; *b = *a^*b; *a = *a^*b; } char * reverseOnlyLetters(char * s){ char hash[100],size= 0; for(int i = 0;s[i];++i) if((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z')) hash[size++] =i;//初始化hash表 for(int i = 0;i < size/2;i++) //交换hash元素 swap(&s[hash[i]],&s[hash[size - 1 -i]]); return s; }
7. 整数反转
7. 整数反转
https://leetcode-cn.com/problems/reverse-integer/
题目描述
给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0。
思路
这题写过,但我忘了啥时候了。。。
就是先处理成负数,因为负数范围大,然后进行计算反转 过程中判断溢出就返回0.
最后转成正确的数字,但是因为转成正数也有一个值会溢出,要注意。
int reverse(int x){ int ans = 0;bool flag = false; int min_int = -2147483648; if(x > 0){ //符号处理 x = -x; flag = true; } for(int i = 0;x;++i){ //处理最终结果 if(ans < min_int / 10) return 0;//溢出 ans *= 10; if(ans < min_int - (x%10)) return 0;//溢出 ans += (x%10); x /= 10; } if(flag && ans == min_int) return 0; //正值最大的溢出 if(flag) ans = -ans; return ans; }
写在最后
今天在图书馆,效率不是特别高,再适应适应把,反正是不会在寝室了,一个人战斗还是爽,而且路上挺冷,让人清醒,大家要注意保暖呀,天凉了。