day9 字符串2

151.翻转字符串里的单词

class Solution {
public:
    string reverseWords(string s) {
        vector<string> vec;
        string res;
        int i = 0;
        while (i < s.size()) {
            if (s[i] == ' ') {
                i ++;
                continue;
            }
            int j = i + 1;
            while (j < s.size() && s[j] != ' ') {
                j ++;
            }
            vec.push_back(s.substr(i, j - i));
            i = j;
        }

        for (int i = vec.size() - 1; i >= 0; i --) {
            res += vec[i];
            if (i > 0) {
                res += ' ';
            }
        }
        return res;
    }
};

上面的写法用了个容器和一个新的字符串，增加了空间复杂度，容器可以不用，字符串也可以原地修改。先全部反转，再单词内局部反转。

class Solution {
public:
    void reverseWord(string &s, int left, int right) {
        for (int i = left, j = right; i < j; i ++, j --) {
            swap(s[i], s[j]);
        }

    }
    string reverseWords(string s) {
        int preSpaceCount = 0, postSpaceCount = 0;
        for (int i = 0, j = s.size() - 1; i < j && (s[i] == ' ' || s[j] == ' '); ) {
            if (s[i] == ' ') {
                preSpaceCount ++;
                i ++;
            }
            if (s[j] == ' ') {
                postSpaceCount ++;
                j --;
            }
        }
        s.erase(0, preSpaceCount);
        s.erase(s.size() - postSpaceCount, postSpaceCount);
        reverseWord(s, 0, s.size() - 1);
        int i = 0;
        while (i < s.size()) {
            int j = i;
            while (j < s.size() && s[j] != ' ') {
                j ++;
            }
            reverseWord(s, i, j - 1);
            i = j + 1;
            while (i < s.size() && s[i] == ' ') {
                s.erase(i, 1);
            }
        }
        return s;
    }
};

卡码网：55.右旋转字符串

#include <string>
#include <iostream>
using namespace std;

void reverse(string &s, int left, int right) {
   for (int i = left, j = right - 1; i < j; i ++, j --) {
       swap(s[i], s[j]);
   }
}

int main() {
   int k;
   string s;
   cin >> k;
   cin >> s;
   reverse(s, 0, s.size());
   reverse(s, 0, k);
   reverse(s, k, s.size());
   cout << s << endl;
   return 0;
}

28. 实现 strStr()

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (haystack.size() < needle.size()) {
            return -1;
        }
        for (int i = 0; i < haystack.size(); i ++) {
            int j;
            for (j = i; j < i + needle.size(); j ++) {
                if (haystack[j] != needle[j-i]) {
                    break;
                }
            }
            if (j == i + needle.size()) {
                return i;
            }
        }
        return -1;
    }
};

459.重复的子字符串

class Solution {
public:
    bool isTrue(int num, string s) {
        string sameStr = s.substr(0, num);
        for (int i = num; i < s.size(); i += num) {
            string temp = s.substr(i, num);
            if (temp != sameStr) {
                return false;
            }
        }
        return true;
    }

    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        for (int num = n - 1; num > 0; num --) {
            if (n % num != 0) {
                continue;
            }
            if (isTrue(num, s)) {
                return true;
            }
        }
        return false;
    }
};