[题解]《算法零基础100讲》(第25讲) 字符串算法(五) - 字符串反转_char *reverseprefix(char *word, char ch)在主函数里怎么表示调

一. 概念讲解

  字符反转就是将一个字符串翻转过来，通常我们都是分别从首位同时进行调换，或则重新定义一个字符数组，将原本的字符串从尾部一一赋值给新串。
代码如下：

#include <stdio.h>

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

int main(){
	char str[] = "abcdefg";
	Reserved(str, strlen(str));
	printf("%s\n", str);//输出结果gfedcba
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

二. 课后习题

2.1 反转字符串

题目链接：
344. 反转字符串
这道题很简单就不细讲了，左右两边对调，并且同时向中间靠近。
代码如下：

void reverseString(char* s, int sSize){
    int l = 0;
    int r = sSize - 1;
    while(l < r){
        char tmp = s[l];
        s[l] = s[r];
        s[r] = tmp;
        l++;r--;
    }
}
1
2
3
4
5
6
7
8
9
10

2.2. 反转单词前缀

题目链接：
2000. 反转单词前缀
思路分析：
  首先我们给找到它所给字母第一次出现的位置，然后再根据字符串反转的方法，将前缀反转即可。
  此外我们还需考虑特殊情况，就是所给的字母没有出现，那我们无需反转。
代码如下：

char * reversePrefix(char * word, char ch){
    int r;
    int n = strlen(word);
    for(int i = 0; i < n; i++){
        //寻找ch的下标
        if(word[i] == ch){
            r = i;break;
        }
        //如果没有则直接返回原串
        if(i == (n - 1)){
           return word; 
        }
    }
    int l = 0;
    //反转前缀
    while(l < r){
        char tmp = word[l];
        word[l] = word[r];
        word[r] = tmp;
        l++;r--;
    }
    return word;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.3 反转字符串中的元音字母

题目链接：
345. 反转字符串中的元音字母
思路分析：
  这道题只需要我们反转元音字母，所以我们要做的第一步就是将所有的元音字母记录下来，那么剩下的步骤就是将他们调转即可。
代码如下：

//判断元音字母
bool isVowels(char s){
    if(s == 'a' || s == 'e' || s == 'i' || s == 'o' || s == 'u'){
        return true;
    }
    if(s == 'A' || s == 'E' || s == 'I' || s == 'O' || s == 'U'){
        return true;
    }
    return false;
}

char * reverseVowels(char * s){
    int n = strlen(s);
    int Vowels[n];
    int Vsize = 0;
    //记录元音字母的下标
    for(int i = 0; i < n; i++){
        if(isVowels(s[i])){
            Vowels[Vsize++] = i;
        }
    }
    int l = 0, r = Vsize - 1;
    //调换元音字母
    while(l < r){
        char tmp = s[Vowels[l]];
        s[Vowels[l]] = s[Vowels[r]];
        s[Vowels[r]] = tmp;
        l++;r--;
    }
    return s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2.4 翻转单词顺序

题目链接：
剑指 Offer 58 - I. 翻转单词顺序
思路分析：
  我们可以通过指针数组*Hash[]，来记录每个单词的首字母的地址，并将所有空格改为’\0’，这样就将所有的单词都分割开来了，然后我们再定义一个字符串数组ret，因为我们的Hash里面记录了每个单词的首地址，所以通过他我们可以找到单词，然后我们从最后一个单词开始拷贝到ret中，并且每拷贝一个单词，都要加上一个空格。
代码如下：

char * reverseWords(char * s){
    int n = strlen(s);
    if(n == 0){
        return "";
    }
    char* Hash[n];
    int HashSize = 0;
    int flag = 1;
    //记录每个单词的首字母的地址，并将空格标记为\0
    for(int i = 0; i < n; i++){
        if(flag && s[i] != ' '){
            Hash[HashSize++] = s + i;
            flag = 0;
        }
        if(s[i] == ' '){
            s[i] = '\0';
            flag = 1;
        }
    }
    char* ret = malloc(n + 1);
    int retSize = 0;
    //从最后一个单词开始拷贝到ret中
    for(int i = HashSize - 1; i >= 0; i--){
        if(i < HashSize - 1)ret[retSize++] = ' ';
        for(int j = 0; j < strlen(Hash[i]); j++){
            ret[retSize++] = *(Hash[i] + j);
        }
    }
    ret[retSize] = '\0';
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

2.5 翻转字符串里的单词

题目链接：
151. 翻转字符串里的单词
这道题和上面那道题是一样的，没有太大的差别。
代码如下：

char * reverseWords(char * s){
    int n = strlen(s);
    char* Hash[n];
    int HashSize = 0;
    int flag = 1;
    //记录每个单词的首字母的地址
    for(int i = 0; i < n; i++){
        if(flag && s[i] != ' '){
            Hash[HashSize++] = s + i;
            flag = 0;
        }
        if(s[i] == ' '){
            s[i] = '\0';
            flag = 1;
        }
    }
    char* ret = malloc(n + 1);
    int retSize = 0;
    for(int i = HashSize - 1; i >= 0; i--){
        if(i < HashSize - 1)ret[retSize++] = ' ';
        for(int j = 0; j < strlen(Hash[i]); j++){
            ret[retSize++] = *(Hash[i] + j);
        }
    }
    ret[retSize] = '\0';
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2.6 反转字符串中的单词 III

题目链接：
557. 反转字符串中的单词 III
思路分析：
  这道题相对上道题的区别是，上道题是反转整个单词，这道题是将每个单词里面的字母进行反转，开始的做法还是一样用指针数组Hash将每个单词记录下来，一次达到分割的效果，最后再逐个进行反转。
代码如下：

char * reverseWords(char * s){
    int n = strlen(s);
    char* Hash[n];
    int HashSize = 0;
    int flag = 1;
    for(int i = 0; i < n; i++){
        if(s[i] != ' ' && flag){
            Hash[HashSize++] = &s[i];
            flag = 0;
        }
        if(s[i] == ' '){
            s[i] = '\0';
            flag = 1;
        }
    }
    char *ret = (char*)malloc(n + 1);
    int retSize = 0;
    for(int i = 0; i < HashSize; i++){
        if(i > 0)ret[retSize++] = ' ';
        int len = strlen(Hash[i]);
        for(int j = len - 1; j >= 0; j--){
            ret[retSize++] = *(Hash[i] + j);
        }
    }
    ret[retSize] = '\0';
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2.7 反转字符串 II

541. 反转字符串 II
思路分析：
  我们可以模拟反转，下标从2k开始的时候开始反转前k个，当子串不足k时，则反转整个子串。
代码如下：

void reverse(char* l, char* r){
    r--;
    while(l < r){
        char tmp = *r;
        *r = *l;
        *l = tmp;
        l++;r--;
    }
}

int min(int a, int b){
    return a < b ? a : b;
}

char * reverseStr(char * s, int k){
    int n = strlen(s);
    for (int i = 0; i < n; i += 2 * k) {
        reverse(&s[i], &s[fmin(i + k, n)]);
    }
    return s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.8 仅反转字母

题目链接：
917. 仅仅反转字母
思路分析：
  这到题我们只需要反转字母，所以可以运用双指针的方式，当两边的指针指向的都为字母时，则进行调换，如果左指针不是字母，那么left++，如果右指针不是字母，那么right++。
代码如下：

//判断字母
bool isalph(char s){
    if((s >= 'A' && s <= 'Z') || (s >= 'a' && s <= 'z')){
        return true;
    }
    return false;
}
//交换
void Swap(char* ch1, char* ch2){
    char tmp = * ch1;
    *ch1 = *ch2; *ch2 = tmp;
}

char * reverseOnlyLetters(char * s){
    int left = 0;
    int right = strlen(s) - 1;
    while(left < right){
        //两边都是字母则交换
        if(isalph(s[left]) && isalph(s[right])){
            Swap(s+left, s+right);
            left++;right--;
        }
        if(!isalph(s[left]))left++;
        if(!isalph(s[right]))right--;
        
    }
    return s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

2.9 整数反转

题目链接：
7. 整数反转
思路分析：
  整数反转的方式很简单，我们只需对10进行模运算和辗转相除，就可以从尾部将其拆分为一个一个的数字，再将他们组合起来即可，但由于这道题的范围是[-2 ^ 31, 2 ^ 31 - 1]，所以我们需要考虑反转后是否会越界。
代码如下：

int reverse(int x){
    int ret = 0;
    //辗转相除
    while(x){
        //判断概述反转后是否会越界
        if(ret < INT_MIN / 10 || ret > INT_MAX / 10){
            return 0;
        }
        ret *= 10;
        int p = x % 10;
        x /= 10;
        ret += p;
    }
    return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15