目錄

一、演算法思想

二、反轉字串

? 三、反轉單詞前綴

四、反轉字串中的元音字母

五、反轉字串中的單詞Ⅲ

六、僅僅反轉字母

? 七、反轉字串Ⅱ

八、翻轉單詞序列

一、演算法思想

字串反轉最常用的方法是使用雙指標，分別指向字串的開頭和結尾，依次進行交換即可

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;
}