字数统计: 1.9k字   |   阅读时长: 8分

字符串

344.反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    void reverseString(vector<char>& s) {
        for(int i = 0, j = s.size() - 1; i < j; i++, j--)
        {
            swap(s[i], s[j]);
        }
    }
};

541.反转字符串 II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

如果剩余字符少于 k 个，则将剩余字符全部反转。
如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string reverseStr(string s, int k) {
        for(int i = 0; i < s.size(); i = i + 2 * k)
        {
            if(i + k < s.size())
            {
                reverse(s.begin() + i, s.begin() + i + k);
            }
            else
            reverse(s.begin() + i, s.end());
        }
        return s;
    }
};

剑指 Offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

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
class Solution {
public:
    string replaceSpace(string s) {
        int oldsize = s.size();
        int count = 0;
        for(int i = 0; i < s.size(); i++)
        {
            if(s[i] == ' ')
            count ++;
        }
        s.resize(s.size() + 2 * count);
        int newsize = s.size();
        for(int i = newsize -1 , j = oldsize - 1; j < i; i--,j--)
        {
            if(s[j] != ' ')
            s[i] = s[j];
            else
            {
                s[i] = '0';
                s[i - 1] = '2';
                s[i - 2] = '%';
                i = i - 2;
            }
        }
        return s;
    }
};

151. 翻转字符串里的单词
给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

说明：

输入字符串 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
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    void reverse(string &s, int start, int end) //引用作为函数参数进行传递
    {
        for(int i = start, j = end; i < j; i++, j--)
        {
            swap(s[i], s[j]);
        }
    }

    void removeExtraSpaces(string &s){
        int slow = 0, fast = 0;
        while(s.size() > 0 && fast < s.size() && s[fast] == ' ')
        fast++;
        for(; fast < s.size(); fast++)
        {
            if(fast > 1 && s[fast - 1] == s[fast] && s[fast] == ' ')
            continue;
            else
            s[slow++] = s[fast];
        }
        if(slow > 1 && s[slow - 1] == ' ')
        s.resize(slow - 1);
        else
        s.resize(slow);
    }

    string reverseWords(string s) {
        removeExtraSpaces(s);
        reverse(s, 0, s.size() - 1);
        for(int i = 0; i < s.size(); i++)
        {
            int j = i;
            while(j < s.size() && s[j] != ' ')
            j++;
            reverse(s, i, j - 1);
            i = j;
        }
        return s;
    }
};

定义了三个函数: 字符串翻转函数, 去空格的函数, 和最后的单词翻转符号.

其中去空格可以使用双指针法。字符串反转函数先将整个字符串翻转, 然后去掉空格, 最后通过判断空格的位置进行单词的翻转实现最后的结果. 注意单词翻转函数调用了其他的两个函数，需要对这两个函数传递参数，所以字符串用引用的方式&s, 如果不用引用不正确。因为如果不引用传递的是形参，不会引起实际参数的变化。

reverse函数是库中的一个函数。

剑指 Offer 58 - II. 左旋转字符串 - 力扣（LeetCode） (leetcode-cn.com)

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    string reverseLeftWords(string s, int n) {
        reverse(s.begin(), s.begin() + n); //左闭右开区间
        reverse(s.begin() + n, s.end());
        reverse(s.begin(), s.end());
        return s;
    }
};

注意reverse的作用范围。

28. 实现 strStr() - 力扣（LeetCode） (leetcode-cn.com)
实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

说明：当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。

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
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = 0;
        int i = 0;
            for(i = 0; i < haystack.size(); i++)
            {
                if(needle.size() == 0)
                break;
                if(needle[n] == haystack[i])
                {
                    int j = i;
                    int k = n;
                    while(needle[k] == haystack[j] && j < haystack.size() && k < needle.size())
                    {
                        j++;
                        k++;
                    }
                    if(k == needle.size())
                        break;
                    else
                        continue; 
                }
            }
            if(i == haystack.size() && i != 0 ||haystack.size() < needle.size())
            i = -1;
            return i;
    }
};

注意返回为0的判断要考虑全面, 需要加上haystack.size() < needle.size()一句

这种方法时间复杂度是O(m*n)

如果用KMP算法, 可以大大降低时间复杂度.

例子:要在文本串：aabaabaafa 中查找是否出现过一个模式串：aabaaf。

前缀表指的是模式串的最长相同前后缀, 比如上面的例子就是(0, 1, 0, 1, 2, 0)

这个前缀表写代码的时候也叫做next数组, next数组的求解方式如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
void getNext(int* next, const string& s) {
    int j = 0;
    next[0] = 0;  //初始化
    for(int i = 1; i < s.size(); i++) {
        while (j > 0 && s[i] != s[j]) { // j要保证大于0，因为下面有取j-1作为数组下标的操作
            j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置了
        }  //字符不匹配的情况
        if (s[i] == s[j]) {
            j++;
        }  //字符匹配的情况
        next[i] = j; //将最长字串的值赋给next数组
    }
}

其中j的物理含义是前缀末尾, i的物理含义是后缀末尾。

28题的KMP解法

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
32
33
class Solution {
public:
    void getNext(string &s, int *next)
    {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++)
        {
            while(j > 0 && s[i] != s[j])
            j = next[j - 1];
            if(s[i] == s[j])
            j++;
            next[i] = j;
            }
    }
    int strStr(string haystack, string needle) {
        if(needle.size() == 0)
        return 0;
        int next[needle.size()];
        getNext(needle, next);
        int j = 0;
        for(int i = 0; i < haystack.size(); i++)
        {
            while(j > 0 && haystack[i] != needle[j])
            j = next[j - 1];
            if(haystack[i] == needle[j])
            j++;
            if(j == needle.size())
            return(i - needle.size() + 1);
        }
        return -1;
    }
};

459. 重复的子字符串

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。

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
class Solution {
public:
    void getNext(const string &s, int *next)
    {
        next[0] = 0;
        int j = 0;
        for(int i = 1; i < s.size(); i++)
        {
            while(j > 0 && s[j] != s[i])
            j = next[j - 1];
            if(s[i] == s[j])
            j++;
            next[i] = j;
        }
    }
    bool repeatedSubstringPattern(string s) {
        int next[s.size()];
        if(s.size() == 0)
        return false;
        getNext(s, next);
        if(next[s.size() - 1] != 0 && s.size() % (s.size() - next[s.size() - 1]) == 0)
        return true;
        return false;
    }
};

也是KMP的思想, 先求next数组,然后如果数组末尾非0且 字符串长度 % (字符串长度 - next数组最后一个元素) == 0则说明字符串可以由子字符串构成。

如果getNext想不出来了, 就考虑字符串aabaaa.s

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

这一定是一个<br><br>很长很长的一生啊