跳到主要内容

字符串

344. 反转字符串​

344. 反转字符串

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0;
        int right = s.size() - 1;
        char tmp;
        while (left < right) {
            std::swap(s[left], s[right]);

            left++;
            right--;
        }
    }
};

关于交换变量的几种方式：

  1. 使用 tmp 变量参与运算
  2. ==使用位运算==
  3. 使用库函数 swap()
// 位运算
s[i] ^= s[j];
s[j] ^= s[i];
s[i] ^= s[j];

541. 反转字符串 II​

力扣题目链接(opens new window)

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

如果剩余字符少于 k 个，则将剩余字符全部反转。

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

class Solution {
public:
    string reverseStr(string s, int k) {
        for (int i = 0; i < s.size(); i += (2 * k)) {
            if (i + k <= s.size()) {
                std::reverse(s.begin() + i, s.begin() + i + k);
            } else {
                std::reverse(s.begin() + i, s.end());
            }
        }
        return s;
    }
};

剑指 Offer 05. 替换空格​

剑指 Offer 05. 替换空格

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

class Solution {
public:
    string replaceSpace(string s) {
        int count = 0;
        int old_size = s.size();
        for (int i = 0; i < old_size; i++) {
            if (s[i] == ' ') {
                count++;
            }
        }
        s.resize(old_size + 2 * count);
        int new_size = s.size();
        for (int i = new_size - 1, j = old_size - 1; j < i; i--, j--) {
            if (s[j] != ' ') {
                s[i] = s[j];
            } else {
                s[i] = '0';
                s[--i] = '2';
                s[--i] = '%';
            }
        }
        return s;
    }
};

151. 翻转字符串里的单词​

给定一个字符串，逐个翻转字符串中的每个单词。

class Solution {
public:
    void reverseString(string &s, int begin, int end) {
        reverse(s.begin() + begin, s.begin() + end);
    }

    void removeExtraSpaces(string &s) {
        int old_index = 0;
        int new_index = 0;
        while (old_index < s.size()) {
            if (s[old_index] != ' ') {
                if (new_index > 0) {
                    s[new_index++] = ' ';
                }
                while (old_index < s.size() && s[old_index] != ' ') {
                    s[new_index++] = s[old_index++];
                }
            } else {
                old_index++;
            }
        }
        s.resize(new_index);
    }

    string reverseWords(string s) {
        removeExtraSpaces(s);
        reverseString(s, 0, s.size());

        int word_start = 0;
        for (int word_end = 0; word_end < s.size(); word_end++) {
            if (word_end == s.size() - 1 || s[word_end + 1] == ' ') {
                reverseString(s, word_start, word_end + 1);
                word_start = word_end + 2;
            }
        }

        return s;
    }
};

剑指 Offer 58-II. 左旋转字符串​

力扣题目链接(opens new window)

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

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

28. 实现 strStr()​

力扣题目链接(opens new window)

实现  strStr()  函数。

给定一个  haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从 0 开始)。如果不存在，则返回   -1。

示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2

示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1

说明: 当  needle  是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当  needle  是空字符串时我们应当返回 0 。这与 C 语言的  strstr()  以及 Java 的  indexOf()  定义相符。

class Solution {
public:
    void getNext(int* next, const string &needle) {
        int j = -1;
        next[0] = j;
        for (int i = 1; i < needle.size(); i++) {
            while (j >= 0 && needle[i] != needle[j + 1]) {
                j = next[j];
            }
            if (needle[i] == needle[j + 1]) {
                j++;
            }
            next[i] = j;
        }
    }

    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = -1;
        for (int i = 0; i < haystack.size(); i++) {
            while (j >= 0 && haystack[i] != needle[j + 1]) {
                j = next[j];
            }
            if (haystack[i] == needle[j + 1]) {
                j++;
            }
            if ((j + 1) == needle.size()) {
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

459. 重复的子字符串​

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

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = -1;
        next[0] = j;
        for (int i = 1; i < s.size(); i++) {
            while (j >= 0 && s[i] != s[j + 1]) {
                j = next[j];
            }
            if (s[i] == s[j + 1]) {
                j++;
            }
            next[i] = j;
        }
    }

    bool repeatedSubstringPattern(string s) {
        int next[s.size()];
        getNext(next, s);
        int len = s.size();
        if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) {
            return true;
        }
        return false;
    }
};