【解题报告】《算法零基础100讲》(第25讲) 字符串算法(五) - 字符串反转

617035918 发布于2021-11-15 11:38 / 1338人阅读

摘要：那我们怎么解决呢我们可以从后往前遍历，当找到一个单词的开头的时候就将他放入数列中，从而实现了逆序。

一、算法思想

一、算法思想

字符串反转最常用的方法是使用双指针，分别指向字符串的开头和结尾，依次进行交换即可

void swap(char* a, char*b){    char* tmp = *a;    *a = *b;    *b = tmp;}void reverseString(char* s, int sSize){    int left = 0;    int right = sSize - 1;    while(left < right)    {        swap(&s[left],&s[right]);        left++;        right--;    }}

有了上面的知识我们就可以开始做题了。

二、反转字符串

https://leetcode-cn.com/problems/reverse-string/http://反转字符串①题目呈现

难度：★☆☆☆☆

②参考题解

void reverseString(char* s, int sSize){    int left = 0;    int right = sSize - 1;    while(left < right)    {        int tmp = s[left];        s[left] = s[right];        s[right] = tmp;        left++;        right--;    }}

三、反转单词前缀

反转单词前缀https://leetcode-cn.com/problems/reverse-prefix-of-word/

①题目呈现

难度：★☆☆☆☆

【分析】和上一题相比只需要多一个对于ch的判断即可

②参考代码

void swap(char* a, char*b){    char tmp = *a;    *a = *b;    *b = tmp;}char * reversePrefix(char * word, char ch){    int i = 0;    while(word[i] && word[i] != ch)    {        i++;    }    printf("%d ",i);    if(!word[i])        return word;    int p = 0;    while(p < i)    {        swap(&word[p],&word[i]);        p++;        i--;    }    return word;}

四、反转字符串中的元音字母

反转字符串中的元音字母https://leetcode-cn.com/problems/reverse-vowels-of-a-string/①题目呈现

难度： ★☆☆☆☆

【分析】只要加上对元音的判断即可

②参考代码

char vowel[] = "aeiouAEIOU";bool isVowel(char ch) {    for (int i = 0; vowel[i]; i++) {        if (vowel[i] == ch) {            return true;        }    }    return false;};char* reverseVowels(char* s) {    int n = strlen(s);    int i = 0, j = n - 1;    while (i < j) {        while (i < n && !isVowel(s[i])) {            ++i;        }        while (j > 0 && !isVowel(s[j])) {            --j;        }        if (i < j) {            char* tmp = s[i];            s[i] = s[j], s[j] = tmp;            ++i;            --j;        }    }    return s;

五、反转字符串中的单词Ⅲ

反转字符串中的元音单词Ⅲhttps://leetcode-cn.com/problems/reverse-words-in-a-string-iii/①题目呈现

难度：★☆☆☆☆

【分析】以空格作为每个字符串的分界，所以本质上还是字符串反转

②参考代码

void reverse(char*s ,int left, int right){    while(left < right)    {        int tmp = s[left];        s[left] = s[right];        s[right] = tmp;        left++;        right--;    }}char * reverseWords(char * s){    int len = strlen(s);    int fast = 1;    int slow = 0;    while(fast < len)    {        if(s[fast] == " "  )//还应该注意到最后面没有空格        {            reverse(s, slow ,fast - 1);            slow = fast + 1;        }        fast++;    }    reverse(s, slow, fast - 1);    return s;}

六、仅仅反转字母

仅仅反转字母https://leetcode-cn.com/problems/reverse-only-letters/https://leetcode-cn.com/problems/reverse-only-letters/①题目呈现

难度： ★☆☆☆☆

【分析】我们在用指针遍历的时候，遇到字母才发生交换

②参考代码

bool is_c(char c){    return (c >= "a" && c <= "z") || (c >="A" && c <="Z");}void swap(char*a,char*b){    char tmp = *a;    *a = *b;    *b = tmp;}char * reverseOnlyLetters(char * s){    int slow = 0;    int fast = strlen(s) - 1;    while(slow < fast)    {        while(slow < fast && !is_c(s[slow]))        {            slow++;        }        while(slow < fast && !is_c(s[fast]))        {            fast--;        }        swap(&s[slow],&s[fast]);        fast--;        slow++;    }    return s;}

七、反转字符串Ⅱ

反转字符串Ⅱhttps://leetcode-cn.com/problems/reverse-string-ii/①题目呈现

难度： ★★☆☆☆

【分析】在反转的时候还需要判断个数，我们交给while去循环就好了

②参考代码

void swap(char*left,char*right){    while(left < right)    {        char tmp = *left;        *left = *right;        *right = tmp;        left++;        right--;    }}char * reverseStr(char * s, int k){    int  p = 0;    int len = strlen(s);    while(len >= 2*k)    {        swap(&s[p], &s[p + k - 1]);        len -= 2*k;        p += 2*k;    }    if(len >=k)    {        swap(&s[p],&s[p + k - 1]);        len -= k;        p += k;    }    else if(len >= 2)        swap(&s[p],&s[p + len - 1]);    return s;}

八、翻转单词序列

翻转单词序列https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/①题目呈现

难度：★★★☆☆

【分析】不同于前面都是字母进行交换，这里我们需要对单词进行交换。那我们怎么解决呢？我们可以从后往前遍历，当找到一个单词的开头的时候就将他放入res数列中，从而实现了逆序。只不过这里我们还需要额外考虑空格的干扰

②参考代码

char* reverseWords(char* s){    int len = strlen(s);     if(len == 0)//什么都没有的情况        return "";    int left = 0;    int right = len - 1;    char blank[] = " ";    char* ans = (char*) malloc(sizeof(char) * len + 1);    memset(ans,0,sizeof(char) * len  + 1);    while(s[left] == " " && left < right)//找到自左向右第一个单词    {        left++;    }    while(s[right] == " " && right > left)//找到自右向左第一个单词    {        right--;    }    if(right == left && s[left] == " ")// 全是空格的情况        return "";    s[right + 1] = "/0";//删除末尾多余空格    while(right > left)    {        if(s[right] == " ")            s[right] = "/0";        else if(s[right-1] == " ")//找到当前单词的开头        {            strcat(ans,&s[right]);            strcat(ans,blank);        }        right--;    }    strcat(ans,&s[left]);    return ans;}

私有云 idc机房托管字符串处理算法匹配算法零基础学大数据算法字符串算法字符串查找算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/123293.html

《算法零基础100讲》(第25讲) 字符串算法(五) - 字符串反转

摘要：双特惠付费专栏优惠券文章目录零写在前面一概念定义二题目描述三算法详解四源码剖析五推荐专栏六习题练习零写在前面这是算法零基础讲专栏打卡学习的第二十五天了。每天都会有五六篇高质量的解题报告被我加精。 ...

abson 2021-11-15 11:38 评论0 收藏0
《算法零基础100讲》(第26讲) 字符串算法(六) - 回文串

摘要：双特惠付费专栏优惠券文章目录零写在前面一概念定义二题目描述三算法详解四源码剖析五推荐专栏六习题练习零写在前面这是算法零基础讲专栏打卡学习的第二十六天了。每天都会有五六篇高质量的解题报告被我加精。 ...

Joyven 2021-11-16 11:44 评论0 收藏0
【万人千题】结对编程排位赛(第一期) 第一周排名公布，这也太卷了

摘要：万人千题结对编程排位赛如果想参加的第二期的同学，可以先联系作者加群，看看第一期的同袍是如何奋斗的。 ?付费专栏券(电脑打开有优惠)? 博主会带领大家进行...

stefanieliang 2021-11-15 11:38 评论0 收藏0
《算法零基础100讲》(第33讲) 排序入门 - 冒泡排序

摘要：文章目录零写在前面一概念定义二题目描述三算法详解四源码剖析五推荐专栏六粉丝福利零写在前面这是算法零基础讲专栏打卡学习的第三十三天了。这就是经典的帮助他人的同时，成就自己。目前，万人千题社区每天都会有五六篇高质量的解题报告被我加精。 ...

Simon_Zhou 2021-11-23 09:51 评论0 收藏0
《算法零基础100讲》(第32讲) 多维枚举(二) - 进阶

摘要：文章目录零写在前面一概念定义二题目描述三算法详解四源码剖析暴力枚举哈希降维五推荐专栏六粉丝福利零写在前面这是算法零基础讲专栏打卡学习的第三十二天了。目前，万人千题社区每天都会有五六篇高质量的解题报告被我加精。 ...

ZHAO_ 2021-11-22 09:34 评论0 收藏0